Stack and Queue Interview Questions for Placements (with Code)

10 must-do stack and queue interview questions for placements with Python code, approach, time complexity and the patterns interviewers test most.

  Company-wise Interview Questions   Oct 7, 2026   20  Add to Reading List

Why Stacks and Queues Matter in Coding Rounds

Stacks and queues are simple data structures, but they power some of the most frequently asked problems in placement coding rounds and technical interviews. Bracket matching, next greater element, sliding window maximum and "implement a queue using stacks" appear again and again across service and product companies.

The reason is that these problems test whether you can spot a pattern. A brute-force solution with nested loops usually takes O(n²) time. The stack or queue solution brings it down to O(n), and interviewers want to see you make that jump.

This guide covers the basics, the two patterns behind most questions, and 10 must-do problems with tested Python code, approach and complexity. If you are new to DSA, start with our DSA for Campus Placements roadmap and Arrays and Strings for Coding Interviews first.

Stack and Queue Basics in 2 Minutes

A stack follows Last In, First Out (LIFO). Think of a pile of plates: you add and remove from the top. A queue follows First In, First Out (FIFO). Think of a ticket line: people join at the back and leave from the front. A deque (double-ended queue) allows adding and removing at both ends.

OperationStackQueueTime
Addpush (to top)enqueue (to rear)O(1)
Removepop (from top)dequeue (from front)O(1)
Lookpeek / topfrontO(1)
Python toollist with append() and pop()collections.deque with append() and popleft()—
Java toolArrayDeque (push, pop)ArrayDeque or LinkedList (offer, poll)—
C++ toolstd::stackstd::queue, std::deque—

Python tip: never use list.pop(0) as a queue. It shifts every element, which costs O(n). Use collections.deque instead.

Where They Are Used in Real Systems

  • Stacks: function call stack, undo in editors, browser back button, expression evaluation.
  • Queues: printer jobs, CPU scheduling, breadth-first search (BFS), message queues between services.

Interviewers sometimes open with these "real-world use" questions before giving you a coding problem, so keep one example of each ready.

The Two Patterns Behind Most Questions

1. Matching and undoing. When something must be closed or cancelled in reverse order (brackets, tags, undo actions), push items as they open and pop when they close.

2. Monotonic stack or deque. When each element needs the next or previous greater or smaller element, keep a stack whose values stay in increasing or decreasing order. Each element is pushed once and popped at most once, so the total work is O(n) even though there is a while loop inside the for loop. Recognising this pattern solves next greater element, stock span, largest rectangle in histogram and sliding window maximum.

10 Must-Do Stack and Queue Interview Questions

1. Valid Parentheses

Problem: Given a string of brackets ( ) [ ] { }, check whether every opening bracket is closed in the correct order.

Example: "{[()]}" is valid. "([)]" is not valid.

Approach: Push every opening bracket. For a closing bracket, the stack top must be its matching opener. At the end, the stack must be empty.

