Python Stack and Queue

Stacks and queues are data structures that help you store and manage your data in a particular manner, which is why they are ideal for solving specific kinds of problems. Here is a detailed breakdown:

Stack

A stack is a linear data structure that obeys the LIFO (Last In, First Out) principle. That is, the last one added to the stack is the first one to be removed.

Basic Operations

1. Push: Adds an element to the top of the stack.
2. Pop: Removes the top element from the stack.
3. Peek/Top: Retrieves the top element without removing it.
4. IsEmpty: Checks if the stack is empty.

Implementation in Python

Python does not have a built-in Stack class, but you can use:

1. Lists: Python’s lists can be used as stacks with append() for push and pop() for pop operations.
2. Collections.deque: A more efficient option for stacks.

Examples

Using Lists:

# Stack implementation using list
stack = []

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

print("Stack:", stack)  # Output: [10, 20, 30]

# Pop the top element
top = stack.pop()
print("Popped Element:", top)  # Output: 30
print("Stack after pop:", stack)  # Output: [10, 20]

# Peek the top element
if stack:
    print("Top Element:", stack[-1])  # Output: 20

Using deque:

from collections import deque

stack = deque()

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

print("Stack:", stack)  # Output: deque([10, 20, 30])

# Pop the top element
top = stack.pop()
print("Popped Element:", top)  # Output: 30
print("Stack after pop:", stack)  # Output: deque([10, 20])

# Peek the top element
if stack:
    print("Top Element:", stack[-1])  # Output: 20

Use Cases

• Function call stack
• Undo/redo operations in text editors
• Backtracking algorithms, e.g., solving a maze

Queue

A queue is a linear data structure that follows the FIFO (First In, First Out) principle. This means the first element added to the queue will be the first one to be removed.

Basic Operations

1. Enqueue: Add an element to the end of the queue.
2. Dequeue: Remove an element from the front of the queue.
3. Front/Peek: Retrieve the element at the front without removing it.
4. IsEmpty: Check if the queue is empty.

Implementation in Python

Python does not have a built-in Queue class but you can use:

1. Lists: append() for enqueue and pop(0) for dequeue (not efficient for large datasets).
2. Collections.deque: Efficient for queues as well as stacks.
3. Queue module: Provides thread-safe implementation.

Examples

Using Lists:

# Queue implementation using list
queue = []

# Enqueue elements
queue.append(10)
queue.append(20)
queue.append(30)

print("Queue:", queue)  # Output: [10, 20, 30]

# Dequeue the front element
front = queue.pop(0)
print("Dequeued Element:", front)  # Output: 10
print("Queue after dequeue:", queue)  # Output: [20, 30]

# Peek the front element
if queue:
    print("Front Element:", queue[0])  # Output: 20

Using deque:

from collections import deque

queue = deque()

# Enqueue elements
queue.append(10)
queue.append(20)
queue.append(30)

print("Queue:", queue)  # Output: deque([10, 20, 30])

# Dequeue the front element
front = queue.popleft()
print("Dequeued Element:", front)  # Output: 10
print("Queue after dequeue:", queue)  # Output: deque([20, 30])

# Peek the front element
if queue:
    print("Front Element:", queue[0])  # Output: 20

Using Queue Module:

from queue import Queue

queue = Queue()

# Enqueue elements
queue.put(10)
queue.put(20)
queue.put(30)

print("Queue Size:", queue.qsize())  # Output: 3

# Dequeue the front element
front = queue.get()
print("Dequeued Element:", front)  # Output: 10
print("Queue Size after dequeue:", queue.qsize())  # Output: 2

Use Cases

• Order processing systems
• Printer queues
• Breadth-First Search (BFS) in graphs

Key Differences Between Stack and Queue

Both stacks and queues are fundamental concepts that simplify many computational problems.