Stack

About

Imagine a stack of dinner plates in a cafeteria. You can only place a new plate on the very top, and when you need a plate, you can only remove the one that is currently on the top.

Because of this, a Stack is known as a LIFO (Last In, First Out) data structure. The element that was added most recently is always the first one to be removed.

Complexities

• Time Complexity:

  • Push (Insertion): $O(1)$ (Adding an item to the top takes constant time)

  • Pop (Removal): $O(1)$ (Removing the top item takes constant time)

  • Peek/Top (View top item): $O(1)$

  • Search: $O(n)$ (In the worst case, you have to pop every item off to find something at the bottom)

• Space Complexity: $O(n)$ (Where $n$ is the number of elements currently stored in the stack)

Code Implementations

Python

if __name__ == "__main__":
    s = Stack()
    s.push(10)
    s.push(20)
    print("Top element (Peek):", s.peek())  # Expected: 20
    print("Popped element:", s.pop())       # Expected: 20
    print("Top element (Peek):", s.peek())  # Expected: 10
    print("Is stack empty?", s.is_empty())   # Expected: False

C++

int main() {
    Stack s;
    s.push(10);
    s.push(20);
    cout << "Top element (Peek): " << s.peek(); // Expected: 20
    s.pop();
    cout << "Top element after pop: " << s.peek(); // Expected: 10
    cout << (s.isEmpty() ? "Yes" : "No"); // Expected: No
}

Key Takeaways

• The Call Stack: Your programming language uses this exact data structure implicitly behind the scenes to track execution. When function A() calls function B(), function A is pushed onto the compiler's memory system call stack until B completes and pops off. This is precisely how recursion functions!
  
  

• Primary Use Cases:

  • Undo/Redo functionality in text editors (the last action typed is the first one undone).
    
    
  • Expression evaluation and parsing (like checking if brackets/parentheses are balanced in code compiler checks).
    
    
  • Backtracking algorithms, such as running a Depth-First Search (DFS) through a maze or graph layout.