# 5.6 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).

Chapter: Stacks & Queues · ~25 min · easy
URL: https://dsa.fetehadin.com/learn/stl-stack-queue

## Mental 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:

```cpp
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 **d**ouble-**e**nded **que**ue (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.

## C++ code: stl-containers.cpp

```cpp
#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:

```text
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
```

## Complexity

| Case | Cost |
| --- | --- |
| 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) |

Space: O(n)

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

## Videos

- [Introduction to stack](https://youtu.be/F1F2imiOJfk) (mycodeschool): Recap of the stack idea behind std::stack.
- [Introduction to Queues](https://youtu.be/XuCbpw6Bj1U) (mycodeschool): Recap of the queue idea behind std::queue.

## Exam 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()`).

## Quick check

1. How do you remove and keep the top of a `std::stack<int> s`?
   A. `int x = s.pop();`
   B. `int x = s.top(); s.pop();`
   C. `int x = s.front(); s.pop();`
   D. `int x = s.back();`
   Answer: B. `pop()` returns void, so read `top()` first.

2. What does this print?

```cpp
queue<int> q;
q.push(1); q.push(2); q.push(3);
q.pop();
cout << q.front() << q.back();
```
   A. 13
   B. 23
   C. 12
   D. 31
   Answer: B. 1 leaves; the front is 2 and the back is 3.

3. Which container lets you add and remove at both ends in O(1)?
   A. std::stack
   B. std::queue
   C. std::deque
   D. std::vector
   Answer: C. A vector is O(1) only at the back; inserting at its front is O(n).

## Practice

**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 << " ";`

Solution:

`{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`).

**Problems:**

- [Valid Parentheses](https://leetcode.com/problems/valid-parentheses/) (easy). Hint: `stack<char>`; check `empty()` before `top()`.
- [Implement Stack using Queues](https://leetcode.com/problems/implement-stack-using-queues/) (easy). Hint: After pushing x, rotate the queue size − 1 times so x comes to the front.
- [Design Circular Deque](https://leetcode.com/problems/design-circular-deque/) (medium). Hint: Build it on an array with modulo, then compare with std::deque.

## Mastery checklist

- [ ] 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.