Navigation

DSA stacks queues 12 min read

Stacks & Queues Exercises: Answer Sheet & Solutions

This is the answer sheet for the stacks & queues exercises. Each solution gives the key idea, the optimal complexity, the code in all four languages (use the switcher), and common pitfalls. Try the problems first — then check your work here.

Q1. Reverse a string using a stack

Idea: A stack is LIFO, so pushing every character and then popping them yields the characters in reverse order — the reversal is automatic. (In practice you’d just reverse in place, but this demonstrates the LIFO property.)

Complexity: O(n) time, O(n) space.

#include <string>
#include <stack>
std::string reverseWithStack(const std::string& s) {
    std::stack<char> st;
    for (char c : s) st.push(c);
    std::string out;
    while (!st.empty()) { out += st.top(); st.pop(); }
    return out;
}

import java.util.*;
String reverseWithStack(String s) {
    Deque<Character> st = new ArrayDeque<>();
    for (char c : s.toCharArray()) st.push(c);
    StringBuilder out = new StringBuilder();
    while (!st.isEmpty()) out.append(st.pop());
    return out.toString();
}

function reverseWithStack(s) {
  const st = [];
  for (const c of s) st.push(c);
  let out = "";
  while (st.length) out += st.pop();
  return out;
}

def reverse_with_stack(s):
    st = list(s)          # pushing every char
    out = []
    while st:
        out.append(st.pop())
    return "".join(out)

Pitfall: Building the result with repeated string concatenation is O(n²) in some languages. Use a StringBuilder (Java) or a list join (Python) for true O(n).

Q2. Valid parentheses

Idea: Push every opening bracket. On a closing bracket, the top of the stack must be its matching opener — otherwise it’s invalid. At the end the stack must be empty (no unclosed openers).

Complexity: O(n) time, O(n) space.

#include <string>
#include <stack>
#include <unordered_map>
bool isValid(const std::string& s) {
    std::unordered_map<char, char> match = {{')','('}, {']','['}, {'}','{'}};
    std::stack<char> st;
    for (char c : s) {
        if (match.count(c)) {
            if (st.empty() || st.top() != match[c]) return false;
            st.pop();
        } else st.push(c);
    }
    return st.empty();
}

import java.util.*;
boolean isValid(String s) {
    Map<Character, Character> match = Map.of(')', '(', ']', '[', '}', '{');
    Deque<Character> st = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (match.containsKey(c)) {
            if (st.isEmpty() || st.pop() != match.get(c)) return false;
        } else st.push(c);
    }
    return st.isEmpty();
}

function isValid(s) {
  const match = { ')': '(', ']': '[', '}': '{' };
  const st = [];
  for (const c of s) {
    if (c in match) {
      if (st.pop() !== match[c]) return false;
    } else st.push(c);
  }
  return st.length === 0;
}

def is_valid(s):
    match = {')': '(', ']': '[', '}': '{'}
    st = []
    for c in s:
        if c in match:
            if not st or st.pop() != match[c]:
                return False
        else:
            st.append(c)
    return not st

Pitfall: Returning true as soon as you reach the end without checking that the stack is empty. "(((" never mismatches but is still invalid.

Q3. Implement a queue using two stacks

Idea: Use an in stack for enqueues and an out stack for dequeues. To dequeue, if out is empty, pour everything from in into out — this reverses LIFO into FIFO. Each element is moved at most once, so dequeue is amortized O(1).

Complexity: enqueue O(1); dequeue amortized O(1). O(n) space.

#include <stack>
#include <stdexcept>
class MyQueue {
    std::stack<int> in, out;
public:
    void enqueue(int x) { in.push(x); }
    int dequeue() {
        if (out.empty()) {
            if (in.empty()) throw std::out_of_range("empty queue");
            while (!in.empty()) { out.push(in.top()); in.pop(); }
        }
        int x = out.top(); out.pop();
        return x;
    }
};

import java.util.*;
class MyQueue {
    private Deque<Integer> in = new ArrayDeque<>(), out = new ArrayDeque<>();
    public void enqueue(int x) { in.push(x); }
    public int dequeue() {
        if (out.isEmpty()) {
            if (in.isEmpty()) throw new NoSuchElementException("empty queue");
            while (!in.isEmpty()) out.push(in.pop());
        }
        return out.pop();
    }
}

