SyntaxPilot
Courses/C++ Coding Questions/Lesson 16
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

C++ Coding Questions · Lesson 16 of 30

Stack questions

balanced brackets (empty-stack trap)next greater element (monotonic stack)evaluate a postfix expression

These are the notes for C++ Coding Questions, episode 16, placement practice for people who finished the SyntaxPilot C++ course. One data structure, three classic questions: balanced brackets (why counting fails, and the empty-stack crash), the next greater element with a monotonic stack (from O(n²) to O(n), and a default of 0 that should be -1), and evaluating a postfix expression (the first pop is the right-hand number, and multi-digit numbers need whole tokens).

Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.

Every program was compiled with g++ -Wall -O2 -std=c++17 main.cpp -o main (g++ 13.3, Linux x86-64), the SyntaxPilot compiler's C++ command with warnings on, and every output below is real. The compiler stops a program that runs too long (Time Limit Exceeded, TLE), like an online judge.

Real-life pictures

In real life In C++
A pile of plates: you only touch the top one a stack: push, top, pop, last in first out
Packing a suitcase: open the suitcase, a bag, a pouch; zip the pouch first brackets: the newest open bracket must close first
Zipping something you never opened a closer when the stack is empty
People in a line for a photo, each looking right for the first taller person the next greater element
People still waiting stand on a pile; a tall person arrives and answers everyone shorter on top a monotonic stack of indexes
A shopkeeper's pile of chits: an operator chit takes the top two, the top one is the right-hand number postfix evaluation: pop b first, then a

A stack in one minute: std::stack

A stack is a container where you only touch the top. The last value pushed is the first one out: LIFO (last in, first out).

#include <stack>
stack<char> st;
st.push('(');      // put on top
st.top();          // read the top (does not remove it)
st.pop();          // remove the top (returns nothing)
st.empty();        // true if there is nothing in it
st.size();         // how many values
  • push, top, pop, empty and size are all O(1).
  • pop() returns nothing: read top() first, then pop().
  • top() or pop() on an empty stack is undefined behaviour (UB): the C++ standard says nothing about what happens. In the video it crashed; on another machine it could silently read garbage.

Q1: Balanced brackets

Problem. For each word made of ( ) [ ] { }, print YES if every bracket is closed by the same kind, in the right order, else NO.

