Stacks and Queues with Python examples

Stacks (LIFO)

A stack is a linear data structure that follows the Last-In, First-Out (LIFO) principle. This means the last element added to the stack is the first one to be removed. Think of a stack of plates: you add a plate to the top, and you remove a plate from the top.

Common Stack Operations:

Push: Add an element to the top of the stack.
Pop: Remove and return the element from the top of the stack.
Peek (or Top): Return the top element without removing it.
isEmpty: Check if the stack is empty.
Size: Get the number of elements in the stack.

In Python, lists can be used as a straightforward way to implement a stack. The append() method acts as push, and the pop() method (without an index) acts as pop from the top of the stack.

Stack Implementation using Python List:


stack = []

# Push operations
stack.append('''A''')
stack.append('''B''')
stack.append('''C''')
print(f"Stack after pushes: {stack}")

# Pop operation
top_element = stack.pop()
print(f"Popped element: {top_element}") # Output: C
print(f"Stack after pop: {stack}")

# Peek operation (accessing the last element)
if stack:
    peek_element = stack[-1]
    print(f"Top element (peek): {peek_element}") # Output: B

# isEmpty check
is_empty = not bool(stack)
print(f"Is stack empty? {is_empty}")

# Size
print(f"Stack size: {len(stack)}")

For a more robust stack implementation, especially in multi-threaded scenarios or if you want a dedicated API, Python'''s collections.deque can also be used efficiently.


from collections import deque

stack_deque = deque()

stack_deque.append('''X''') # Push
stack_deque.append('''Y''') # Push
print(f"Deque stack: {stack_deque}")

popped = stack_deque.pop() # Pop
print(f"Deque popped: {popped}")
print(f"Deque stack after pop: {stack_deque}")

Queues (FIFO)

A queue is a linear data structure that follows the First-In, First-Out (FIFO) principle. This means the first element added to the queue is the first one to be removed. Think of a queue of people waiting for a bus: the first person to join the queue is the first one to get on the bus.

Common Queue Operations:

Enqueue: Add an element to the rear (end) of the queue.
Dequeue: Remove and return the element from the front of the queue.
Peek (or Front): Return the front element without removing it.
isEmpty: Check if the queue is empty.
Size: Get the number of elements in the queue.

While Python lists can be used to implement a queue (append() for enqueue and pop(0) for dequeue), using pop(0) on a list is inefficient (O(n) time complexity) because all subsequent elements need to be shifted. For an efficient queue implementation, Python'''s collections.deque is highly recommended as it supports fast appends and pops from both ends (O(1) time complexity).

Queue Implementation using `collections.deque`:


from collections import deque

queue = deque()

# Enqueue operations
queue.append('''Task 1''') # Enqueue to the right (rear)
queue.append('''Task 2''')
queue.append('''Task 3''')
print(f"Queue after enqueues: {queue}")

# Dequeue operation
front_element = queue.popleft() # Dequeue from the left (front)
print(f"Dequeued element: {front_element}") # Output: Task 1
print(f"Queue after dequeue: {queue}")

# Peek operation
if queue:
    peek_front = queue[0]
    print(f"Front element (peek): {peek_front}") # Output: Task 2

# isEmpty check
is_empty = not bool(queue)
print(f"Is queue empty? {is_empty}")

# Size
print(f"Queue size: {len(queue)}")

Applications:

Stacks: Function call management (call stack), undo/redo operations, expression evaluation (e.g., converting infix to postfix), backtracking algorithms (e.g., maze solving).
Queues: Managing requests in servers (e.g., print queues, web server request handling), breadth-first search (BFS) in graphs, task scheduling, message queues in distributed systems.