Back to all concepts
Intermediate 10 min

Stack and Queue

Learn std::stack and std::queue container adapters for LIFO and FIFO data structures

Master stack and queue container adapters that enforce specific access patterns for cleaner, safer code.

A Simple Example 

#include <iostream>
#include <stack>
#include <queue>
#include <string>

int main() {
    // std::stack - LIFO (Last In, First Out)
    std::stack<int> plates;

    plates.push(1);  // Add to top
    plates.push(2);
    plates.push(3);

    std::cout << "Top plate: " << plates.top() << "\n";  // 3 (last added)

    plates.pop();  // Remove from top
    std::cout << "After pop, top: " << plates.top() << "\n";  // 2

    std::cout << "Stack size: " << plates.size() << "\n";

    // std::queue - FIFO (First In, First Out)
    std::queue<std::string> line;

    line.push("Alice");  // Add to back
    line.push("Bob");
    line.push("Charlie");

    std::cout << "\nFront of line: " << line.front() << "\n";  // Alice (first added)
    std::cout << "Back of line: " << line.back() << "\n";      // Charlie (last added)

    line.pop();  // Remove from front
    std::cout << "After serving, front: " << line.front() << "\n";  // Bob

    return 0;
}

Breaking It Down

std::stack - LIFO (Last In, First Out)

  • What it is: Container adapter restricting access to one end
  • Like a stack of plates - only access the top one
  • Operations: push(), pop(), top(), size(), empty()
  • Use for: Function call stack, undo operations, depth-first search

std::queue - FIFO (First In, First Out)

  • What it is: Container adapter with front and back access
  • Like a line at a store - first person in line is served first
  • Operations: push(), pop(), front(), back(), size(), empty()
  • Use for: Task scheduling, message queues, breadth-first search

Container Adapters - Intentional Limitations

  • What they are: Wrappers around deque/vector/list that restrict operations
  • Cannot iterate through elements or access middle elements
  • This restriction prevents bugs by enforcing the pattern
  • Remember: If you need random access, you don't want stack/queue

pop() Returns Void

  • Why: Exception safety - if construction throws, value is lost
  • Pattern: Call top()/front() to get value, then pop() to remove
  • Always check empty() before calling pop()
  • Remember: pop() on empty container is undefined behavior

Why This Matters

  • Stacks and queues are fundamental data structures that model common patterns.
  • Stacks handle function calls, undo/redo operations, and expression evaluation.
  • Queues manage task scheduling, message processing, and breadth-first algorithms.
  • Understanding these patterns makes your code clearer and more maintainable.

Critical Insight

Stacks and queues deliberately hide functionality to prevent mistakes. They're built on top of deque or vector, but you can't access elements in the middle or iterate through them.

This restriction isn't a limitation - it's a feature! By limiting what you can do, the compiler can catch logic errors.

If you find yourself wishing you could access the middle, you probably need a different container.

Best Practices

Always check empty() before pop(): Calling pop() on empty stack/queue is undefined behavior. Check first.

Use stack for LIFO patterns: Undo/redo, expression evaluation, depth-first traversal.

Use queue for FIFO patterns: Task processing, breadth-first traversal, message handling.

Get value before pop(): Call top()/front() to get the value, then pop() to remove it.

Common Mistakes

Calling pop() without checking empty(): Both stack and queue's pop() returns void and calling it on empty container is undefined behavior.

Confusing top/front/back: Stack uses top(), queue uses front() and back(). They're different methods.

Expecting pop() to return value: pop() returns void for exception safety. Use top()/front() first.

Debug Challenge

This undo system needs LIFO behavior (last action undone first). Click the highlighted line to fix it:

1 #include <iostream>
2 #include <queue>
3
4 int main() {
5 std::queue<std::string> undoStack;
6 undoStack.push("Action 1");
7 undoStack.push("Action 2");
8 // Undo last action first
9 return 0;
10 }

Quick Quiz

  1. What's the time complexity of stack::push() and queue::push()?
O(1) for both
O(log n) for both
O(n) for both
  1. Which container is best for implementing a function call stack?
std::stack
std::queue
std::vector

Practice Playground

Time to try out what you just learned! Play with the example code below, experiment by making changes and running the code to deepen your understanding.

Lesson Progress

  • Fix This Code
  • Quick Quiz
  • Practice Playground - run once