Stack

A stack keeps items like a pile of plates: you put a plate on top and take one from the top, so the newest item leaves first. Each operation takes $O (1)$ time. If the oldest item must leave first, use a queue; if the smallest, use a priority queue.

Use it when things must be finished in the reverse order of starting, such as actions to undo in an editor. If you only ever need the last item, one variable is enough. A stack is for when, after finishing the newest item, you need the one before it.

How it works

The item you can reach, like the plate on top of the pile, is the top. Push puts an item on top, and pop takes the top item off. This order is called last in, first out.

Operation	What it does	Time
`push(x)`	puts `x` on top	$O (1)$
`top()`	the item on top	$O (1)$
`pop()`	removes the item on top	$O (1)$
`empty()`, `size()`	is it empty, how many items	$O (1)$

A stack fits in an array a and a counter cnt, the number of items. The bottom item is in cell 0, so the top is in cell cnt - 1. Push writes x into cell cnt and adds 1 to cnt; top reads cell cnt - 1; pop subtracts 1 from cnt. No item ever moves, and each operation touches one cell or the counter, so each takes $O (1)$ time. A stack has no fixed size: when the array is full, it grows the way a vector does.

Let's run a few commands on an empty stack to see how it works.

The stack is empty: cnt is 0, so the first free cell is cell 0.

1/12

Fig. 1. The 11 commands on an array a of 6 cells. The blue arrow points to cell cnt, the first free cell; a popped item leaves to the right.

The two pops print 1 and 4, the newest item each time. Then top prints 7 without removing it, and size prints 5.

In C++

The C++ stack is in the header <stack>, and stack<int> st; declares an empty stack of integers. It has the operations from the table and grows as needed.

The program below reads the number of commands q ( $1 \leq q \leq 1 0^{5}$ 1 \le q \le 10^5), then q lines, each push x ( $∣ x ∣ \leq 1 0^{9}$ |x| \le 10^9), pop, top or size. pop and top come only when the stack is not empty. For pop it prints the removed item, for top the item on top, for size the number of items. The example above is this input:

11
push 5
push 8
push 2
push 6
push 1
pop
push 4
pop
push 7
top
size

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

int main() {
    int q;
    cin >> q;
    stack<int> st;

    for (int i = 0; i < q; i++) {
        string cmd;
        cin >> cmd;
        if (cmd == "push") {
            int x;
            cin >> x;
            st.push(x);
        } else if (cmd == "pop") {
            cout << st.top() << '\n';   // read the top first
            st.pop();                   // pop returns nothing
        } else if (cmd == "top") {
            cout << st.top() << '\n';
        } else if (cmd == "size") {
            cout << st.size() << '\n';
        }
    }
}

Examples of use

Depth-first search without recursion keeps the vertices waiting to be explored in a stack, so it always goes on from the vertex found last.

A recursive function uses a stack without showing it: the calls that have started and not yet finished wait in the call stack, and the call started last finishes first. That is why very deep recursion can run out of stack memory.

Common mistakes

Reading the top from the wrong cell. In the array version the top is in a[cnt - 1]; a[cnt] is the first free cell, which holds an old value or doesn't exist.
Popping before reading. After st.pop(), st.top() gives the item below, so read st.top() first and then call st.pop().

Similar structures

A queue is the opposite order: items join at one end and leave from the other, so the oldest item leaves first.

A deque adds and removes items at both ends, so it can work as a stack and as a queue at once.

A monotonic stack is a stack whose items stay sorted: before a push, it pops every item that would break the order. It finds the nearest greater element to the left of every position of an array in $O (n)$ .