Stacks and queues are abstract data structures with unique insertion and deletion rules that make them ideal for specific types of data processing tasks. Let’s go over the fundamentals of each, how to implement them with arrays and linked lists, and look at the deque (double-ended queue), which provides more flexibility.
Stacks
A stack is a Last-In-First-Out (LIFO) data structure. Think of it like a stack of plates: you can only take the top plate off or add a new plate to the top.
- Push: Add an element to the top of the stack.
- Pop: Remove the element at the top of the stack.
- Peek: Get the element at the top without removing it.
Stack Implementation Using Arrays
Here’s a Python implementation using a list as the underlying array:
class StackArray:
def __init__(self):
self.stack = []
def push(self, data: int):
"""Push an element onto the stack."""
self.stack.append(data)
def pop(self) -> int:
"""Remove and return the top element. Raises IndexError if stack is empty."""
if self.is_empty():
raise IndexError("Pop from empty stack")
return self.stack.pop()
def peek(self) -> int:
"""Return the top element without removing it. Raises IndexError if stack is empty."""
if self.is_empty():
raise IndexError("Peek from empty stack")
return self.stack[-1]
def is_empty(self) -> bool:
return len(self.stack) == 0
# Usage
stack = StackArray()
stack.push(10)
stack.push(20)
print("Top element:", stack.peek()) # Output: Top element: 20
print("Popped element:", stack.pop()) # Output: Popped element: 20
Stack Implementation Using Linked Lists
A linked list stack implementation provides a way to handle dynamic memory allocation, which may be more efficient for larger, unknown stack sizes.
class Node:
def __init__(self, data: int):
self.data = data
self.next = None
class StackLinkedList:
def __init__(self):
self.head = None
def push(self, data: int):
"""Push an element onto the stack."""
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def pop(self) -> int:
"""Remove and return the top element. Raises IndexError if stack is empty."""
if self.is_empty():
raise IndexError("Pop from empty stack")
data = self.head.data
self.head = self.head.next
return data
def peek(self) -> int:
"""Return the top element without removing it. Raises IndexError if stack is empty."""
if self.is_empty():
raise IndexError("Peek from empty stack")
return self.head.data
def is_empty(self) -> bool:
return self.head is None
# Usage
stack = StackLinkedList()
stack.push(10)
stack.push(20)
print("Top element:", stack.peek()) # Output: Top element: 20
print("Popped element:", stack.pop()) # Output: Popped element: 20
Queues
A queue is a First-In-First-Out (FIFO) data structure, often compared to a line of people: the first person in line is the first to be served.
- Enqueue: Add an element to the end of the queue.
- Dequeue: Remove the element from the front of the queue.
- Peek: Get the front element without removing it.
Queue Implementation Using Arrays
An array-based queue can be challenging due to shifting elements after dequeuing, but using a fixed starting point can simplify it.
class QueueArray:
def __init__(self):
self.queue = []
def enqueue(self, data: int):
"""Add an element to the end of the queue."""
self.queue.append(data)
def dequeue(self) -> int:
"""Remove and return the front element. Raises IndexError if queue is empty."""
if self.is_empty():
raise IndexError("Dequeue from empty queue")
return self.queue.pop(0) # Shift remaining elements
def peek(self) -> int:
"""Return the front element without removing it. Raises IndexError if queue is empty."""
if self.is_empty():
raise IndexError("Peek from empty queue")
return self.queue[0]
def is_empty(self) -> bool:
return len(self.queue) == 0
# Usage
queue = QueueArray()
queue.enqueue(10)
queue.enqueue(20)
print("Front element:", queue.peek()) # Output: Front element: 10
print("Dequeued element:", queue.dequeue()) # Output: Dequeued element: 10
Queue Implementation Using Linked Lists
A linked list-based queue simplifies operations as there is no shifting of elements.
class Node:
def __init__(self, data: int):
self.data = data
self.next = None
class QueueLinkedList:
def __init__(self):
self.front = None
self.rear = None
def enqueue(self, data: int):
"""Add an element to the end of the queue."""
new_node = Node(data)
if self.is_empty():
self.front = self.rear = new_node
else:
self.rear.next = new_node
self.rear = new_node
def dequeue(self) -> int:
"""Remove and return the front element. Raises IndexError if queue is empty."""
if self.is_empty():
raise IndexError("Dequeue from empty queue")
data = self.front.data
self.front = self.front.next
if self.front is None: # Queue is now empty
self.rear = None
return data
def peek(self) -> int:
"""Return the front element without removing it. Raises IndexError if queue is empty."""
if self.is_empty():
raise IndexError("Peek from empty queue")
return self.front.data
def is_empty(self) -> bool:
return self.front is None
# Usage
queue = QueueLinkedList()
queue.enqueue(10)
queue.enqueue(20)
print("Front element:", queue.peek()) # Output: Front element: 10
print("Dequeued element:", queue.dequeue()) # Output: Dequeued element: 10
Deques (Double-Ended Queues)
A deque allows insertions and deletions at both ends, making it more versatile than a standard queue.
Deque Implementation Using collections.deque
Python’s collections.deque is optimized for operations on both ends, making it an ideal choice for implementing a deque.
from collections import deque
# Initialize a deque
dq = deque()
# Add to both ends
dq.append(10) # Add to the right end
dq.appendleft(20) # Add to the left end
# Remove from both ends
dq.pop() # Remove from the right end
dq.popleft() # Remove from the left end
# Usage
dq = deque()
dq.append(10)
dq.appendleft(20)
print("Deque after appending:", dq) # Output: deque([20, 10])
dq.pop()
print("Deque after popping from right:", dq) # Output: deque([20])
dq.popleft()
print("Deque after popping from left:", dq) # Output: deque([])