ReviseAlgo Logo

Standard Template Library (STL)

std::stack and std::queue

LIFO and FIFO container adaptors built on top of other containers

Interview: Classic data structures — DFS uses stack, BFS uses queue; always tested in graph/tree problems

std::stack and std::queue

std::stack and std::queue are container adaptors — they wrap another container and expose a restricted interface that enforces LIFO (Last In, First Out) for stack and FIFO (First In, First Out) for queue. They intentionally hide random access, forcing the correct usage pattern.

Stack (LIFO)

Operations: push(), pop(), top(), empty(), size(). Default underlying container: deque. Can also use vector (stack<int, vector<int>>) for better cache performance. Use cases: function call stack simulation, balanced bracket checking, expression evaluation, DFS traversal.

Queue (FIFO)

Operations: push(), pop(), front(), back(), empty(), size(). Default underlying container: deque. Use cases: BFS traversal, task scheduling, producer-consumer patterns, level-order tree traversal.

A Note on pop()

In both stack and queue, pop() removes the element but does NOT return it. To get the value and remove it, you must call top() (stack) or front() (queue) first, copy the value, then call pop(). This is intentional: returning by value and removing in one exception-safe step was not possible in the original STL design.

Interview Corner

Q: Why does stack::pop() not return the popped value?

A: Exception safety. If pop() returned by value and the copy constructor of the value threw, the element would be removed from the stack but the caller never received the value — data loss. By separating top() (read, no mutation) and pop() (remove, no return), both are individually exception-safe. In modern C++, this concern is lessened with move semantics, but the API remains for backward compatibility.

Q: How do you implement BFS using std::queue?

A: Initialize the queue with the start node. While the queue is not empty: dequeue front, process it, enqueue all unvisited neighbors. The queue ensures nodes at the same depth are processed before deeper nodes — classic level-order traversal. Use a visited set to avoid processing nodes multiple times.

Common Pitfalls

  • Calling pop() expecting the value: pop() returns void — always read with top()/front() before popping.
  • Calling top()/front() on empty container: Undefined behavior. Always check !stack.empty() before accessing the top/front element.

Best Practices

  • Use stack<T, vector<T>> for better cache performance when the stack grows mainly by push/pop from the back.
  • Always check empty() before calling top(), front(), or pop().