Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Notes › DSA

Stack and Queue

Both store items in a fixed order and allow adding/removing only at the ends — that restriction is what makes them useful.

Stack Queue
Order LIFO — last in, first out FIFO — first in, first out
Add push (top) push / enqueue (back)
Remove pop (top) pop / dequeue (front)
Real life Pile of plates, undo button Ticket line, printer queue
In code Function calls, undo, DFS BFS, task scheduling, buffers

All main operations are O(1).

Stack in C++

#include <stack>
stack<int> st;
st.push(10);
st.push(20);
cout << st.top();   // 20
st.pop();           // removes 20
cout << st.size();  // 1
bool e = st.empty();

Queue and deque in C++

#include <queue>
#include <deque>
queue<int> q;
q.push(1); q.push(2);
cout << q.front() << q.back();   // 1 2
q.pop();                         // removes 1

deque<int> dq;                   // double-ended: add/remove at both ends
dq.push_front(5); dq.push_back(6);
dq.pop_front();   dq.pop_back();

Implementing them yourself

Pattern 1: matching brackets

Push opening brackets; on a closing bracket the top must be its match.

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

Pattern 2: monotonic stack

Keep the stack increasing or decreasing. Each element is pushed and popped once, so the whole pass is O(n).

Next greater element — for each element, the first bigger element to its right:

vector<int> nextGreater(vector<int>& a) {
    int n = a.size();
    vector<int> ans(n, -1);
    stack<int> st;                       // indices, values decreasing
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] < a[i]) {
            ans[st.top()] = a[i];        // a[i] is the next greater for the popped index
            st.pop();
        }
        st.push(i);
    }
    return ans;
}

Used for: stock span, daily temperatures, largest rectangle in a histogram, trapping rain water.

Pattern 3: expression evaluation

Pattern 4: queue for BFS and "level by level"

A queue processes things in the order they were discovered — the basis of BFS in trees and graphs, and of the sliding-window maximum (with a deque).

Pattern 5: min stack

Keep a second stack (or pairs value, currentMin) so getMin() is O(1).

Classic problems

Problem Structure
Valid parentheses stack
Min stack two stacks
Next greater element / daily temperatures monotonic stack
Largest rectangle in histogram monotonic stack
Evaluate reverse Polish notation stack
Implement queue using stacks two stacks
Sliding window maximum monotonic deque
Rotting oranges / shortest path in grid queue (BFS)

Practise them in the Stack & Queue section.

Interview one-liners

More DSA notes