Input Output Why
{[()]} YES closed in reverse order
()[]{} YES side by side
([)] NO ) closes while [ is still open
(( NO opens left over
()) NO a closer with nothing open

Think out loud. Three edge cases: the wrong order, opens left over at the end, and a closer with nothing open.

The obvious attempt: count each kind

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

bool balanced(const string& s) {
    int round = 0, square = 0, curly = 0;
    for (char c : s) {
        if (c == '(') round++;
        if (c == ')') round--;
        if (c == '[') square++;
        if (c == ']') square--;
        if (c == '{') curly++;
        if (c == '}') curly--;
        if (round < 0 || square < 0 || curly < 0) return false;
    }
    return round == 0 && square == 0 && curly == 0;
}

int main() {
    string s;
    while (cin >> s) cout << s << ": " << (balanced(s) ? "YES" : "NO") << "\n";
    return 0;
}

On {[()]} ()[]{}:

{[()]}: YES
()[]{}: YES

On {[()]} ([)]:

{[()]}: YES
([)]: YES

([)] says YES. Each counter goes up once and down once, so all three end at zero, but the round bracket was closed while the square one inside it was still open. Counts can't see the order.

Why a stack

When a closer comes, it must match the newest bracket that is still open. "Remember things in order and always look at the newest" is exactly a stack: push every open bracket; on a closer, top() must be its partner, then pop().

Attempt: a stack, without the empty check

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

bool balanced(const string& s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') st.push(c);
        else {
            char open = st.top();
            st.pop();
            if ((c == ')' && open != '(') || (c == ']' && open != '[') ||
                (c == '}' && open != '{')) return false;
        }
    }
    return st.empty();
}

int main() {
    string s;
    while (cin >> s) cout << s << ": " << (balanced(s) ? "YES" : "NO") << "\n";
    return 0;
}

On {[()]} ([)] it is right:

{[()]}: YES
([)]: NO

On {[()]} ([)] (( ()) the compiler shows the lines printed so far and then:

{[()]}: YES
([)]: NO
((: NO
Runtime Error (SIGSEGV)

SIGSEGV (segmentation fault) means the program touched memory it doesn't own. In ()), the first ) pops the (; the second ) calls st.top() on an empty stack.

Fix: check st.empty() before top()

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

bool balanced(const string& s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') st.push(c);
        else {
            if (st.empty()) return false;   // a closer with nothing open
            char open = st.top();
            st.pop();
            if ((c == ')' && open != '(') || (c == ']' && open != '[') ||
                (c == '}' && open != '{')) return false;
        }
    }
    return st.empty();
}

int main() {
    string s;
    while (cin >> s) cout << s << ": " << (balanced(s) ? "YES" : "NO") << "\n";
    return 0;
}
{[()]}: YES
([)]: NO
((: NO
()): NO

The last line, return st.empty();, catches opens left over (((). O(n) time (each bracket pushed and popped at most once), O(n) space (a word of only open brackets).

Q2: Next greater element

Problem. For each number, print the first larger number to its right, or -1 if there is none.

Input Output
4 5 2 25 5 25 25 -1
13 7 6 12 10 15 3 15 12 12 15 15 -1 -1

Think out loud. The last number always gets -1; falling numbers get -1 everywhere. Big test: 500,000 falling prices (when n is 0, the program builds 500000 499999 ... 1).

The obvious attempt: scan to the right

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

vector<int> nextGreater(const vector<int>& a) {
    int n = a.size();
    vector<int> ans(n, -1);
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (a[j] > a[i]) { ans[i] = a[j]; break; }
    return ans;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    if (n == 0) {                        // test: 500,000 falling prices
        n = 500000;
        a.resize(n);
        for (int i = 0; i < n; i++) a[i] = n - i;
    }
    vector<int> ans = nextGreater(a);
    if (n > 20) { cout << "last: " << ans[n - 1] << "\n"; return 0; }
    for (int x : ans) cout << x << " ";
    cout << "\n";
    return 0;
}

On 4 5 2 25:

5 25 25 -1 

On the big test:

Time Limit Exceeded

Nobody finds a larger number, so every scan runs to the end: about n²/2 = 125,000,000,000 comparisons. Each scan starts from scratch and forgets what the earlier scans saw.

Why the pile works: a monotonic stack

Keep the indexes still waiting for an answer on a stack. When a[i] arrives, it is the answer for every waiting index whose value is smaller: pop them and fill in ans. Then push i.

13 7 6 12:  stack 13 7 6  →  12 arrives: 6 gets 12, 7 gets 12, 13 keeps waiting
            stack 13 12

The values on the stack always fall from bottom to top: that's a monotonic stack (a stack kept in sorted order). We store indexes, not values, so we know whose answer to fill in. Each index is pushed once and popped at most once: O(n).

Attempt: the monotonic stack with vector<int> ans(n)

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

vector<int> nextGreater(const vector<int>& a) {
    int n = a.size();
    vector<int> ans(n);
    stack<int> st;                       // indexes still waiting
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] < a[i]) {
            ans[st.top()] = a[i];        // a[i] answers everyone smaller
            st.pop();
        }
        st.push(i);
    }
    return ans;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    if (n == 0) {                        // test: 500,000 falling prices
        n = 500000;
        a.resize(n);
        for (int i = 0; i < n; i++) a[i] = n - i;
    }
    vector<int> ans = nextGreater(a);
    if (n > 20) { cout << "last: " << ans[n - 1] << "\n"; return 0; }
    for (int x : ans) cout << x << " ";
    cout << "\n";
    return 0;
}
5 25 25 0 

The last answer is 0, not -1. vector<int> ans(n) fills every slot with 0; indexes left on the stack at the end are never answered, so they keep the 0.

Fix: vector<int> ans(n, -1)

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

vector<int> nextGreater(const vector<int>& a) {
    int n = a.size();
    vector<int> ans(n, -1);              // nobody answered yet
    stack<int> st;                       // indexes still waiting
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] < a[i]) {
            ans[st.top()] = a[i];        // a[i] answers everyone smaller
            st.pop();
        }
        st.push(i);
    }
    return ans;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    if (n == 0) {                        // test: 500,000 falling prices
        n = 500000;
        a.resize(n);
        for (int i = 0; i < n; i++) a[i] = n - i;
    }
    vector<int> ans = nextGreater(a);
    if (n > 20) { cout << "last: " << ans[n - 1] << "\n"; return 0; }
    for (int x : ans) cout << x << " ";
    cout << "\n";
    return 0;
}

On 13 7 6 12 10 15 3:

15 12 12 15 15 -1 -1 

On the big test (500,000 falling prices), instantly:

last: -1

O(n) time, O(n) space (the stack and the answers).

Q3: Evaluate a postfix expression

