Stacks and Queues in Interviews: LIFO/FIFO Patterns, Monotonic Stacks and Deques

By 0xmote · May 24, 2026 · 22 min read · Updated Sep 27, 2026 Beginner Tutorial

Key takeaways

How stacks (LIFO) and queues (FIFO) work, which interview problems they unlock, advanced variants like deques and monotonic stacks, and troubleshooting notes for common bugs.

Introduction

Stacks and queues are the same idea with one rule changed: both hold items waiting to be processed, and the only question is which waiting item goes next. A stack hands back the most recent one, a queue the oldest one. That single choice decides a surprising amount: depth-first versus breadth-first search, whether brackets can be matched, whether you get the shortest path in a maze or just a path.

In interviews the data structure itself is rarely the hard part. The difficulty is recognizing that a problem is secretly “match the most recent unmatched thing” (stack) or “process things in the order they were discovered” (queue), and then avoiding a handful of implementation traps that are specific to Python and C++.

What this article covers:

Stack (LIFO)
Queue (FIFO)
Implementation methods
Real-world problem solving

Stack

What is a Stack?

A stack is a LIFO (Last In First Out) data structure. The last item inserted comes out first.

Real-life analogies:

Stacking plates: Take the top plate first
Browser back button: Navigate to most recent page
Function call stack: Most recently called function exits first

Stack operations:
    push(3)        push(2)        push(1)
    ↓              ↓              ↓
                            [1]  ← top
                   [2]      [2]
[3]                [3]      [3]  ← bottom
    pop() → 1      pop() → 2      pop() → 3
    ↓              ↓              ↓
[2]  ← top         [3]  ← top     [] (empty)
[3]

Python Implementation (3 Methods)

# Method 1: Using list (simplest, recommended)
stack = []
# push: add element
stack.append(1)  # [1]
stack.append(2)  # [1, 2]
stack.append(3)  # [1, 2, 3]
print(stack)  # [1, 2, 3] (3 is top)
# pop: remove and return top
top = stack.pop()
print(top)  # 3
print(stack)  # [1, 2] (2 is new top)
# top: check without removing
if stack:
    print(stack[-1])  # 2 (last element = top)
# empty check
is_empty = len(stack) == 0
print(is_empty)  # False
# Method 2: collections.deque (works too, no real advantage for a stack)
from collections import deque
stack = deque()
stack.append(1)
stack.append(2)
stack.append(3)
print(stack.pop())  # 3
# Method 3: Class implementation (explicit, educational)
class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, item):
        self.items.append(item)
    
    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        raise IndexError("pop from empty stack")
    
    def top(self):
        if not self.is_empty():
            return self.items[-1]
        raise IndexError("top from empty stack")
    
    def is_empty(self):
        return len(self.items) == 0
    
    def size(self):
        return len(self.items)
# Usage
s = Stack()
s.push(10)
s.push(20)
print(s.top())   # 20
print(s.pop())   # 20
print(s.size())  # 1

A plain list is the right default for a stack in Python. append and pop() both work at the end of the list, which is amortized O(1): the list over-allocates capacity, so most appends do not move anything. A deque offers the same operations and is just as fast for this use, but it gives you nothing extra for a stack, while a list also supports cheap stack[-1] peeks and slicing. The class wrapper is useful in interviews mainly because it makes the empty-stack case explicit instead of relying on Python’s IndexError: pop from empty list.

C++ Implementation

#include <iostream>
#include <stack>
using namespace std;
int main() {
    stack<int> s;
    
    // push: add element
    s.push(1);
    s.push(2);
    s.push(3);
    
    // top: check top (no removal)
    cout << s.top() << endl;  // 3
    
    // pop: remove top (no return!)
    s.pop();  // Remove 3
    
    cout << s.top() << endl;  // 2
    
    // empty: check if empty
    cout << s.empty() << endl;  // 0 (false)
    
    // size: get size
    cout << s.size() << endl;  // 2
    
    return 0;
}

Python vs C++ Difference:

Python: pop() returns the value
C++: pop() doesn’t return, use top() then pop()

The C++ design is deliberate. If pop() returned the element by value and the copy constructor threw an exception after the element had already been removed, the value would be lost. Splitting “read” and “remove” into two calls keeps the container consistent no matter what happens during the copy. The price is a trap: calling top() or pop() on an empty std::stack is undefined behavior, not an exception, so check empty() first. std::stack is an adapter over std::deque by default; std::stack<int, std::vector<int>> is a common alternative when you want contiguous storage.

