Stack (LIFO) & Expression Evaluation

Every function call your program makes is pushed onto a stack, and every Ctrl+Z pops one. The same tiny structure lets a compiler parse your code and a calculator respect operator priority.

★ Lecture: STL_stack · Zaza Gamezardashvili▶ video beginner⏱ 15 min read

←Builds on

0Recursion & the Call StackThe call stack is a stack: recursion is LIFO in disguise.1Arrays & Dynamic ArraysA stack is a dynamic array that only pushes and pops at its back.

Leads to→

3Monotonic StackA monotonic stack is a plain stack that pops everything that can no longer be an answer.3Queue (FIFO) & DequeA queue is the stack's twin that removes from the other end: FIFO instead of LIFO.4Backtracking & Pruning: N-QueensUndoing a choice on return is popping it off the stack of choices made so far.6Depth-First Search (DFS)Swap the queue of BFS for a stack and the wave becomes a dive.

1Learn 2Watch 3Play 4Check 5Practice

Learn

The idea, the mechanics and the cost.

01Last in, first out

A stack is an abstract data type: a list of elements where you can reach only one of them, the element at the top. You put new elements on top and take them off the top, so the principle is "Last In, First Out" (LIFO). Think of a pile of plates.

Elements of a stack are not indexed: there is no st[2]. That restriction is the whole point. Because you can only touch the top, every operation is O(1) and the code that uses a stack is easy to reason about.

Stacks are used in every programming language: the compiler uses one for syntax analysis, arithmetic expressions are evaluated with one, and recursion runs on the call stack.

02The STL stack and its five functions

In C++ the stack has its own library, #include <stack>, and you declare it like an ordinary variable: stack<int> st1;, stack<string> st2;, stack<char> st3;, stack<pair<int,int>> st4;, stack<double> st5;.

push(x): add an element. The new element always becomes the top, and the old top becomes the one below it.
pop(): remove the top element; the one below becomes the new top.
top(): access the top element.
size(): the number of elements.
empty(): a boolean, true or false.

Two C++ details: pop() returns nothing, so read top() first if you need the value. And calling top() or pop() on an empty stack is undefined behaviour: check empty() first.

03Tracing the lecture program

The lecture runs this program on an empty stack<int> st: print empty(), push 37, 22 and 29, print size(), pop(), print top(), pop(), print empty(), push 16, print size().

Follow the top. After the three pushes the stack is 37, 22, 29 with 29 on top, so size() prints 3. The first pop() removes 29, the last one in, and top() prints 22. The second pop() removes 22, leaving only 37, so empty() prints false. Finally 16 lands on top of 37 and size() prints 2.

The output is true 3 22 false 2. Run it in the visualizer below and predict each line before you step.

04From infix to postfix

We write (A+B)*(C+D)-E in infix form: the operation sits between its operands, and we need parentheses and priorities. In postfix form the operation comes after its operands: A B + C D + * E -. No parentheses, no priorities. Give the operations priorities: ^ high, * and / medium, + and - low. Scan left to right with a stack of operations:

a) an identifier or number goes straight to the output string;
b) if the stack is empty, or the operation on top has lower priority, push the current one;
c) otherwise the operation evicts every operation of equal or higher priority to the output, stopping at a left parenthesis, then is pushed;
d) a left parenthesis is always pushed;
e) a right parenthesis evicts everything up to the nearest left parenthesis; the pair itself is just deleted.

At the end, pop what is left to the output. (One refinement the slide leaves out: ^ is usually right associative, so 2^3^2 means 2^(3^2). An incoming ^ therefore evicts only operations of strictly higher priority, never another ^.)

Slide 8: the 13 symbols of (A+B)*(C+D)-E, the stack after each one, and what reaches the output.

05Evaluating the postfix form

Postfix is not a goal in itself: an expression in this form is easy to evaluate with the same stack, now holding numbers.

a) a number goes straight onto the stack;
b) for an operation ⊕, take x from the top and y below it, pop both and push y ⊕ x;
c) when all symbols are processed, the number left on the stack is the value.

The lecture example is ((13+7)-3*4)/2+16, in postfix 13 7 + 3 4 * - 2 / 16 +. The stack goes 13 → 13 7 → 20 → 20 3 → 20 3 4 → 20 12 → 8 → 8 2 → 4 → 4 16 → 20.

Mind the order: for - and / it is y - x, the element below minus the top. Both passes touch each symbol once, so the whole calculation is O(n). Type your own expression into the visualizer to watch both stages.

The lecture's C++C++

Slide 5 of the lecture: follow the pushes and pops on st and match every printed line with the output listed at the bottom.

#include<bits/stdc++.h>
using namespace std;
stack <int> st;
main(){
    cout<<boolalpha<<st.empty()<<endl;
    st.push(37);
    st.push(22);
    st.push(29);
    cout<<st.size()<<endl;
    st.pop();
    cout<<st.top()<<endl;
    st.pop();
    cout<<boolalpha<<st.empty()<<endl;
    st.push(16);
    cout<<st.size()<<endl;
}
// პროგრამის შესრულების შედეგი:
// true
// 3
// 22
// false
// 2

Cost at a glance

push / pop / topO(1)

size / emptyO(1)

Infix → postfixO(n)

Evaluate postfixO(n)

Remember

A stack gives access only to its top element: Last In, First Out, with every operation in O(1).
With a stack of operations and the priority rules, an infix expression becomes postfix in a single pass from left to right.
A postfix expression is evaluated with a stack of numbers: each operation pops x and y and pushes y ⊕ x.

Watch

The lecture as a narrated explainer video.

▶

Watch the lecture, animated

The video follows the lecture slide by slide: the same example, the same notation. Use it before or after playing with the visualizer.

▶ Open the video page ▣ Open as presentation

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: The default run is the slide-5 program: predict each cout line before stepping. Then type (A+B)*(C+D)-E or ((13+7)-3*4)/2+16 to watch slides 8 and 9.

Interactive visualizerfocus here, then space ← →

Stack st (LIFO: Last In, First Out)

(empty)

Console output (cout)

Declare an empty stack. Only the TOP element is ever accessible: Last In, First Out.

Pseudocode

 1 stack<int> st; 2 cout << st.empty();  // true 3 st.push(37); 4 st.push(22); 5 st.push(29); 6 cout << st.size();   // 3 7 st.pop(); 8 cout << st.top();    // 22 9 st.pop();10 cout << st.empty();  // false11 st.push(16);12 // your expression: infix → postfix (slide 8)13 for each symbol c of the infix:14   operand → copy it to the output15   "(" → push it16   ")" → pop ops to output until "(", drop both17   op → pop ops with priority ≥ op (for ^ only >), then push op18 pop all remaining ops to the output19 // evaluate the postfix (slide 9)20 for each symbol of the postfix:21   number → st.push(number)22   op ⊕ → x = pop, y = pop, push(y ⊕ x)23 answer = st.top()

1 / 1

Check

Three questions. Pick an answer to see why.

Starting empty: push 5, push 8, pop, push 3, push 9, pop. What does top() return?

Converting A-BC: when arrives, the stack holds -. What happens?

What is the value of the postfix expression 8 2 - 3 *?

Practice

Real problems to lock it in, easiest first.

LeetCodeValid Parentheses beginner↗LeetCodeMin Stack intermediate↗LeetCodeEvaluate Reverse Polish Notation intermediate↗LeetCodeBasic Calculator II intermediate↗