class MyQueue {
  constructor() { this.in = []; this.out = []; }
  enqueue(x) { this.in.push(x); }
  dequeue() {
    if (this.out.length === 0) {
      if (this.in.length === 0) throw new Error("empty queue");
      while (this.in.length) this.out.push(this.in.pop());
    }
    return this.out.pop();
  }
}

class MyQueue:
    def __init__(self):
        self._in, self._out = [], []
    def enqueue(self, x):
        self._in.append(x)
    def dequeue(self):
        if not self._out:
            if not self._in:
                raise IndexError("empty queue")
            while self._in:
                self._out.append(self._in.pop())
        return self._out.pop()

Pitfall: Refilling out from in on every dequeue (even when out is non-empty) breaks FIFO order and ruins the amortized bound. Only refill when out is empty.

Q4. Min Stack

Idea: Alongside each value, store the minimum of the stack at that point. Pushing records min(x, currentMin); popping discards both. The current minimum is always the top of the min-tracking stack — O(1).

Complexity: O(1) for every operation. O(n) space.

#include <stack>
#include <algorithm>
class MinStack {
    std::stack<int> data, mins;
public:
    void push(int x) {
        data.push(x);
        mins.push(mins.empty() ? x : std::min(x, mins.top()));
    }
    void pop() { data.pop(); mins.pop(); }
    int top() const { return data.top(); }
    int getMin() const { return mins.top(); }
};

import java.util.*;
class MinStack {
    private Deque<Integer> data = new ArrayDeque<>(), mins = new ArrayDeque<>();
    public void push(int x) {
        data.push(x);
        mins.push(mins.isEmpty() ? x : Math.min(x, mins.peek()));
    }
    public void pop() { data.pop(); mins.pop(); }
    public int top() { return data.peek(); }
    public int getMin() { return mins.peek(); }
}

class MinStack {
  constructor() { this.data = []; this.mins = []; }
  push(x) {
    this.data.push(x);
    const m = this.mins.length ? Math.min(x, this.mins[this.mins.length - 1]) : x;
    this.mins.push(m);
  }
  pop() { this.data.pop(); this.mins.pop(); }
  top() { return this.data[this.data.length - 1]; }
  getMin() { return this.mins[this.mins.length - 1]; }
}

class MinStack:
    def __init__(self):
        self._data = []
        self._mins = []
    def push(self, x):
        self._data.append(x)
        self._mins.append(x if not self._mins else min(x, self._mins[-1]))
    def pop(self):
        self._data.pop()
        self._mins.pop()
    def top(self):
        return self._data[-1]
    def get_min(self):
        return self._mins[-1]

Pitfall: Keeping a single min variable instead of a stack. When you pop the current minimum you’d have no way to restore the previous minimum in O(1). The parallel min-stack remembers every prefix minimum.

Q5. Next Greater Element

Idea: Use a monotonic stack of indices whose values are decreasing. Scanning left to right, when the current value exceeds the value at the top index, the current value is that index’s next-greater — pop and record it. Then push the current index.

Complexity: O(n) time (each index pushed/popped once), O(n) space.

#include <vector>
#include <stack>
std::vector<int> nextGreater(const std::vector<int>& a) {
    int n = a.size();
    std::vector<int> res(n, -1);
    std::stack<int> st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[i] > a[st.top()]) {
            res[st.top()] = a[i];
            st.pop();
        }
        st.push(i);
    }
    return res;
}

import java.util.*;
int[] nextGreater(int[] a) {
    int n = a.length;
    int[] res = new int[n];
    Arrays.fill(res, -1);
    Deque<Integer> st = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        while (!st.isEmpty() && a[i] > a[st.peek()]) {
            res[st.pop()] = a[i];
        }
        st.push(i);
    }
    return res;
}

function nextGreater(a) {
  const n = a.length;
  const res = new Array(n).fill(-1);
  const st = [];
  for (let i = 0; i < n; i++) {
    while (st.length && a[i] > a[st[st.length - 1]]) {
      res[st.pop()] = a[i];
    }
    st.push(i);
  }
  return res;
}

def next_greater(a):
    n = len(a)
    res = [-1] * n
    st = []
    for i in range(n):
        while st and a[i] > a[st[-1]]:
            res[st.pop()] = a[i]
        st.append(i)
    return res

Pitfall: Pushing values instead of indices. You need the index to write the answer into the right slot of res. Store indices, read values via a[index].

Q6. Implement a stack using two queues