Stack Time Complexity

Operation	Description	Time	Python	C++
push(x)	Add element	O(1)	`append(x)`	`push(x)`
pop()	Remove top	O(1)	`pop()`	`pop()`
top()	Check top	O(1)	`[-1]`	`top()`
empty()	Check empty	O(1)	`len() == 0`	`empty()`
size()	Get size	O(1)	`len()`	`size()`

Queue

What is a Queue?

A queue is a FIFO (First In First Out) data structure. The first item inserted comes out first.

Real-life analogies:

Standing in line: First person gets served first
Printer queue: First document sent prints first
Call center: First caller gets answered first

Queue operations:
    enqueue(1)     enqueue(2)     enqueue(3)
    ↓              ↓              ↓
[1]                [1][2]         [1][2][3]
 ↑                  ↑              ↑     ↑
front              front          front  rear
    dequeue() → 1  dequeue() → 2  dequeue() → 3
    ↓              ↓              ↓
[2][3]             [3]            [] (empty)
 ↑                  ↑
front              front

Python Implementation

# Method 1: collections.deque (recommended)
from collections import deque
queue = deque()
# enqueue: add to rear
queue.append(1)  # deque([1])
queue.append(2)  # deque([1, 2])
queue.append(3)  # deque([1, 2, 3])
# dequeue: remove from front
front = queue.popleft()  # O(1) - efficient!
print(front)  # 1
print(queue)  # deque([2, 3])
# front: check without removing
if queue:
    print(queue[0])  # 2
# empty check
is_empty = len(queue) == 0
# ❌ Method 2: list (inefficient, NOT recommended)
queue_list = []
queue_list.append(1)
queue_list.pop(0)  # O(n)! Very slow

deque vs list Performance:

import time
from collections import deque
# deque (O(1))
q = deque(range(100000))
start = time.time()
for _ in range(10000):
    q.popleft()
print(f"deque: {time.time() - start:.4f}s")  # milliseconds
# list (O(n))
q = list(range(100000))
start = time.time()
for _ in range(10000):
    q.pop(0)
print(f"list: {time.time() - start:.4f}s")  # much slower, and grows with the list size

The exact times depend on your machine, but the shape does not. list.pop(0) has to shift every remaining element one slot to the left, so each call costs O(n) and draining a queue of n items costs O(n²). deque is implemented as a doubly linked list of fixed-size blocks, so removing from either end touches only one block. The memory shift is fast per element, which is why the list version often looks fine on small tests and then times out on the judge’s largest input. When a BFS solution in Python times out and the algorithm looks right, pop(0) is the first thing I look for.

deque is not better at everything: indexing into the middle (q[50000]) is O(n) on a deque but O(1) on a list. Use each for what it is good at.

C++ Implementation

#include <iostream>
#include <queue>
using namespace std;
int main() {
    queue<int> q;
    
    // push: add to rear
    q.push(1);
    q.push(2);
    q.push(3);
    
    // front: check front (no removal)
    cout << q.front() << endl;  // 1
    
    // back: check rear
    cout << q.back() << endl;  // 3
    
    // pop: remove from front (no return!)
    q.pop();  // Remove 1
    
    cout << q.front() << endl;  // 2
    
    // empty: check if empty
    cout << q.empty() << endl;  // 0 (false)
    
    // size: get size
    cout << q.size() << endl;  // 2
    
    return 0;
}

Problem Solving

Problem 1: Valid Parentheses

def is_valid_parentheses(s):
    """
    Check if parentheses are valid
    "(())" → True
    "(()" → False
    """
    stack = []
    pairs = {'(': ')', '{': '}', '[': ']'}
    
    for char in s:
        if char in pairs:  # Opening bracket
            stack.append(char)
        else:  # Closing bracket
            if not stack:
                return False
            if pairs[stack.pop()] != char:
                return False
    
    return len(stack) == 0
# Test
print(is_valid_parentheses("()"))        # True
print(is_valid_parentheses("()[]{}"))    # True
print(is_valid_parentheses("(]"))        # False
print(is_valid_parentheses("([)]"))      # False
print(is_valid_parentheses("{[]}"))      # True

