Stack and queue interview questions, with answers

The questions, with answers

1. 1.What is the difference between a stack and a queue, and where does each appear in real systems?

   A stack is last-in, first-out: push and pop happen at the same end, so the most recent item comes out first. A queue is first-in, first-out: items enter at the rear and leave from the front, so the oldest item comes out first. Both give O(1) insert and remove when implemented sensibly. Stacks are everywhere control flow is nested — the call stack, undo history, the back button, matching brackets, depth-first search. Queues appear wherever order of arrival matters — print jobs, request handling, breadth-first search, producer-consumer buffers between threads.

2. 2.What is the stack approach to bracket matching, and which edge cases do candidates miss?

   Scan left to right. Push every opening bracket. On a closing bracket, pop and check that what came off is the matching opener. The three failures people forget: a closing bracket when the stack is empty ("())"), a closer of the wrong type ("(]"), and — the one most often missed — characters left on the stack when the input ends ("(("), which means unmatched openers. The string is balanced only if every check passes and the stack is empty at the end. O(n) time, O(n) space in the worst case of all openers.

   boolean balanced(String s) {
       String pairs = "()[]{}";                 // opener at even index, its closer right after
       Deque<Character> st = new ArrayDeque<>();
       for (char c : s.toCharArray()) {
           int i = pairs.indexOf(c);
           if (i % 2 == 0) st.push(c);              // an opener
           else if (st.isEmpty() || pairs.indexOf(st.pop()) != i - 1) return false;
       }
       return st.isEmpty();                         // leftover openers fail too
   }

3. 3.How do you implement a queue using two stacks?

   Keep an in-stack and an out-stack. Enqueue always pushes onto the in-stack. Dequeue pops from the out-stack; if the out-stack is empty, first pour everything from the in-stack into it, which reverses the order so the oldest element is on top. A single dequeue can cost O(n) when the pour happens, but each element is moved at most once in its lifetime, so over any sequence of operations the cost is O(1) amortised per operation. That word — amortised — is what the interviewer is listening for; also note that you never pour while the out-stack still has elements, or you would break the order.

4. 4.How do you implement a stack using queues?

   With one queue: on push, enqueue the element and then rotate the queue by dequeuing and re-enqueuing the previous size-many elements, so the new element ends up at the front. Push is O(n), pop and peek are O(1) — just the front. The two-queue version makes push O(1) and pop O(n) instead: pop moves all but the last element into the second queue, returns the last, then swaps the queues. Neither is efficient, and the interviewer knows it; the question checks that you can reason about which end each structure exposes and that you pick which operation to make expensive on purpose.

5. 5.How do you design a stack that returns its minimum element in O(1)?

   Keep a second stack of minimums alongside the main one. On push, if the new value is less than or equal to the current top of the min stack, push it onto the min stack too. On pop, if the popped value equals the min stack's top, pop that as well. The min stack's top is always the minimum of what remains. The subtlety is the "or equal": pushing duplicates of the minimum onto the min stack means that popping one copy does not lose the minimum still present below. Space is O(n) in the worst case (a descending sequence pushes everything twice); a variant stores the value and the current minimum together in each node to avoid the second stack.

6. 6.What is a circular queue, and why use it instead of a plain array queue?

   A plain array queue moves its front index forward on every dequeue, so the space behind it is wasted and the queue "walks" to the end of the array even though it is mostly empty. A circular queue wraps the indices around using modulo, so the freed slots are reused and a fixed-size buffer supports unlimited enqueue and dequeue as long as it never holds more than its capacity. The classic subtlety is telling full from empty, since both have front equal to rear: keep an explicit count, or leave one slot permanently empty so full means (rear + 1) % capacity == front. Ring buffers in device drivers and audio pipelines are exactly this structure.

7. 7.How do you convert an infix expression to postfix with a stack?

   This is the shunting-yard algorithm. Scan the infix expression left to right. Operands go straight to the output. For an operator, first pop to the output every operator on the stack with higher precedence, or equal precedence when the operator is left-associative, then push the new operator. A left parenthesis is pushed; a right parenthesis pops operators to the output until the matching left parenthesis, which is discarded. At the end, pop whatever remains.

   For a + b * c - d: a goes out, + is pushed, b goes out, * has higher precedence so it is pushed, c goes out, - pops * and then + (equal precedence, left-associative) before being pushed, d goes out, and the final pop gives a b c * + d -. Postfix needs no parentheses, which is why calculators and compilers evaluate it with a second, simpler stack.

8. 8.What is a deque, and what is the sliding-window maximum trick?

   A deque is a double-ended queue: O(1) insert and remove at both ends. The trick built on it is the monotonic deque, which finds the maximum of every window of size k in an array in O(n) total. Keep a deque of indices whose values are in decreasing order. For each new element, pop from the back every index whose value is smaller (they can never be a maximum while the new element is in the window), push the new index, and pop from the front if the front index has left the window. The front is always the window's maximum. Each index is pushed and popped at most once, hence linear time — against the naive O(n × k) of rescanning every window.

How the diagnostic asks it

One question from the DSA bank, exactly as a sitting would show it. The bank has 5 on stacks & queues and 60 across DSA.