Python
def is_valid(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        elif not stack or stack.pop() != pairs[ch]:
            return False
    return not stack

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

2. Next Greater Element

Problem: For each element, find the first element to its right that is greater. Use -1 if none exists.

Example: [4, 5, 2, 25] gives [5, 25, 25, -1].

Approach: Keep a stack of indexes still waiting for a greater value. When a bigger number arrives, it is the answer for every smaller value it pops.

Python
def next_greater(arr):
    result = [-1] * len(arr)
    stack = []  # holds indexes waiting for a greater element
    for i, x in enumerate(arr):
        while stack and arr[stack[-1]] < x:
            result[stack.pop()] = x
        stack.append(i)
    return result

Complexity: O(n) time, O(n) space. Each index is pushed and popped once.

3. Min Stack

Problem: Design a stack that supports push, pop, top and get_min, all in O(1) time.

Example: Push 5, 3, 7, 2: get_min is 2. After one pop, get_min is 3.

Approach: Store each value together with the minimum so far. The minimum is always at the top, so no searching is needed.

Python
class MinStack:
    def __init__(self):
        self.stack = []  # each item is (value, min_so_far)

    def push(self, x):
        current_min = min(x, self.stack[-1][1]) if self.stack else x
        self.stack.append((x, current_min))

    def pop(self):
        return self.stack.pop()[0]

    def top(self):
        return self.stack[-1][0]

    def get_min(self):
        return self.stack[-1][1]

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

4. Implement a Queue Using Two Stacks

Problem: Build a FIFO queue using only stack operations.

Example: Push 1, 2, 3, then pop gives 1.

Approach: Push into an inbox stack. To pop, move everything into an outbox stack only when the outbox is empty. This reverses the order once.

Python
class MyQueue:
    def __init__(self):
        self.inbox, self.outbox = [], []

    def push(self, x):
        self.inbox.append(x)

    def pop(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())
        return self.outbox.pop()

Complexity: Amortised O(1) per operation, because each element moves between stacks only once.

5. Evaluate a Postfix Expression

Problem: Evaluate an expression in postfix (Reverse Polish) notation.

Example: "2 3 1 * + 9 -" means 2 + (3 × 1) − 9 = −4.

Approach: Push numbers. On an operator, pop two values: the second pop is the left operand. Push the result back.

Python
def eval_postfix(tokens):
    stack = []
    for t in tokens:
        if t in '+-*/':
            b, a = stack.pop(), stack.pop()
            if t == '+': stack.append(a + b)
            elif t == '-': stack.append(a - b)
            elif t == '*': stack.append(a * b)
            else: stack.append(int(a / b))  # truncate toward zero
        else:
            stack.append(int(t))
    return stack[0]

Complexity: O(n) time, O(n) space. A common follow-up asks you to convert infix to postfix, which also uses a stack.

6. Stock Span Problem

Problem: For each day, find how many consecutive days up to and including today had a price less than or equal to today's price.

Example: [100, 80, 60, 70, 60, 75, 85] gives [1, 1, 1, 2, 1, 4, 6].

Approach: This is "previous greater element" in disguise. Pop all days with a lower or equal price; the remaining top is the previous higher day.

Python
def stock_span(prices):
    span = []
    stack = []  # indexes of days with higher prices
    for i, p in enumerate(prices):
        while stack and prices[stack[-1]] <= p:
            stack.pop()
        span.append(i + 1 if not stack else i - stack[-1])
        stack.append(i)
    return span

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

7. Largest Rectangle in Histogram

Problem: Given bar heights, find the area of the largest rectangle that fits inside the histogram.

Example: [2, 1, 5, 6, 2, 3] gives 10 (bars of height 5 and 6, width 2).

Approach: Keep an increasing stack. When a shorter bar arrives, each popped bar gets its final width: from the new stack top to the current index. Adding a 0 at the end forces all remaining bars to be processed.

Python
def largest_rectangle(heights):
    stack, best = [], 0
    for i, h in enumerate(heights + [0]):
        while stack and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            left = stack[-1] + 1 if stack else 0
            best = max(best, height * (i - left))
        stack.append(i)
    return best

Complexity: O(n) time, O(n) space. This is a favourite in product-company interviews.

8. Sliding Window Maximum

Problem: Return the maximum of every window of size k.

Example: [1, 3, -1, -3, 5, 3, 6, 7] with k = 3 gives [3, 3, 5, 5, 6, 7].

Approach: Use a deque of indexes with decreasing values. The front is always the current maximum. Remove indexes that fall out of the window.

Python
from collections import deque

def max_sliding_window(nums, k):
    dq, result = deque(), []  # dq stores indexes, values decreasing
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] < x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

Complexity: O(n) time, O(k) space. The brute-force approach is O(n × k).

9. First Non-Repeating Character in a Stream

Problem: As characters arrive one by one, output the first character seen so far that has not repeated, or # if none.

Example: "aabc" gives "a#bb".

Approach: Count every character and keep a queue in arrival order. Remove characters from the front while they have repeated.

Python
from collections import deque, Counter

def first_non_repeating(stream):
    count, q, out = Counter(), deque(), []
    for ch in stream:
        count[ch] += 1
        q.append(ch)
        while q and count[q[0]] > 1:
            q.popleft()
        out.append(q[0] if q else '#')
    return ''.join(out)

