5.6 ~25 min easy

std::stack, std::queue & std::deque

The standard library versions you will use in real code and on LeetCode, their method names, and the classic traps (pop returns void, empty checks).

Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.

02Mental model

You have built stacks and queues yourself, which is what the exam asks for. In real C++ code (and on LeetCode) you use the Standard Template Library versions. Same ideas, ready-made.

	`std::stack<T>`	`std::queue<T>`	`std::deque<T>`
add	`push(x)`	`push(x)` (at back)	`push_front(x)`, `push_back(x)`
remove	`pop()`	`pop()` (from front)	`pop_front()`, `pop_back()`
look	`top()`	`front()`, `back()`	`front()`, `back()`, `d[i]`
size	`size()`, `empty()`	`size()`, `empty()`	`size()`, `empty()`

Trap 1: pop() returns nothing

s.pop() removes the top, but returns void. Read first, then pop:

int x = s.top();
s.pop();

Trap 2: empty containers

Calling top(), front() or pop() on an empty container is undefined behaviour. It may crash or print garbage. Check empty() first.

What is a deque?

A double-ended queue (say “deck”): add or remove at both ends in O(1). A stack uses one end; a queue uses both ends, but each for one job. A deque can do both jobs, so it can act as either.

03Visualize

space play · ←→ step · r reset. The highlighted code line follows each step.

Loading visualizer…

push and pop at both ends. A stack uses one end; a queue adds at one end and removes at the other.

04C++ code

Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.

stl-containers.cpp32 lines · C++17

Compiler ExplorerRun OnlineGDB

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

int main() {
    stack<int> s;
    s.push(1); s.push(2); s.push(3);
    cout << "stack top: " << s.top() << ", size: " << s.size() << "\n";
    s.pop();                                  // pop() returns void!
    cout << "after pop, top: " << s.top() << "\n";

    queue<string> q;
    q.push("Abel"); q.push("Hana"); q.push("Liya");
    cout << "queue front: " << q.front() << ", back: " << q.back() << "\n";
    q.pop();
    cout << "after pop, front: " << q.front() << "\n";

    deque<int> d = {3, 6, 9};
    d.push_front(1);
    d.push_back(12);
    cout << "deque: ";
    for (int x : d) cout << x << " ";
    cout << "| d[2] = " << d[2] << "\n";
    d.pop_front(); d.pop_back();
    cout << "after pops: front " << d.front() << ", back " << d.back() << "\n";

    stack<int> e;
    if (!e.empty()) e.pop();                  // always check empty() first
    cout << "empty stack handled safely\n";
}

Expected output

stack top: 3, size: 3
after pop, top: 2
queue front: Abel, back: Liya
after pop, front: Hana
deque: 1 3 6 9 12 | d[2] = 6
after pops: front 3, back 9
empty stack handled safely

05Complexity

stack push / pop / top	O(1)
queue push / pop / front / back	O(1)
deque push/pop at either end	O(1)
deque d[i]	O(1)
Extra space	O(n)

std::stack and std::queue are adapters: they wrap a std::deque by default and only expose the allowed operations.

06Watch

Introduction to stack

mycodeschool · 8:26

Why this one: Recap of the stack idea behind std::stack.

Watched

Introduction to Queues

mycodeschool · 9:18

Why this one: Recap of the queue idea behind std::queue.

Watched

Original class slides (Python, by the course's lecture authors):Stacks, Queues and Monotonicity

07Exam lens

Likely questions

Write C++ that pushes 1, 2, 3 onto a std::stack and prints them in pop order.
What does s.pop() return in std::stack?
What is a deque? How is it different from a queue?

Common mistakes

Writing int x = s.pop();. It does not compile; pop() returns void. Read top() first.
Calling top() / front() / pop() on an empty container (undefined behaviour). Check empty().
Using q.top() on a queue (it is front()), or s.front() on a stack (it is top()).

08Quick check

1.How do you remove and keep the top of a std::stack<int> s?

2.What does this print?

queue<int> q;
q.push(1); q.push(2); q.push(3);
q.pop();
cout << q.front() << q.back();

3.Which container lets you add and remove at both ends in O(1)?

09Practice

🟢 Trace by hand

Predict the output: deque<int> d = {5}; d.push_front(3); d.push_back(8); d.push_front(1); d.pop_back(); for (int x : d) cout << x << " ";

Show answer

{5} → {3,5} → {3,5,8} → {1,3,5,8} → {1,3,5}. Prints 1 3 5.

🟡 Implement it

Solve the bracket checker and the "recent calls" counter again, this time using std::stack and std::queue.

Hint

Same logic as your own classes. Only the method names change (top, front, empty).

🔴 Solve problems

Valid Parentheses easyleetcode.com
Hint
stack<char>; check empty() before top().
Implement Stack using Queues easyleetcode.com
Hint
After pushing x, rotate the queue size − 1 times so x comes to the front.
Design Circular Deque mediumleetcode.com
Hint
Build it on an array with modulo, then compare with std::deque.

10Mastery checklist

Tick these honestly. When every box is ticked, the topic is marked complete.

I know the method names of std::stack, std::queue and std::deque.
I always read top()/front() before pop(), and check empty() first.
I can explain what a deque is.

0/3 ticked

My notes

View as Markdown · Chapter cheat sheet