Stacks

Understanding stacks as a data structure.

What are Stacks?

A stack follows the LIFO (Last In, First Out) principle, which means the last element added to the stack is the first one to be removed. Imagine a stack of plates—when you add a plate, it goes on top, and when you remove one, it’s also from the top. That’s how stacks work.

Types of Stacks

While the basic concept of a stack is the same, there are variations:

  1. Static Stack: Fixed size, implemented using arrays.
  2. Dynamic Stack: Can grow or shrink in size, typically implemented using linked lists.

How Stacks Work in Memory

Stacks are typically implemented using arrays or linked lists. In memory, they grow from one end—either upwards or downwards, depending on how the system manages memory. When you push an element onto the stack, it’s added to the top of the stack. When you pop, the top element is removed.

Common Stack Operations

Here are the main operations you'll use with stacks:

  • Push: Add an element to the top of the stack. O(1)
  • Pop: Remove the top element. O(1)
  • Peek/Top: Look at the top element without removing it. O(1)
  • IsEmpty: Check if the stack is empty. O(1)

Applications of Stacks

Stacks are everywhere. Here are a few places where they shine:

  • Expression evaluation and conversion (e.g., infix to postfix).
  • Backtracking in algorithms like DFS or solving mazes.
  • Undo functionality in text editors.
  • Function call management in recursion.

Code Examples

Here’s how stacks can be implemented in C++, Python, and Java. Each language has its way of dealing with stacks, but the underlying concept remains the same.

# Using a list as a stack
stack = []

# Push elements
stack.append(10)
stack.append(20)
stack.append(30)

# Pop the top element
stack.pop()

# Peek the top element
print("Top element:", stack[-1] if stack else "Stack is empty")

# Check if stack is empty
if not stack:
    print("Stack is empty.")
else:
    print("Stack is not empty.")

Problems to Solve

Important Problems on Stacks

Resources