Why a stack: a closing bracket must match the most recently opened bracket that has not been closed yet. “Most recent unmatched” is exactly what the top of a stack holds. "([)]" fails because when ) arrives, the most recent opening bracket is [, not (.

There are three ways to fail, and the function checks each one: a closing bracket with nothing open (if not stack), a closing bracket of the wrong type, and opening brackets left over at the end (len(stack) == 0). Forgetting the last check is the most common mistake; "((" then returns True. Note also that this version treats any character that is not an opening bracket as a closing one, so "a" makes pairs[stack.pop()] compare against 'a' and return False. If the input can contain other characters, skip them explicitly.

A counter instead of a stack works only when there is a single bracket type. With three types, a counter cannot tell "(]" from "()". C++ Solution:

#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>
using namespace std;
bool isValid(string s) {
    stack<char> st;
    unordered_map<char, char> pairs = {
        {'(', ')'}, {'{', '}'}, {'[', ']'}
    };
    
    for (char c : s) {
        if (pairs.count(c)) {  // Opening bracket
            st.push(c);
        } else {  // Closing bracket
            if (st.empty()) return false;
            
            char opening = st.top();
            st.pop();
            
            if (pairs[opening] != c) return false;
        }
    }
    
    return st.empty();
}

Problem 2: Implement Queue using Stacks

Problem: Implement a queue using two stacks. Idea:

stack_in: for enqueue
stack_out: for dequeue
When dequeue and stack_out is empty, transfer all from stack_in

class QueueUsingStacks:
    """
    Implement queue using two stacks
    """
    def __init__(self):
        self.stack_in = []   # for enqueue
        self.stack_out = []  # for dequeue
    
    def enqueue(self, x):
        """Add to rear - O(1)"""
        self.stack_in.append(x)
    
    def dequeue(self):
        """Remove from front - Amortized O(1)"""
        if not self.stack_out:
            while self.stack_in:
                self.stack_out.append(self.stack_in.pop())
        
        return self.stack_out.pop() if self.stack_out else None
    
    def front(self):
        """Check front - Amortized O(1)"""
        if not self.stack_out:
            while self.stack_in:
                self.stack_out.append(self.stack_in.pop())
        
        return self.stack_out[-1] if self.stack_out else None
    
    def is_empty(self):
        return not self.stack_in and not self.stack_out
# Test
q = QueueUsingStacks()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue())  # 1
print(q.front())    # 2
print(q.dequeue())  # 2

Pouring stack_in into stack_out reverses the order, which turns LIFO into FIFO: the oldest element ends up on top of stack_out. The key rule is to transfer only when stack_out is empty. Transferring while stack_out still holds items would bury older elements under newer ones and break the order.

A single dequeue can cost O(n) when it triggers a transfer, but each element is moved from stack_in to stack_out exactly once in its lifetime. Over any sequence of n operations the total work is O(n), so the amortized cost per operation is O(1). Interviewers ask this question mainly to hear that argument.

Problem 3: Next Greater Element

Problem: Find the next greater element to the right for each element. Example:

[4, 5, 2, 10] → [5, 10, 10, -1]
[1, 2, 3, 4] → [2, 3, 4, -1]

def next_greater_element(arr):
    """
    Find next greater element for each element
    Time: O(n)
    Space: O(n)
    """
    n = len(arr)
    result = [-1] * n
    stack = []  # Store indices
    
    for i in range(n):
        # Current value is greater than stack top's value
        while stack and arr[stack[-1]] < arr[i]:
            idx = stack.pop()
            result[idx] = arr[i]
        
        stack.append(i)
    
    return result
# Test
arr = [4, 5, 2, 10, 8]
print(next_greater_element(arr))
# [5, 10, 10, -1, -1]

The stack holds indices whose answer is still unknown, and their values are always in decreasing order from bottom to top (a monotonic stack). When a new value arrives, every smaller value on top has just found its next greater element, so they are popped and answered. Whatever remains at the end has no greater element to its right and keeps -1. Storing indices rather than values is what lets you write the answer into the right slot, and it also handles duplicates.

The same pattern answers LeetCode 739 (Daily Temperatures), where the answer is the distance i - idx instead of the value, and LeetCode 84 (Largest Rectangle in Histogram), where popping a bar tells you how far it can extend. To find the next smaller element, flip the comparison; to find the previous greater element, look at what is left on the stack right before you push i.

Problem 3b: Sliding Window Maximum (monotonic deque)

Problem (LeetCode 239): for every window of size k, report the maximum.

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()          # indices, values decreasing from front to back
    result = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:   # smaller values can never be a max again
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:                # front index left the window
            dq.popleft()
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]

