These are the notes for C++ Coding Questions, episode 17, placement practice for people who finished the SyntaxPilot C++ course. The stack's partner, the queue, and the deque that works at both ends, on three classic questions: a queue built from two stacks (and why it is amortised O(1)), the sliding window maximum with a deque of indexes (O(n·k) to O(n)), and the first non-repeating character in a stream (and an if that must be a while).
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 ticket line: join at the back, leave from the front | a queue: FIFO, push, front, pop |
| A line you can join or leave at both ends | a deque: push_front/back, pop_front/back |
| A teacher's in-tray (newest sheet on top), flipped once into an out-tray (oldest on top) | a queue from two stacks |
| Never flip again while the out-tray still has sheets | move only when out.empty() |
| The hottest day in every 3 days: a hotter newcomer sends cooler earlier days home for good | a monotonic deque: pop from the back |
| The hottest day slides out of the 3 days | pop from the front when dq.front() <= i - k |
| A mela lucky draw: the earliest name entered exactly once wins; names entered twice are out | first non-repeating character: a queue of candidates |
| Several disqualified names at the front: skip all of them | while, not if |
Queue and deque in one minute
A queue is first in, first out (FIFO): values join at the back and leave from the front.
#include <queue>
queue<int> q;
q.push(5); // join at the back
q.front(); // read the first one
q.pop(); // remove the first one (returns nothing)
q.empty(); q.size();
A deque (double-ended queue, said "deck") lets you add and remove at both ends:
#include <deque>
deque<int> dq;
dq.push_back(1); dq.push_front(2); dq.pop_back(); dq.pop_front();
dq.front(); dq.back(); dq[i]; // it also has indexing
All of these are O(1). Like the stack, front()/pop() on an empty queue is undefined behaviour.
Q1: A queue using two stacks
Problem. Implement a queue with only two stacks. Input: the number of operations, then push x or pop. Print every popped value.
| Operations | Output |
|---|---|
push 1 push 2 push 3 pop pop pop |
1 2 3 |
push 1 push 2 pop push 3 pop pop |
1 2 3 |
Think out loud. One stack (in) takes the pushes; reversing a stack into another one puts the oldest value on top. Edge cases: pushes in between pops. Big test (0 operations): 200,000 pushes then 200,000 pops, printing the sum.
The obvious attempt: move everything there and back on every pop
#include <iostream>
#include <string>
#include <stack>
using namespace std;
struct TwoStackQueue {
stack<int> in, out;
void push(int x) { in.push(x); }
int pop() {
while (!in.empty()) { out.push(in.top()); in.pop(); }
int front = out.top(); out.pop();
while (!out.empty()) { in.push(out.top()); out.pop(); }
return front;
}
};
int main() {
TwoStackQueue q;
int ops;
cin >> ops;
if (ops == 0) { // test: 200,000 pushes, then 200,000 pops
long long sum = 0;
for (int i = 1; i <= 200000; i++) q.push(i);
for (int i = 1; i <= 200000; i++) sum += q.pop();
cout << "sum = " << sum << "\n";
return 0;
}
while (ops--) {
string op;
cin >> op;
if (op == "push") { int x; cin >> x; q.push(x); }
else cout << q.pop() << " ";
}
cout << "\n";
return 0;
}
1 2 3
On the big test:
Time Limit Exceeded
Every pop moves the whole queue twice: up to 200,000 values × 2, for 200,000 pops, about 40,000,000,000 moves.
Attempt: don't move back, but flip on every pop
#include <iostream>
#include <string>
#include <stack>
using namespace std;
struct TwoStackQueue {
stack<int> in, out;
void push(int x) { in.push(x); }
int pop() {
while (!in.empty()) { out.push(in.top()); in.pop(); }
int front = out.top(); out.pop();
return front;
}
};
int main() {
TwoStackQueue q;
int ops;
cin >> ops;
if (ops == 0) { // test: 200,000 pushes, then 200,000 pops
long long sum = 0;
for (int i = 1; i <= 200000; i++) q.push(i);
for (int i = 1; i <= 200000; i++) sum += q.pop();
cout << "sum = " << sum << "\n";
return 0;
}
while (ops--) {
string op;
cin >> op;
if (op == "push") { int x; cin >> x; q.push(x); }
else cout << q.pop() << " ";
}
cout << "\n";
return 0;
}
1 2 3
1 3 2
1 3 2. After popping 1, the out stack still holds 2. Then 3 is pushed, and the next pop flips again: 3 lands on top of the older 2.
push 1, 2 in: 1 2 pop → flip → out: 2 1 → pop 1 → out: 2
push 3 in: 3 pop → flip → out: 2 3 (3 on top of the older 2!)
Fix: flip only when out is empty
#include <iostream>
#include <string>
#include <stack>
using namespace std;
struct TwoStackQueue {
stack<int> in, out;
void push(int x) { in.push(x); }
int pop() {
if (out.empty()) // flip only when out is empty
while (!in.empty()) { out.push(in.top()); in.pop(); }
int front = out.top(); out.pop();
return front;
}
};
int main() {
TwoStackQueue q;
int ops;
cin >> ops;
if (ops == 0) { // test: 200,000 pushes, then 200,000 pops
long long sum = 0;
for (int i = 1; i <= 200000; i++) q.push(i);
for (int i = 1; i <= 200000; i++) sum += q.pop();
cout << "sum = " << sum << "\n";
return 0;
}
while (ops--) {
string op;
cin >> op;
if (op == "push") { int x; cin >> x; q.push(x); }
else cout << q.pop() << " ";
}
cout << "\n";
return 0;
}
1 2 3
The big test, instantly (1 + 2 + ... + 200,000):
sum = 20000100000
Amortised O(1). One pop can still be slow (when it flips n values), but every value is pushed into in once, moved once, and popped from out once: 3 operations per value. Spread over all operations, each costs O(1) on average. That's what amortised means: the total cost divided by the number of operations. Space O(n).
Q2: Sliding window maximum
Problem. Given n numbers and k, print the maximum of every window of k numbers in a row.
| Input | Output |
|---|---|
1 3 -1 -3 5 3 6 7, k = 3 |
3 3 5 5 6 7 |
9 1 2 3, k = 2 |
9 2 3 |
Think out loud. There are n − k + 1 windows. Edge cases: the maximum at the very start, k = 1. Big test (0 0): 1,000,000 numbers i % 1000, k = 500,000.
The obvious attempt: rescan every window
#include <iostream>
#include <vector>
using namespace std;
vector<int> windowMax(const vector<int>& a, int k) {
vector<int> m;
for (int i = 0; i + k <= (int)a.size(); i++) {
int best = a[i];
for (int j = i; j < i + k; j++) best = max(best, a[j]);
m.push_back(best);
}
return m;
}
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int& x : a) cin >> x;
if (n == 0) { // test: 1,000,000 numbers, k = 500,000
n = 1000000; k = 500000;
a.resize(n);
for (int i = 0; i < n; i++) a[i] = i % 1000;
}
vector<int> m = windowMax(a, k);
if (n > 20) { cout << m.size() << " windows, last max " << m.back() << "\n"; return 0; }
for (int x : m) cout << x << " ";
cout << "\n";
return 0;
}
3 3 5 5 6 7
On the big test:
Time Limit Exceeded
500,001 windows × 500,000 numbers ≈ 250,000,000,000 looks. Neighbouring windows share k − 1 numbers, and we scanned them all again.
The idea: a deque of indexes, biggest first
When a new value arrives, every earlier value that is not bigger can never be a window maximum again: the newcomer is at least as big and stays in the window longer. So pop them from the back, then push the new index. The values in the deque then fall from front to back, so the front is the maximum. We store indexes so we can tell how old the front is.
1 3 -1 (k = 3): 1 → [1] 3 → 1 goes home → [3] -1 → [3 -1] max 3
-3: [3 -1 -3] max 3
5: -3, -1, 3 go home → [5] max 5
Attempt: never drop the front
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
vector<int> windowMax(const vector<int>& a, int k) {
vector<int> m;
deque<int> dq; // indexes, their values falling
for (int i = 0; i < (int)a.size(); i++) {
while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
dq.push_back(i);
if (i >= k - 1) m.push_back(a[dq.front()]);
}
return m;
}
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int& x : a) cin >> x;
if (n == 0) { // test: 1,000,000 numbers, k = 500,000
n = 1000000; k = 500000;
a.resize(n);
for (int i = 0; i < n; i++) a[i] = i % 1000;
}
vector<int> m = windowMax(a, k);
if (n > 20) { cout << m.size() << " windows, last max " << m.back() << "\n"; return 0; }
for (int x : m) cout << x << " ";
cout << "\n";
return 0;
}
3 3 5 5 6 7
Looks right. But:
9 9 9
9 9 9: the window 2 3 (indexes 2 and 3) has no 9. Nothing bigger than 9 came, so nothing pushed it out from the back, and nobody checked its age. The first test passed only by luck.
Fix: drop the front once it slides out
The window ending at i is i − k + 1 .. i, so a front index <= i − k is outside it.
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
vector<int> windowMax(const vector<int>& a, int k) {
vector<int> m;
deque<int> dq; // indexes, their values falling
for (int i = 0; i < (int)a.size(); i++) {
while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
dq.push_back(i);
if (dq.front() <= i - k) dq.pop_front(); // slid out
if (i >= k - 1) m.push_back(a[dq.front()]);
}
return m;
}
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int& x : a) cin >> x;
if (n == 0) { // test: 1,000,000 numbers, k = 500,000
n = 1000000; k = 500000;
a.resize(n);
for (int i = 0; i < n; i++) a[i] = i % 1000;
}
vector<int> m = windowMax(a, k);
if (n > 20) { cout << m.size() << " windows, last max " << m.back() << "\n"; return 0; }
for (int x : m) cout << x << " ";
cout << "\n";
return 0;
}
9 2 3
3 3 5 5 6 7
The big test, instantly:
500001 windows, last max 999
O(n) time: each index has one push_back and at most one pop (from the back or the front). O(k) space: the deque never holds more than one window.
Q3: First non-repeating character in a stream
Problem. A stream of characters a–z arrives one by one. After each character, print the first character seen exactly once so far, or # if there is none.
| Stream | Output |
|---|---|
aabc |
a#bb |
zz |
z# |
abba |
aaa# |
Think out loud. Edge cases: nobody left (#), two repeated characters at the front at once. Big test: the word big builds 300,000 as.
The obvious attempt: rescan the stream after every character
#include <iostream>
#include <string>
using namespace std;
string firstUnique(const string& s) {
string ans;
int cnt[26] = {};
for (int i = 0; i < (int)s.size(); i++) {
cnt[s[i] - 'a']++;
char first = '#';
for (int j = 0; j <= i; j++) // rescan the stream so far
if (cnt[s[j] - 'a'] == 1) { first = s[j]; break; }
ans += first;
}
return ans;
}
int main() {
string s;
while (cin >> s) {
if (s == "big") s = string(300000, 'a'); // test: 300,000 a's
string ans = firstUnique(s);
if (s.size() > 20) cout << ans.size() << " answers, last " << ans.back() << "\n";
else cout << s << ": " << ans << "\n";
}
return 0;
}
aabc: a#bb
zz: z#
On big:
Time Limit Exceeded
After each a, the scan walks the whole stream and finds nothing: about n²/2 = 45,000,000,000 steps.
The idea: a queue of candidates
- A character seen for the first time joins the back of a queue.
- The front is the earliest candidate. If its count is now more than 1, it is out: pop it.
- The answer is
q.front(), or#if the queue is empty. - A character that is out never comes back, so each character is pushed once and popped at most once.
Attempt: if instead of while
#include <iostream>
#include <string>
#include <queue>
using namespace std;
string firstUnique(const string& s) {
string ans;
int cnt[26] = {};
queue<char> q; // candidates, in arrival order
for (char c : s) {
if (++cnt[c - 'a'] == 1) q.push(c);
if (!q.empty() && cnt[q.front() - 'a'] > 1) q.pop();
ans += q.empty() ? '#' : q.front();
}
return ans;
}
int main() {
string s;
while (cin >> s) {
if (s == "big") s = string(300000, 'a'); // test: 300,000 a's
string ans = firstUnique(s);
if (s.size() > 20) cout << ans.size() << " answers, last " << ans.back() << "\n";
else cout << s << ": " << ans << "\n";
}
return 0;
}
aabc: a#bb
zz: z#
abba: aaab
abba ends with b, but b was entered twice. At the last a, the queue is a b and both counts are 2. The if pops a and stops; the new front b is out too. (When the second b came, b was not at the front, so nobody popped it then.)
Fix: while
#include <iostream>
#include <string>
#include <queue>
using namespace std;
string firstUnique(const string& s) {
string ans;
int cnt[26] = {};
queue<char> q; // candidates, in arrival order
for (char c : s) {
if (++cnt[c - 'a'] == 1) q.push(c);
while (!q.empty() && cnt[q.front() - 'a'] > 1) q.pop();
ans += q.empty() ? '#' : q.front();
}
return ans;
}
int main() {
string s;
while (cin >> s) {
if (s == "big") s = string(300000, 'a'); // test: 300,000 a's
string ans = firstUnique(s);
if (s.size() > 20) cout << ans.size() << " answers, last " << ans.back() << "\n";
else cout << s << ": " << ans << "\n";
}
return 0;
}
aabc: a#bb
zz: z#
abba: aaa#
On big, instantly:
300000 answers, last #
O(n) time, O(26) = O(1) extra space (26 counts and at most 26 candidates).
Stack, queue or deque?
| Use | When the next thing to handle is | Examples |
|---|---|---|
| stack | the newest | brackets, undo, next greater element |
| queue | the oldest | ticket lines, printer jobs, first unique character, BFS |
| deque | removed from both ends | sliding window maximum, palindromes, 0-1 BFS |
And whenever many things can become useless at once (too small at the back, out at the front), pop with while, not if.
Complexity summary
| Program | Time | Extra space |
|---|---|---|
| two-stack queue, move back every pop | O(n) per pop: TLE | O(n) |
| two-stack queue, flip only when empty | O(1) amortised per op | O(n) |
| window max, rescan | O(n · k): TLE | O(1) |
| window max, deque of indexes | O(n) | O(k) |
| first unique, rescan | O(n²): TLE | O(26) |
| first unique, queue + counts | O(n) | O(26) |
Common mistakes (and the real results)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| moving everything back after every pop | Time Limit Exceeded | O(n) per pop | leave out as it is |
flipping when out isn't empty |
1 3 2 |
new values jump over older ones | if (out.empty()) flip |
| never dropping the deque's front | 9 9 9 for 9 1 2 3, k = 2 |
an old maximum stays | if (dq.front() <= i - k) dq.pop_front(); |
| storing values in the deque | can't tell the front's age | values aren't positions | store indexes |
reading the window max before i >= k - 1 |
extra "windows" of fewer than k values | the first window isn't full | if (i >= k - 1) |
if to skip repeated candidates |
abba: aaab |
only one is skipped | while |
q.front() on an empty queue |
undefined behaviour | nobody is left | print # when q.empty() |
q.pop() used as a value |
error: void value not ignored as it ought to be |
pop() returns void |
x = q.front(); q.pop(); |
Your turn: reverse the first k of a queue (solution)
Problem. Reverse the first k values of a queue, using only a queue and a stack. 1 2 3 4 5, k = 3 → 3 2 1 4 5.
Idea. Pop k values into a stack (reversing them), push them back into the queue (now at the back), then move the other n − k values from the front to the back.
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
void reverseFirstK(queue<int>& q, int k) {
stack<int> st;
for (int i = 0; i < k; i++) { st.push(q.front()); q.pop(); }
while (!st.empty()) { q.push(st.top()); st.pop(); }
for (int i = 0; i < (int)q.size() - k; i++) { q.push(q.front()); q.pop(); }
}
int main() {
int n, k;
while (cin >> n >> k) {
queue<int> q;
for (int i = 0; i < n; i++) { int x; cin >> x; q.push(x); }
reverseFirstK(q, k);
while (!q.empty()) { cout << q.front() << " "; q.pop(); }
cout << "\n";
}
return 0;
}
5 3 / 1 2 3 4 5, 4 4 / 10 20 30 40, 3 1 / 7 8 9:
3 2 1 4 5
40 30 20 10
7 8 9
O(n) time, O(k) extra space.
Practice questions (with solutions)
1. Binary numbers from 1 to n with a queue.
Solution
Start with "1"; each time, pop a string s, print it, and push s + "0" and s + "1". The queue produces them in increasing order.
#include <iostream>
#include <string>
#include <queue>
using namespace std;
int main() {
int n;
cin >> n;
queue<string> q;
q.push("1");
for (int i = 0; i < n; i++) {
string s = q.front(); q.pop();
cout << s << " ";
q.push(s + "0");
q.push(s + "1");
}
cout << "\n";
return 0;
}
Input 10:
1 10 11 100 101 110 111 1000 1001 1010
2. First negative number in every window of k. Print 0 for a window with no negative number.
Solution
A queue of the indexes of negative numbers; drop indexes that slid out of the window; the front is the answer.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int& x : a) cin >> x;
queue<int> neg; // indexes of negatives, oldest first
for (int i = 0; i < n; i++) {
if (a[i] < 0) neg.push(i);
while (!neg.empty() && neg.front() <= i - k) neg.pop();
if (i >= k - 1) cout << (neg.empty() ? 0 : a[neg.front()]) << " ";
}
cout << "\n";
return 0;
}
Input 8 3 / 12 -1 -7 8 -15 30 16 28:
-1 -1 -7 -15 -15 0
3. A stack using two queues.
Solution
To push x: put it into the empty queue q2, move everything from q1 behind it, then swap q1 and q2. Now q1.front() is always the newest value. Push O(n), pop O(1).
#include <iostream>
#include <queue>
using namespace std;
struct QueueStack {
queue<int> q1, q2;
void push(int x) {
q2.push(x);
while (!q1.empty()) { q2.push(q1.front()); q1.pop(); }
swap(q1, q2);
}
int pop() { int x = q1.front(); q1.pop(); return x; }
bool empty() const { return q1.empty(); }
};
int main() {
QueueStack s;
for (int x : {1, 2, 3}) s.push(x);
cout << s.pop() << " ";
s.push(4);
while (!s.empty()) cout << s.pop() << " ";
cout << "\n";
return 0;
}
3 4 2 1
4. Is a word a palindrome? Use a deque.
Solution
Put the letters in a deque and compare front() and back(), popping both, until fewer than two are left.
#include <iostream>
#include <string>
#include <deque>
using namespace std;
int main() {
string s;
while (cin >> s) {
deque<char> dq(s.begin(), s.end());
bool ok = true;
while (dq.size() > 1) {
if (dq.front() != dq.back()) { ok = false; break; }
dq.pop_front();
dq.pop_back();
}
cout << s << ": " << (ok ? "palindrome" : "no") << "\n";
}
return 0;
}
malayalam: palindrome
deque: no
level: palindrome
abca: no
Mini project: a printer queue
Jobs arrive (add <name> <pages>); the printer prints 5 pages per tick (tick) from the oldest job; status shows the waiting jobs. A queue keeps the order fair.
#include <iostream>
#include <string>
#include <queue>
using namespace std;
struct Job { string name; int pages; };
int main() {
queue<Job> q;
string cmd;
int tick = 0;
while (cin >> cmd) {
if (cmd == "add") {
Job j;
cin >> j.name >> j.pages;
q.push(j);
} else if (cmd == "tick") {
tick++;
int budget = 5; // pages per tick
while (budget > 0 && !q.empty()) {
int done = min(budget, q.front().pages);
q.front().pages -= done;
budget -= done;
if (q.front().pages == 0) {
cout << "tick " << tick << ": finished " << q.front().name << "\n";
q.pop();
}
}
} else {
cout << "waiting: " << q.size();
if (!q.empty()) cout << ", next " << q.front().name << " (" << q.front().pages << " pages left)";
cout << "\n";
}
}
return 0;
}
waiting: 3, next notes (7 pages left)
waiting: 3, next notes (2 pages left)
tick 2: finished notes
tick 2: finished resume
tick 3: finished ticket
waiting: 0
Quick quiz
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> dq;
dq.push_back(1);
dq.push_back(2);
dq.push_front(3);
dq.pop_back();
dq.push_front(4);
cout << dq.front() << " " << dq.back() << " " << dq.size() << "\n";
return 0;
}
(A) 4 1 3 (B) 4 2 3 (C) 3 1 3 (D) 1 4 3
Answer
(A) 4 1 3. [1] → [1 2] → [3 1 2] → pop_back → [3 1] → push_front(4) → [4 3 1].
4 1 3
Interview questions
- Queue vs stack? A queue removes the oldest value (FIFO); a stack removes the newest (LIFO).
- What is a deque and what does
std::dequecost? A double-ended queue: O(1) push/pop at both ends and O(1) indexing. - How do you build a queue from two stacks? Push onto
in; to pop, ifoutis empty move everything fromintoout, then popout. - Why is that amortised O(1)? Each value is moved from
intooutat most once, so n operations cost O(n) in total even though a single pop can cost O(n). - What does amortised mean? The cost averaged over a whole sequence of operations, not the worst single operation.
- Why does the sliding window maximum use a deque, not a heap? A deque gives O(n) total; a heap needs O(n log k) and lazy deletion of old values.
- Why store indexes in the deque? To know when the front has slid out of the window (
front <= i - k). - Why is the window maximum O(n) with a
whileinside the loop? Every index is pushed once and popped at most once. - First non-repeating character: why a queue? Candidates are needed in arrival order, and the earliest one is checked first.
- What does
std::queueuse underneath? Astd::dequeby default (likestd::stack).
Glossary
| Term | Meaning | Example |
|---|---|---|
| Queue | A container where values join at the back and leave from the front | a ticket line |
| FIFO | First in, first out | the first in line is served first |
std::queue |
The C++ queue adaptor, from <queue> |
queue<int> q; q.push(5); |
front() |
Reads the first (oldest) value of a queue or deque | q.front() |
| Deque | A double-ended queue: add and remove at both ends | deque<int> dq; |
push_front / pop_back |
Add at the front / remove from the back of a deque | dq.push_front(3); |
| Amortised O(1) | O(1) on average over all operations, though one may be slow | the two-stack queue |
| Sliding window maximum | The largest value in every window of k in a row | 3 3 5 5 6 7 |
| Monotonic deque | A deque whose values stay sorted, by popping before each push | values fall front to back |
| Window | The k positions i − k + 1 .. i |
indexes 2..3 for i = 3, k = 2 |
| Stream | Data that arrives one piece at a time | characters typed one by one |
| Non-repeating character | A character seen exactly once so far | b in aab |
| Candidate | A value that could still be the answer | names still in the lucky draw |
| Time Limit Exceeded (TLE) | The judge stopped a program that ran too long | O(n · k) on a million numbers |
Summary
- Queue: FIFO,
push/front/pop; deque: both ends, O(1); neverfront()an empty one. - Queue from two stacks: push to
in; pop fromout, flippinginintooutonly whenoutis empty. Amortised O(1). - Sliding window maximum: a deque of indexes; pop the back while not bigger, pop the front once
<= i − k; the front is the max. O(n). - First non-repeating character: counts + a queue of first-time characters;
whilethe front is repeated, pop. O(n).
Next episode: Heap questions: the k largest elements (a min-heap of size k), the k-th smallest, and merging k sorted vectors with priority_queue and greater<>.