Complexity: O(n) time overall. Space is limited by the number of distinct characters.

10. Reverse the First K Elements of a Queue

Problem: Reverse the first k elements of a queue and leave the rest in order.

Example: [1, 2, 3, 4, 5] with k = 3 gives [3, 2, 1, 4, 5].

Approach: Pop k items into a stack, push them back (now reversed), then move the remaining n − k items from front to back.

Python
from collections import deque

def reverse_first_k(q, k):
    stack = [q.popleft() for _ in range(k)]
    while stack:
        q.append(stack.pop())
    for _ in range(len(q) - k):
        q.append(q.popleft())
    return q

Complexity: O(n) time, O(k) space. A popular question in service-company coding rounds.

Quick Revision Table

ProblemStructurePatternTime
Valid parenthesesStackMatchingO(n)
Next greater elementStackMonotonic decreasingO(n)
Min stackStack of pairsTrack extra stateO(1) per op
Queue using two stacksTwo stacksReverse onceAmortised O(1)
Postfix evaluationStackOperands wait for operatorO(n)
Stock spanStackPrevious greaterO(n)
Largest rectangleStackMonotonic increasingO(n)
Sliding window maximumDequeMonotonic dequeO(n)
First non-repeating in streamQueue + countsOrder + frequencyO(n)
Reverse first k of queueQueue + stackReverse partO(n)

Common Mistakes in Interviews

  • Popping from an empty stack. Always check the stack is not empty before pop or peek. Valid parentheses fails on input ")" without this check.
  • Storing values instead of indexes. Monotonic stack problems usually need the index to calculate distances or widths. Store indexes and look up values.
  • Using list.pop(0) as a queue in Python. It is O(n) per call. Use deque.popleft().
  • Getting operand order wrong. In postfix evaluation, the first pop is the right operand. 8 2 − is 6, not −6.
  • Saying O(n²) for a monotonic stack. The while loop runs at most n times in total, not n times per element. Explain this clearly; interviewers ask.
  • Not explaining brute force first. Briefly state the O(n²) approach, then improve it. This shows your thinking process.

How to Practise This Topic in One Week

  1. Day 1: Implement a stack and a queue from scratch using an array and a linked list. See our Linked List Interview Questions guide for the linked list part.
  2. Days 2–3: Solve problems 1, 3, 4, 5 and 10 without looking at the code.
  3. Days 4–5: Learn the monotonic pattern with problems 2, 6 and 7. Draw the stack on paper for each step.
  4. Day 6: Solve problems 8 and 9, then try BFS on a grid, which uses a queue.
  5. Day 7: Time yourself: two random problems in 40 minutes, explaining your approach out loud.

After stacks and queues, move on to trees and graphs. Queues are the base of BFS, so read Graph Algorithms for Coding Rounds next.

Frequently Asked Questions

What is the difference between a stack and a queue?

A stack is Last In, First Out: the most recently added item is removed first. A queue is First In, First Out: the oldest item is removed first.

Which stack and queue questions are asked most in placements?

Valid parentheses, next greater element, min stack, queue using two stacks, postfix evaluation and sliding window maximum are among the most common.

What is a monotonic stack?

A stack whose values are kept in increasing or decreasing order. It solves next greater, previous smaller and histogram problems in O(n) time.

How do I implement a queue in Python?

Use collections.deque with append() to add and popleft() to remove. Both are O(1). Avoid list.pop(0), which is O(n).

Can I solve these problems in Java or C++ instead?

Yes. The logic is the same. Use ArrayDeque in Java and std::stack, std::queue or std::deque in C++.

Final Word

Most stack and queue questions come down to two patterns: matching in reverse order, and keeping a monotonic stack or deque. Master the 10 problems above, explain the time complexity clearly, and you will handle most variations in placement coding rounds.

Continue with Arrays and Strings for Coding Interviews, Linked List Interview Questions and our complete DSA for Campus Placements roadmap.

Crack Your Placement with PlacementBaba

Free practice questions, mock tests and interview tipsStart Practicing — DSA Roadmap →