Arrays & Linear Structures

stack

A stack is a collection where you only ever touch the top, like a stack of plates: you put a new plate on top and you take the top one off. Whatever went in last comes out first — this is called LIFO, last in, first out. The two core moves are push (add to the top) and pop (remove the top); peek just looks at the top without removing it.

Because all the action happens at one end, a stack is cheap: push and pop are both O(1). You can build one on top of a dynamic array (push = append, pop = remove last) or a linked list (push/pop at the head). C++ offers std::stack as a ready-made wrapper. There is deliberately no fast way to reach into the middle — that restriction is the point, and it keeps the structure simple and fast.

Stacks show up everywhere once you look. The call stack tracks which function called which and how to return; undo history pops the last action; matching brackets, evaluating expressions, and the backtracking in depth-first search all lean on a stack to remember where to come back to.

#include <stack>
std::stack<int> s;
s.push(1); s.push(2); s.push(3);
//  top -> | 3 |
//         | 2 |
//         | 1 |   (bottom)
int t = s.top();   // 3   (peek, O(1))
s.pop();           // removes 3, O(1)
// now top() == 2

LIFO order; push and pop are both O(1).

Stack the data structure is not the same as the call stack of a running program — but the call stack is literally a stack, which is why the name is shared.

Also called

LIFOLIFO stack栈堆栈堆疊後進先出