Postfix (also called Reverse Polish notation) writes the operator after its two numbers: 2 3 + means 2 + 3. It needs no brackets: 2 3 1 * + 9 - means (2 + 3 × 1) − 9. A token is one piece of the expression: a number or an operator.

Problem. Each line is a postfix expression with tokens separated by spaces. Print its value.

Input Output
2 3 + 5
2 3 1 * + 9 - -4
10 2 / 5
100 20 30 + - 50

Think out loud. Numbers go on a stack; an operator takes the top two, combines them, and pushes the result. Edge cases: - and / care about the order; numbers can have more than one digit.

The obvious attempt: pop a, then b

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

long long evalPostfix(const string& e) {
    stack<long long> st;
    for (char c : e) {
        if (c == ' ') continue;
        if (isdigit(c)) { st.push(c - '0'); continue; }
        long long a = st.top(); st.pop();
        long long b = st.top(); st.pop();
        if (c == '+') st.push(a + b);
        if (c == '-') st.push(a - b);
        if (c == '*') st.push(a * b);
        if (c == '/') st.push(a / b);
    }
    return st.top();
}

int main() {
    string line;
    while (getline(cin, line)) cout << line << " = " << evalPostfix(line) << "\n";
    return 0;
}
2 3 + = 5
2 3 1 * + 9 - = 4

4, but the answer is -4. At the -, the stack is 5 9 with 9 on top. We popped 9 into a, 5 into b, and computed 9 − 5.

Why: the first pop is the RIGHT operand

9 was pushed last, so it comes out first: it is the right-hand side. + and * don't care about the order, so they hid the bug; - and / do. Pop b (right) first, then a (left), and push a - b.

Attempt: the right order, still char by char

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

long long evalPostfix(const string& e) {
    stack<long long> st;
    for (char c : e) {
        if (c == ' ') continue;
        if (isdigit(c)) { st.push(c - '0'); continue; }
        long long b = st.top(); st.pop();    // the TOP is the right side
        long long a = st.top(); st.pop();
        if (c == '+') st.push(a + b);
        if (c == '-') st.push(a - b);
        if (c == '*') st.push(a * b);
        if (c == '/') st.push(a / b);
    }
    return st.top();
}

int main() {
    string line;
    while (getline(cin, line)) cout << line << " = " << evalPostfix(line) << "\n";
    return 0;
}
2 3 + = 5
2 3 1 * + 9 - = -4
10 2 / = 0

10 2 / says 0. Character by character, 10 became two numbers, 1 and 0; then / computed 0 / 2.

Fix: read whole tokens with stringstream

A stringstream (from <sstream>) reads a string the way cin reads the keyboard: in >> tok gives one space-separated token at a time. stoll (string to long long) turns "10" into 10.

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

long long evalPostfix(const string& e) {
    stack<long long> st;
    stringstream in(e);
    string tok;
    while (in >> tok) {                  // one whole token at a time
        if (isdigit(tok[0])) { st.push(stoll(tok)); continue; }
        long long b = st.top(); st.pop();    // the TOP is the right side
        long long a = st.top(); st.pop();
        if (tok == "+") st.push(a + b);
        if (tok == "-") st.push(a - b);
        if (tok == "*") st.push(a * b);
        if (tok == "/") st.push(a / b);
    }
    return st.top();
}

int main() {
    string line;
    while (getline(cin, line)) cout << line << " = " << evalPostfix(line) << "\n";
    return 0;
}
2 3 + = 5
2 3 1 * + 9 - = -4
10 2 / = 5
100 20 30 + - = 50

O(n) time (each token is pushed or popped a fixed number of times), O(n) space. A real calculator would also reject division by zero and a malformed expression (too few numbers on the stack); see the practice questions.

When is a stack the right tool?

  • When the newest unfinished thing is the one that matters next.
  • Brackets: the newest open bracket. Next greater: the newest index still waiting. Postfix: the two newest numbers.
  • Everyday stacks: undo in an editor, the browser's back button, the call stack of your program's functions.
  • Before every top() or pop(), ask: can the stack be empty here?
Question What the stack holds Pops when
balanced brackets open brackets a closer arrives
next greater indexes still waiting a larger value arrives
postfix numbers an operator arrives

Complexity summary

Program Time Extra space
brackets, counters O(n) but wrong O(1)
brackets, stack O(n) O(n)
next greater, scan right O(n²): TLE for 500,000 O(1)
next greater, monotonic stack O(n) O(n)
postfix, stack of numbers O(n) O(n)

Common mistakes (and the real results)