Idea: Make push do the work. Enqueue the new element into the empty helper queue q2, then move every element of q1 behind it, and swap the two queues. Now q1’s front is always the most recently pushed element, so pop is a plain O(1) dequeue.

Complexity: push O(n); pop, top O(1). O(n) space.

#include <queue>
#include <stdexcept>
class MyStack {
    std::queue<int> q1, q2;
public:
    void push(int x) {
        q2.push(x);
        while (!q1.empty()) { q2.push(q1.front()); q1.pop(); }
        std::swap(q1, q2);
    }
    int pop() {
        if (q1.empty()) throw std::out_of_range("empty stack");
        int x = q1.front(); q1.pop();
        return x;
    }
    int top() const { return q1.front(); }
};

import java.util.*;
class MyStack {
    private Queue<Integer> q1 = new ArrayDeque<>(), q2 = new ArrayDeque<>();
    public void push(int x) {
        q2.offer(x);
        while (!q1.isEmpty()) q2.offer(q1.poll());
        Queue<Integer> tmp = q1; q1 = q2; q2 = tmp;   // swap
    }
    public int pop() {
        if (q1.isEmpty()) throw new NoSuchElementException("empty stack");
        return q1.poll();
    }
    public int top() { return q1.peek(); }
}

class MyStack {
  constructor() { this.q1 = []; this.q2 = []; }
  push(x) {
    this.q2.push(x);
    while (this.q1.length) this.q2.push(this.q1.shift());
    [this.q1, this.q2] = [this.q2, this.q1];   // swap
  }
  pop() {
    if (this.q1.length === 0) throw new Error("empty stack");
    return this.q1.shift();
  }
  top() { return this.q1[0]; }
}

from collections import deque
class MyStack:
    def __init__(self):
        self.q1, self.q2 = deque(), deque()
    def push(self, x):
        self.q2.append(x)
        while self.q1:
            self.q2.append(self.q1.popleft())
        self.q1, self.q2 = self.q2, self.q1   # swap
    def pop(self):
        if not self.q1:
            raise IndexError("empty stack")
        return self.q1.popleft()
    def top(self):
        return self.q1[0]

Pitfall: Forgetting the swap, or enqueuing the new element into q1 first — then the rotation order is wrong and you no longer get LIFO. Always stage the new element in the empty queue, drain the other behind it, then swap.

Q7. Sliding window maximum

Idea: Keep a monotonic deque of indices with decreasing values. For each i: pop indices off the back whose values are <= a[i] (they can never be a max while a[i] is in the window), then push i. Drop the front if it’s outside the window (< i - k + 1). The front is always the current window’s maximum.

Complexity: O(n) time (each index enters/leaves the deque once), O(k) space.

#include <vector>
#include <deque>
std::vector<int> maxSlidingWindow(const std::vector<int>& a, int k) {
    std::deque<int> dq;            // indices, values decreasing
    std::vector<int> res;
    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();   // out of window
        if (i >= k - 1) res.push_back(a[dq.front()]);
    }
    return res;
}

import java.util.*;
int[] maxSlidingWindow(int[] a, int k) {
    Deque<Integer> dq = new ArrayDeque<>();        // indices, values decreasing
    int n = a.length;
    int[] res = new int[n - k + 1];
    int idx = 0;
    for (int i = 0; i < n; i++) {
        while (!dq.isEmpty() && a[dq.peekLast()] <= a[i]) dq.pollLast();
        dq.offerLast(i);
        if (dq.peekFirst() <= i - k) dq.pollFirst();
        if (i >= k - 1) res[idx++] = a[dq.peekFirst()];
    }
    return res;
}

function maxSlidingWindow(a, k) {
  const dq = [];        // indices, values decreasing
  const res = [];
  for (let i = 0; i < a.length; i++) {
    while (dq.length && a[dq[dq.length - 1]] <= a[i]) dq.pop();
    dq.push(i);
    if (dq[0] <= i - k) dq.shift();
    if (i >= k - 1) res.push(a[dq[0]]);
  }
  return res;
}

from collections import deque
def max_sliding_window(a, k):
    dq = deque()          # indices, values decreasing
    res = []
    for i, x in enumerate(a):
        while dq and a[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            res.append(a[dq[0]])
    return res

Pitfall: Storing values instead of indices — you can’t tell when the front has slid out of the window. Track indices and evict the front when front <= i - k.

That’s the full answer sheet. Back to the stacks & queues exercises, or continue to hashing.