stack and queue: The Newest Leaves First, or the Oldest

Bob types a paragraph, makes a word bold, then deletes a line by mistake. When he presses Undo, the editor must take back the newest change first, like the top plate of a pile. Alice's bakery has the opposite job: it serves customers in the order they came, which is a line. A vector or a deque could do both jobs, but each also allows moves these jobs must never make. This lesson gives each job a container that allows only the right moves.

Two jobs, two orders

Bob's undo list and Alice's line hold the same kind of thing, a few items in arrival order. What differs is which item leaves first. In Bob's list the newest item leaves first, an order called LIFO: last in, first out. In Alice's line the oldest item leaves first, an order called FIFO: first in, first out.

A stack is a container in LIFO order, and a queue (say "cue") is a container in FIFO order. A stack is open at one end only, called its top. A queue is open at two ends: things join at the back and leave from the front.

So ask one question of any job: who leaves first, the newest or the oldest? The newest means a stack, and the oldest means a queue.

A stack moves at one end

Now watch a stack move. Each step below is one call on a stack of plates, numbered 1, 2 and 3 in the order they arrive. Look at where every push lands and where every pop takes from.

The plates went in as 1, 2, 3 and came out as 3, 2, 1. Nothing ever touched plate 1 until the plates above it had gone. So a stack gives its items back in the reverse of the order they went in.

A queue moves at both ends

The same kind of steps on a queue now. Three tickets join Alice's line, two leave, and one more joins. Watch the front and the back separately.

On a queue, push works at the back and pop at the front, so they never meet. Ticket 104 came last and waits behind everyone. So a queue gives its items back in the same order they went in.

The syntax you need on day one

#include <stack>
#include <queue>

stack<T> s;                an empty stack of T
s.push(x);                 put x on the top
s.top()                    the top element, the newest
s.pop();                   remove the top element; returns nothing

queue<T> q;                an empty queue of T
q.push(x);                 add x at the back
q.front()                  the front element, the oldest
q.back()                   the back element, the newest
q.pop();                   remove the front element; returns nothing

s.size()    s.empty()      how many, and whether there are none (q too)

So a stack has three working calls, push, top and pop, and a queue has four: push, front, back and pop.

An adaptor: a container with a narrower door

std::stack and std::queue do not store anything themselves. Each keeps another container inside, a deque unless you choose otherwise, and passes your calls on to it. A class that wraps another one like this is called an adaptor. Module 4's lesson 04 already showed it: its container_type program printed queue keeps a deque inside: yes.

The adaptor's whole job is the narrower door. The deque inside has a front, a back and a middle you can index. The stack lets you reach only its top, and the queue only its two ends. A call that is not on the door does not compile, and lesson 02 shows each message.

Every call on the door is one call on the deque inside, at one of its ends. Module 4 showed that a deque's ends are cheap, so every push, look and pop here is cheap too. So an adaptor adds no new storage: it takes moves away, and keeps the ones the job needs.

push, top and pop on a stack

push(x) puts x on the top. top() tells you what is on the top now. pop() removes it. This program prints the top and the size after each call.

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> s;
    s.push(10);
    s.push(20);
    s.push(30);
    cout << "top " << s.top() << ", size " << s.size() << '\n';
    s.pop();
    cout << "top " << s.top() << ", size " << s.size() << '\n';
    s.push(40);
    cout << "top " << s.top() << ", size " << s.size() << '\n';
    return 0;
}

top 30, size 3
top 20, size 2
top 40, size 3

After the pop, 20 came back to the top, because it was under 30. Then 40 went on top of 20. The 10 at the bottom was never seen: a stack shows you only its top. So top() always answers with the most recent push that has not been popped.

push, front, back and pop on a queue

A queue's push(x) adds x at the back. front() is the oldest element and back() the newest. pop() removes the front one.

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;
    q.push(10);
    q.push(20);
    q.push(30);
    cout << "front " << q.front() << ", back " << q.back() << ", size " << q.size() << '\n';
    q.pop();
    cout << "front " << q.front() << ", back " << q.back() << ", size " << q.size() << '\n';
    q.push(40);
    cout << "front " << q.front() << ", back " << q.back() << ", size " << q.size() << '\n';
    return 0;
}

front 10, back 30, size 3
front 20, back 30, size 2
front 20, back 40, size 3

These are the same calls as the stack program, with front and back in place of top. Yet the pop took 10, not 30. Module 4 said a queue has three moves: push at the back, look at the front, pop from the front. back() is one more look, and it never moves anything. So on a queue, the pop always takes the element that has waited longest.

pop returns nothing: read first, then pop

Bob wants the top value and its removal in one line, so he writes this.

stack<int> s;
s.push(4);
int x = s.pop();