This is the monotonic stack with a second exit. The back of the deque behaves like the stack above: a new value removes every smaller value, because those can never be the maximum of any window that also contains the new one. The front removes the index that has slid out of the window. The front always holds the current maximum. Each index enters and leaves at most once, so the whole pass is O(n), against O(nk) for recomputing max() on every window.

Problem 4: BFS (Breadth-First Search)

from collections import deque
def bfs(graph, start):
    """
    Traverse graph using BFS
    """
    visited = set()
    queue = deque([start])
    visited.add(start)
    result = []
    
    while queue:
        node = queue.popleft()
        result.append(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return result
# Test
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
print(bfs(graph, 'A'))
# ['A', 'B', 'C', 'D', 'E', 'F']

The queue is what makes this breadth-first: nodes are processed in the order they were discovered, so every node at distance 1 from A comes out before any node at distance 2. That ordering is why BFS finds shortest paths in unweighted graphs. Replace popleft() with pop() and the same code becomes a depth-first traversal, still visiting every node but no longer in order of distance.

Marking a node visited when it is enqueued, not when it is dequeued, matters. If you mark on dequeue, a node reachable from several others can be added to the queue several times; the output stays correct but the queue can grow far beyond the number of nodes, which is how grid BFS solutions run out of time or memory. See BFS and DFS for shortest-path reconstruction and grid versions.

Usage Patterns

Stack Usage Patterns

Pattern	Description	Examples
Bracket/Tag Matching	Match opening and closing	HTML, JSON, expressions
Calculator	Evaluate postfix notation	`3 4 + 2 *` → 14
Function Call Stack	Simulate recursion	DFS, backtracking
Undo	Cancel recent actions	Ctrl+Z
Path Tracking	Remember previous states	Maze exploration

Queue Usage Patterns

Pattern	Description	Examples
BFS	Level-order traversal	Shortest path, tree levels
Task Queue	Process in order	Printer, call center
Scheduling	Round-robin	CPU scheduler
Sliding Window	Fixed-size window	Recent N items
Stream Processing	Sequential data	Log analysis

Advanced Topics

Priority Queue

Priority queue is a queue where elements with higher priority come out first.

import heapq
# Min heap (default)
pq = []
heapq.heappush(pq, 3)
heapq.heappush(pq, 1)
heapq.heappush(pq, 2)
print(heapq.heappop(pq))  # 1 (smallest)
print(heapq.heappop(pq))  # 2
print(heapq.heappop(pq))  # 3
# Max heap (use negative values)
pq = []
heapq.heappush(pq, -3)
heapq.heappush(pq, -1)
heapq.heappush(pq, -2)
print(-heapq.heappop(pq))  # 3 (largest)

Despite the name, a priority queue is not a queue in the FIFO sense: it is a binary heap where push and pop cost O(log n) and peeking at the smallest element (pq[0]) is O(1). Python’s heapq only provides a min-heap, hence the negation trick. When you push tuples such as (priority, item), equal priorities fall back to comparing the items, which raises TypeError if the items are, say, dicts; adding a counter as a tie-breaker, (priority, count, item), avoids that and also keeps equal-priority items in insertion order. C++ Priority Queue:

#include <queue>
#include <iostream>
using namespace std;
int main() {
    // Max heap (default)
    priority_queue<int> pq;
    pq.push(3);
    pq.push(1);
    pq.push(2);
    
    cout << pq.top() << endl;  // 3 (largest)
    pq.pop();
    cout << pq.top() << endl;  // 2
    
    // Min heap
    priority_queue<int, vector<int>, greater<int>> min_pq;
    min_pq.push(3);
    min_pq.push(1);
    min_pq.push(2);
    
    cout << min_pq.top() << endl;  // 1 (smallest)
    
    return 0;
}

C++ has the opposite default: priority_queue is a max-heap. The comparator semantics confuse people because greater<int> produces a min-heap. The comparator answers “does a belong below b?”, and the element that is “greatest” by that comparison sits on top. The same inversion applies to custom comparators for Dijkstra: to pop the smallest distance, the comparator must return a.dist > b.dist.

Deque - Double-Ended Queue

Deque allows insertion/deletion from both ends.

from collections import deque
dq = deque([1, 2, 3])
# Add/remove from rear
dq.append(4)        # [1, 2, 3, 4]
dq.pop()            # [1, 2, 3]
# Add/remove from front
dq.appendleft(0)    # [0, 1, 2, 3]
dq.popleft()        # [1, 2, 3]
# Check both ends
print(dq[0])   # 1 (front)
print(dq[-1])  # 3 (back)
# Rotate
dq.rotate(1)   # Right by 1 → [3, 1, 2]
dq.rotate(-1)  # Left by 1 → [1, 2, 3]

Troubleshooting

Issue 1: Pop from Empty Stack/Queue

# ❌ Error
stack = []
# stack.pop()  # IndexError: pop from empty list
# ✅ Solution: Check empty
if stack:
    value = stack.pop()
else:
    print("Stack is empty")
# ✅ Or exception handling
try:
    value = stack.pop()
except IndexError:
    print("Stack is empty")

Issue 2: Using list for Queue (Performance)

# ❌ Inefficient
queue = []
queue.append(1)
queue.pop(0)  # O(n)!
# ✅ Efficient
from collections import deque
queue = deque()
queue.append(1)
queue.popleft()  # O(1)

Issue 3: C++ stack/queue pop() Returns Nothing

// ❌ Error: pop() is void
// int value = stack.pop();  // Compile error
// ✅ Correct way
int value = stack.top();  // Get value
stack.pop();              // Remove

Choosing between a stack and a queue

Situation	Data Structure	Reason
Process recent items first	Stack	LIFO
Process in order	Queue	FIFO
Parenthesis matching	Stack	Match most recent opening
BFS	Queue	Level-order traversal
DFS	Stack	Depth-first search
Undo/Redo	Stack	Cancel recent actions

The question to ask is whether the item you need next is the one you saw most recently (stack) or the one that has waited longest (queue). The mistake that most often turns a correct Python solution into a time-limit failure is implementing the queue with a list and pop(0): every call shifts the remaining elements, so a BFS over n nodes becomes O(n²). Use collections.deque with popleft() for queues; a plain list is fine for stacks because append and pop work at the end.

Next: Hash Table and BFS/DFS, where the queue and stack from this post drive the two traversals.

Frequently Asked Questions (FAQ)

Q. Why use a monotonic stack for Next Greater Element instead of nested loops?

A. Nested loops scan to the right for every element, which is O(n²). A monotonic stack keeps indices whose next greater value is still unknown in decreasing order; when a larger value arrives, you pop and record answers for all smaller ones at once. Each index is pushed and popped at most once, so the whole pass is O(n).

Stacks and Queues in Interviews: LIFO/FIFO Patterns, Monotonic Stacks and Deques

Key takeaways

Introduction

Stack

What is a Stack?

Python Implementation (3 Methods)

C++ Implementation

Stack Time Complexity

Queue

What is a Queue?

Python Implementation

C++ Implementation

Problem Solving

Problem 1: Valid Parentheses

Problem 2: Implement Queue using Stacks

Problem 3: Next Greater Element

Problem 3b: Sliding Window Maximum (monotonic deque)

Problem 4: BFS (Breadth-First Search)

Usage Patterns

Stack Usage Patterns

Queue Usage Patterns

Advanced Topics

Priority Queue

Deque - Double-Ended Queue

Troubleshooting

Issue 1: Pop from Empty Stack/Queue

Issue 2: Using list for Queue (Performance)

Issue 3: C++ stack/queue pop() Returns Nothing

Choosing between a stack and a queue

Recommended Problems

Beginner

Intermediate

Advanced

Frequently Asked Questions (FAQ)

Q. Why use a monotonic stack for Next Greater Element instead of nested loops?

Key takeaways

Introduction

Stack

What is a Stack?

Python Implementation (3 Methods)

C++ Implementation

Stack Time Complexity

Queue

What is a Queue?

Python Implementation

C++ Implementation

Problem Solving

Problem 1: Valid Parentheses

Problem 2: Implement Queue using Stacks

Problem 3: Next Greater Element

Problem 3b: Sliding Window Maximum (monotonic deque)

Problem 4: BFS (Breadth-First Search)

Usage Patterns

Stack Usage Patterns

Queue Usage Patterns

Advanced Topics

Priority Queue

Deque - Double-Ended Queue

Troubleshooting

Issue 1: Pop from Empty Stack/Queue

Issue 2: Using list for Queue (Performance)

Issue 3: C++ stack/queue pop() Returns Nothing

Choosing between a stack and a queue

Recommended Problems

Beginner

Intermediate

Advanced

Related Articles

Frequently Asked Questions (FAQ)

Q. Why use a monotonic stack for Next Greater Element instead of nested loops?