Mistake What you see Why Fix
counting each bracket type ([)]: YES counts can't see the order a stack of open brackets
st.top() with no check Runtime Error (SIGSEGV) on ()) top() of an empty stack (UB) if (st.empty()) return false;
forgetting return st.empty(); ((: YES opens left over the stack must end empty
scanning right for every element Time Limit Exceeded O(n²) a monotonic stack
vector<int> ans(n) 5 25 25 0 unanswered slots keep 0 vector<int> ans(n, -1)
pushing values instead of indexes can't tell whose answer to fill values aren't positions push i, read a[st.top()]
pop a first, then b 2 3 1 * + 9 - = 4 the top is the right side pop b first, then a
reading char by char 10 2 / = 0 10 read as 1 and 0 stringstream + stoll
st.pop() used as a value error: void value not ignored as it ought to be pop() returns void x = st.top(); st.pop();

The last one is a compile error; for example int x = st.pop(); gives:

main.cpp: In function 'int main()':
main.cpp:7:19: error: void value not ignored as it ought to be
    7 |     int x = st.pop();
      |             ~~~~~~^~

Your turn: a stack that knows its minimum (solution)

Problem. Commands push x, pop, min. Every operation, min included, in O(1).

Idea. A second stack holds, at each level, the minimum of everything at or below that level. Push: mins.push(min(x, mins.top())). Pop: pop both.

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

struct MinStack {
    stack<int> vals, mins;               // mins.top() = minimum of vals
    void push(int x) {
        vals.push(x);
        mins.push(mins.empty() ? x : min(x, mins.top()));
    }
    void pop() { vals.pop(); mins.pop(); }
    int getMin() const { return mins.top(); }
    bool empty() const { return vals.empty(); }
};

int main() {
    MinStack s;
    string op;
    while (cin >> op) {
        if (op == "push") { int x; cin >> x; s.push(x); }
        else if (op == "pop") { if (!s.empty()) s.pop(); }
        else cout << (s.empty() ? string("empty") : to_string(s.getMin())) << "\n";
    }
    return 0;
}

Input push 5 push 3 push 7 min pop pop min pop min:

3
5
empty

Practice questions (with solutions)

1. Previous smaller element. For each number, print the nearest smaller number to its left, or -1.

Solution

A monotonic stack again, read left to right: pop everything that is not smaller than a[i]; whatever is left on top is the answer; then push a[i].

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    stack<int> st;                       // values, rising from bottom to top
    for (int x : a) {
        while (!st.empty() && st.top() >= x) st.pop();
        cout << (st.empty() ? -1 : st.top()) << " ";
        st.push(x);
    }
    cout << "\n";
    return 0;
}

Input 6 / 4 5 2 10 8 9:

-1 4 -1 2 2 8 

2. Stock span. For each day, how many days in a row ending today had a price at most today's price?

Solution

Keep indexes of days with a higher price on a stack. Pop the days with price ≤ today; the span is i − (index on top), or i + 1 if the stack is empty.

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

int main() {
    int n;
    cin >> n;
    vector<int> p(n);
    for (int& x : p) cin >> x;
    stack<int> st;                       // indexes of higher prices
    for (int i = 0; i < n; i++) {
        while (!st.empty() && p[st.top()] <= p[i]) st.pop();
        cout << (st.empty() ? i + 1 : i - st.top()) << " ";
        st.push(i);
    }
    cout << "\n";
    return 0;
}

Input 7 / 100 80 60 70 60 75 85:

1 1 1 2 1 4 6 

3. Reverse a string with a stack.

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

int main() {
    string s;
    while (cin >> s) {
        stack<char> st;
        for (char c : s) st.push(c);
        string r;
        while (!st.empty()) { r += st.top(); st.pop(); }
        cout << r << "\n";
    }
    return 0;
}

Input stack syntaxpilot:

kcats
tolipxatnys

(std::reverse does the same in place; the stack shows LIFO at work.)

4. A safe postfix calculator. Print error for division by zero or a malformed expression.

Solution

Check that two numbers are on the stack before every operator, that b != 0 before /, and that exactly one number is left at the end.

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

bool evalSafe(const string& e, long long& result) {
    stack<long long> st;
    stringstream in(e);
    string tok;
    while (in >> tok) {
        if (isdigit(tok[0])) { st.push(stoll(tok)); continue; }
        if (st.size() < 2) return false;     // not enough numbers
        long long b = st.top(); st.pop();
        long long a = st.top(); st.pop();
        if (tok == "+") st.push(a + b);
        else if (tok == "-") st.push(a - b);
        else if (tok == "*") st.push(a * b);
        else if (tok == "/") { if (b == 0) return false; st.push(a / b); }
        else return false;                   // unknown token
    }
    if (st.size() != 1) return false;
    result = st.top();
    return true;
}

int main() {
    string line;
    while (getline(cin, line)) {
        long long r;
        if (evalSafe(line, r)) cout << line << " = " << r << "\n";
        else cout << line << " = error\n";
    }
    return 0;
}
2 3 1 * + 9 - = -4
4 0 / = error
1 + = error
1 2 = error

Mini project: an undo button for a text box

Commands: type <word> adds a word, undo removes the last change, show prints the text. Every change goes on a stack; undo pops it. This is how editors implement undo.

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

int main() {
    string text, cmd;
    stack<string> history;               // the text before each change
    while (cin >> cmd) {
        if (cmd == "type") {
            string w;
            cin >> w;
            history.push(text);
            text += (text.empty() ? "" : " ") + w;
        } else if (cmd == "undo") {
            if (history.empty()) { cout << "(nothing to undo)\n"; continue; }
            text = history.top();
            history.pop();
        } else cout << "[" << text << "]\n";
    }
    return 0;
}
[hello stack world]
[hello stack]
[]
(nothing to undo)

Quick quiz

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

int main() {
    stack<int> st;
    for (int x : {3, 1, 4, 1, 5}) {
        while (!st.empty() && st.top() > x) st.pop();
        st.push(x);
    }
    cout << st.size() << " " << st.top() << "\n";
    return 0;
}

(A) 3 5 (B) 5 5 (C) 2 5 (D) 3 4

Answer

(A) 3 5. 3 → [3]; 1 pops 3 → [1]; 4 → [1 4]; 1 pops 4 → [1 1]; 5 → [1 1 5]. Size 3, top 5.

3 5

Interview questions

  1. What is a stack, and what are its operations' costs? A LIFO container: push, pop, top, empty, size, all O(1).
  2. Why can't counters check brackets? They lose the order: ([)] has balanced counts but closes in the wrong order.
  3. What happens on top() of an empty std::stack? Undefined behaviour: a crash, garbage, or anything. Always check empty() first.
  4. What is a monotonic stack? A stack kept in sorted order by popping elements that break the order before each push; used for next/previous greater or smaller.
  5. Why is the monotonic stack O(n) with a while inside a for? Each index is pushed once and popped at most once: at most 2n operations in total.
  6. Why store indexes on the stack? To know which answer slot to fill, and to compute distances (stock span).
  7. In postfix, which operand is popped first? The right one: a b - pops b, then a, computes a - b.
  8. Why is postfix easy for computers? No brackets and no precedence rules: one left-to-right pass with a stack.
  9. What does std::stack use underneath? A std::deque by default; stack<int, vector<int>> uses a vector.
  10. How do you make a min-stack? A second stack holding the running minimum at each level.

Glossary

Term Meaning Example
Stack A container where you only add, read and remove at the top a pile of plates
LIFO Last in, first out the last plate on is the first off
push / pop / top Add on top / remove the top / read the top st.push('(')
std::stack The C++ stack adaptor, from <stack> stack<char> st;
Empty stack A stack with no values; top()/pop() on it is UB st.empty() is true
Undefined behaviour (UB) Code the C++ standard gives no meaning to: anything may happen top() of an empty stack
SIGSEGV Segmentation fault: the program touched memory it doesn't own Runtime Error (SIGSEGV)
Balanced brackets Every bracket closed by the same kind in reverse order {[()]}
Next greater element The first larger value to the right 5 for 4 in 4 5 2 25
Monotonic stack A stack whose values stay sorted, by popping before each push values fall from bottom to top
Postfix (Reverse Polish) Operators written after their operands 2 3 + = 5
Operand A value an operator works on 2 and 3 in 2 3 +
Token One piece of an expression: a number or an operator 10, /
stringstream A stream that reads from or writes to a string, from <sstream> stringstream in(e); in >> tok;
stoll String to long long stoll("10") is 10
Time Limit Exceeded (TLE) The judge stopped a program that ran too long O(n²) on 500,000 numbers

Summary

  • Stack: only the top; push, top, pop, empty are O(1); pop() returns nothing; never top()/pop() an empty stack.
  • Balanced brackets: push opens; on a closer the stack must be non-empty and its top the partner; end with an empty stack. O(n).
  • Next greater element: a monotonic stack of indexes; a larger value answers everyone smaller on top; default -1. O(n).
  • Postfix: numbers on a stack; an operator pops b (right) then a (left); read whole tokens with stringstream. O(n).

Next episode: Queue and deque questions: a queue using two stacks (amortised O(1)), the sliding window maximum with a deque, and the first non-repeating character in a stream.