C++ Stack: Last-In-First-Out

The C++ Stack is a container adapter that follows the LIFO (Last-In-First-Out) principle. Imagine a physical stack of plates: the last plate you place on the pile is the first one you must remove. In a C++ Stack, elements are added and removed from only one end, called the "top." This restricted access makes it an ideal structure for managing function calls, reversing strings, or implementing undo mechanisms.

1. The STL Stack Adapter

In the C++ Standard Template Library, the std::stack is not a standalone container but an **adapter**. This means it uses an underlying container (by default std::deque, but it can also use std::vector or std::list) to store data, while providing a specific LIFO interface. This design allows the C++ Stack to be flexible while ensuring high performance for its specific operations.

2. Core Operations

Interacting with a C++ Stack is straightforward because it only allows access to the top-most element. You cannot iterate through a stack or access elements by index; you must pop elements one by one to see what lies beneath.

Function Description
push(x)Inserts element x at the top.
pop()Removes the top-most element.
top()Returns a reference to the top element.
empty()Returns true if the stack is empty.
size()Returns the number of elements.

3. Time Complexity

Because the C++ Stack only interacts with one end of the container, all its primary operations are exceptionally fast. Whether you are pushing a new value or checking the top, the complexity remains constant regardless of how many items are already in the stack.

  • Push / Pop: $O(1)$
  • Top: $O(1)$
  • Empty / Size: $O(1)$

Practice MCQs on Stacks

1. Which operation is used to view the top element without removing it?
A) pop() | B) top() | C) peek_all()

2. What is the default underlying container for std::stack?
A) std::vector | B) std::list | C) std::deque

3. If you push 'A', then 'B', then 'C', what does top() return?
A) A | B) B | C) C