Lecture 4/15: Stacks and Queues


April 15, 2020

📂Associated files

Stacks and Queues

CS 106B: Programming Abstractions

Spring 2020, Stanford University Computer Science Department

Lecturers: Chris Gregg and Julie Zelenski

A stack of pancakes and a queue of students


Announcements


Slide 2

Abstract Data Types


Slide 3

Stacks

A stack is an abstract data type with the following behaviors / functions:

Why do we call it a stack? Because we model it using a stack of things:

A stack showing that elements are pushed and popped at the top, only


Slide 4

Stacks


Slide 5

Stacks: Tradeoffs


Slide 6

Reversing the words in a sentence

  1. Use a stack
  2. Read characters in a string and place them in a new word.
  3. When we get to a space, push that word onto the stack, and reset the word to be empty.
  4. Repeat until we have put all the words into the stack.
  5. Pop the words from the stack one at a time and print them out.

Slide 7

Reversing the words in a sentence with a stack

#include <iostream>
#include "console.h"
#include "stack.h"

using namespace std;
const char SPACE = ' ';

int main() {
    string sentence = "hope is what defines humanity";
    string word;
    Stack<string> wordStack;

    cout << "Original sentence: " << sentence << endl;

    for (char c : sentence) {
       if (c == SPACE) {
           wordStack.push(word);
           word = ""; // reset
       } else {
           word += c;
       }
    }
    if (word != "") {
        wordStack.push(word);
    }

    cout << "     New sentence: ";
    while (!wordStack.isEmpty()) {
        word = wordStack.pop();
        cout << word << SPACE;
    }
    cout << endl;

    return 0;
}

Output:

Original sentence: hope is what defines humanity
     New sentence: humanity defines what is hope 

Slide 8

Next…

A line (queue) of people


Slide 9

Queues

A line (queue) of people that says, 'The last person in line is the last person served. The first person in line is the first person served'


Slide 10

Queues


Slide 11

Queue Examples


Slide 12

Queue Mystery

The words 'Code Mystery' with a fingerprint


Slide 13

Queue Idiom 1


Slide 14

Queue Idiom 2


Slide 15

More advanced stack example

A stack of pancakes


Slide 16

Postfix Example

5 4 * 8 2 / - 9 +

*Postfix notation is also called "Reverse Polish Notation" (RPN) because in the 1920s a Polish logician named Jan Łukasiewicz invented "prefix" notation, and postfix is the opposite of postfix, and therefore so-called "Reverse Polish Notation"


Slide 17

Postfix Example Code

// Postfix arithmetic, implementing +, -, *, /

#include <iostream>
#include "console.h"
#include "simpio.h"
#include "stack.h"

using namespace std;

const string OPERATORS = "+-*x/";
const string SEPARATOR = " ";

// function prototypes
double parsePostfix(string expression);
string getNextToken(string &expression);
void performCalculation(Stack<double> &s, char op);

// Postfix arithmetic, implementing +, -, *, /

#include <iostream>
#include "console.h"
#include "simpio.h"
#include "stack.h"

using namespace std;

const string OPERATORS = "+-*x/";
const string SEPARATOR = " ";

// function prototypes
double parsePostfix(string expression);
string getNextToken(string &expression);
void performCalculation(Stack<double> &s, char op);

int main() {
    string expression;
    double answer;
    do {
        expression = getLine("Please enter a postfix expression (blank to quit): ");
        answer = parsePostfix(expression);
        cout << "The answer is: " << answer << endl << endl;
    } while (expression != "");
    return 0;
}

int main() {
    string expression;
    double answer;
    do {
        expression = getLine("Please enter a postfix expression (blank to quit): ");
        if (expression == "") {
            break;
        }
        answer = parsePostfix(expression);
        cout << "The answer is: " << answer << endl << endl;
    } while (true);
    return 0;
}

string getNextToken(string &expression) {
    // pull out the substring up to the first space
    // and return the token, removing it from the expression

    string token;
    int sepLoc = expression.find(SEPARATOR);
    if (sepLoc != (int) string::npos) {
        token = expression.substr(0,sepLoc);
        expression = expression.substr(sepLoc+1,expression.size()-sepLoc);
        return token;
    }
    else {
        token = expression;
        expression = "";
        return token;
    }
}

double parsePostfix(string expression) {
    Stack<double> s;
    string nextToken;
    
    while (expression != "") {
        // gets the next token and removes it from expression
        nextToken = getNextToken(expression);
        if (OPERATORS.find(nextToken) == string::npos) {
            // we have a number
            double operand = stringToDouble(nextToken);
            s.push(operand);
        }
        else {
            // we have an operator
            char op = stringToChar(nextToken);
            performCalculation(s,op);
        }
    }
    return s.pop();
}

void performCalculation(Stack<double> &s, char op) {
    double result;
    double operand2 = s.pop(); // LIFO!
    double operand1 = s.pop();
    switch(op) {
        case '+': result = operand1 + operand2;
            break;
        case '-': result = operand1 - operand2;
            break;
            // allow "*" or "x" for times
        case '*':
        case 'x': result = operand1 * operand2;
            break;
        case '/': result = operand1 / operand2;
            break;
    }
    s.push(result);
}

Example run:

Please enter a postfix expression (blank to quit): 5 4 * 8 2 / - 9 +
The answer is: 25

Please enter a postfix expression (blank to quit): 1 2 3 4 + + +
The answer is: 10
 
Please enter a postfix expression (blank to quit): 1 2 3 4 - - -
The answer is: -2
 
Please enter a postfix expression (blank to quit): 1 2 + 3 * 6 + 2 3 + /
The answer is: 3 

Please enter a postfix expression (blank to quit): 2 3 4 + * 6 - 
The answer is: 8 

Slide 18

World's First Programmable Desktop Computer

The HP 9100A desktop calculator