GCC 12 stops at the runner's flags with error: void value not ignored as it ought to be. void means "no value": pop() removes the element and hands nothing back. The same holds for a queue's pop(). Lesson 05 explains why the library was designed this way. The fix is two lines, a read and then a pop.

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> s;
    s.push(4);
    s.push(9);
    int x = s.top();
    s.pop();
    cout << "took " << x << ", now the top is " << s.top() << '\n';
    return 0;
}

took 9, now the top is 4

On a queue the idiom is the same, with front() in place of top(). So you will write this pair, a look and then a pop, in almost every stack or queue program.

The empty adaptor: Zara's first test

Zara always tries the empty case first. She asks an empty stack for its top plate.

stack<int> plates;
cout << "top plate: " << plates.top() << '\n';

It compiled with no message at the runner's flags. On Compiler Explorer's GCC 12.2, in one run, the program printed nothing and crashed with SIGSEGV, the signal for reading memory it does not own. Even the words top plate: never appeared, because cout still held them when it crashed. Then she asked an empty queue for its front. That run printed first in line: 0 and ended normally.

Both are undefined behaviour: the C++ standard says nothing about what happens. So one run crashes, and another prints a 0 that is not a customer. pop() on an empty adaptor is undefined too. So write if (!s.empty()) before every top(), front(), back() or pop() whose input you do not control.

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);
    while (!s.empty()) {
        cout << "pop " << s.top() << '\n';
        s.pop();
    }
    return 0;
}

pop 3
pop 2
pop 1

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    while (!q.empty()) {
        cout << "pop " << q.front() << '\n';
        q.pop();
    }
    return 0;
}

pop 1
pop 2
pop 3

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main() {
    stack<string> changes;
    changes.push("typed a paragraph");
    changes.push("made a word bold");
    changes.push("deleted a line");

    for (int press = 1; press <= 2; press++) {
        cout << "undo: " << changes.top() << '\n';
        changes.pop();
    }
    cout << "next undo would take back: " << changes.top() << '\n';
    cout << changes.size() << " change left\n";
    return 0;
}

undo: deleted a line
undo: made a word bold
next undo would take back: typed a paragraph
1 change left

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> line;
    for (int ticket = 101; ticket <= 104; ticket++) {
        line.push(ticket);
    }
    cout << line.size() << " waiting, front " << line.front() << ", back " << line.back() << '\n';

    for (int served = 0; served < 2; served++) {
        cout << "serving ticket " << line.front() << '\n';
        line.pop();
    }
    line.push(105);
    cout << line.size() << " waiting, front " << line.front() << ", back " << line.back() << '\n';
    return 0;
}

4 waiting, front 101, back 104
serving ticket 101
serving ticket 102
3 waiting, front 103, back 105

stack<int> s;
s.push_back(5);

stack<int> s;
s.push(4);
s.push(9);
s.pop();
cout << "took " << s.top() << '\n';

#include <iostream>
using namespace std;

int main() {
    queue<int> q;
    q.push(5);
    cout << q.front() << '\n';
    return 0;
}

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

int main() {
    stack<int> s;
    queue<int> q;
    s.push(1);
    s.push(2);
    s.pop();
    s.push(3);
    q.push(1);
    q.push(2);
    q.pop();
    q.push(3);
    cout << s.top() << ' ' << q.front() << '\n';
    return 0;
}

#include <iostream>
#include <queue>
#include <string>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = 0;
    cin >> n;
    queue<string> line;
    for (int i = 0; i < n; i++) {
        string op;
        cin >> op;
        if (op == "join") {
            string name;
            cin >> name;
            // Add name at the back of line.
        } else {
            // op is "serve": print the name at the front and remove it,
            // or print nobody if line is empty.
        }
    }

    // Print the names still waiting, front to back, separated by single
    // spaces, or the word empty if nobody is left.

    return 0;
}

#include <iostream>
#include <queue>
#include <stack>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        string word;
        cin >> word;
        stack<char> from_end;
        queue<char> from_start;
        // Push every letter of word into both containers.
        // Then compare from_end.top() with from_start.front(), pop both,
        // and repeat until they are empty. Print yes or no.
    }
    return 0;
}

#include <iostream>
#include <stack>
using namespace std;

int main() {
    int n;
    cin >> n;
    stack<int> pile;
    for (int i = 0; i < n; i++) {
        int w;
        cin >> w;
        pile.push(w);
    }

    stack<int> sorted;
    // Move crates one at a time until pile is empty, so that every crate
    // in sorted sits on a heavier or equal one. You may hold one crate in
    // a variable, and you may move crates from sorted back onto pile.
    // Then print sorted from its top to its bottom.

    return 0;
}

Next, lesson 02 goes through every operation of both adaptors, one by one, each with its cost, and everything they refuse.