Stack
Imagine organizing a closet by placing winter clothes first, then summer clothes on top. When summer arrives, you grab the summer clothes first from the top without disturbing the items below.
A stack is a container that allows storing, accessing, and removing elements exclusively from one end called the top. This constraint means the element accessible at any moment is always the one most recently inserted. Stack enforces a default access pattern known as Last In First Out (LIFO).
Implementation
Stacks can be implemented using arrays or linked lists.
Core Operations
| Operation | Description |
|---|---|
| Stack() | Initialize an empty stack |
| push(item) | Insert element at the top |
| pop() | Remove and return the top element |
| peek() | Return the top elemant without removing |
| is_empty() | Check if the stack contains no elements |
| size() | Return the number of elements |
class Stack:
def __init__(self):
self._data = []
def is_empty(self):
return len(self._data) == 0
def push(self, element):
self._data.append(element)
def pop(self):
if self.is_empty():
raise IndexError("Stack is empty")
return self._data.pop()
def peek(self):
if self.is_empty():
raise IndexError("Stack is empty")
return self._data[-1]
def size(self):
return len(self._data)
if __name__ == "__main__":
s = Stack()
s.push("first")
s.push("second")
s.push("third")
print(s.size())
print(s.peek())
print(s.pop())
print(s.pop())
print(s.pop())
Queue
Think about waiting in line at a ticket counter. The first person in line gets served first, while newcomers join at the back.
A queue is a linear structure where insertion happens at one end (rear) and deletion happens at the other end (front). This gives queues their First In First Out (FIFO) characteristic. Unlike stacks, queues never allow operations in the middle of the structure. For a queue q = [a1, a2, ..., an], element a1 sits at the front and an sits at the rear.
Implementation
Queues can be built using arrays or linked lists.
Core Operations
| Operation | Description |
|---|---|
| Queue() | Create an empty queue |
| enqueue(item) | Add an element to the rear |
| dequeue() | Remove and return the front element |
| is_empty() | Check if the queue is empty |
| size() | Return the element count |
class Queue:
def __init__(self):
self._items = []
def is_empty(self):
return len(self._items) == 0
def enqueue(self, element):
self._items.insert(0, element)
def dequeue(self):
if self.is_empty():
raise IndexError("Queue is empty")
return self._items.pop()
def size(self):
return len(self._items)
if __name__ == "__main__":
q = Queue()
q.enqueue("apple")
q.enqueue("banana")
q.enqueue("cherry")
print(q.size())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
Deque
A deque (double-ended queue) combines properties of both stacks and queues. Elements can be added or removed from either end, making it more flexible than a standard queue.
Implementation
Core Operations
| Operation | Description |
|---|---|
| Deque() | Create an empty deque |
| add_front(item) | Insert at the front |
| add_rear(item) | Insert at the rear |
| remove_front() | Remove from the front |
| remove_rear() | Remove from the rear |
| is_empty() | Check if empty |
| size() | Return element count |
class Deque:
def __init__(self):
self._container = []
def is_empty(self):
return len(self._container) == 0
def add_front(self, element):
self._container.insert(0, element)
def add_rear(self, element):
self._container.append(element)
def remove_front(self):
if self.is_empty():
raise IndexError("Deque is empty")
return self._container.pop(0)
def remove_rear(self):
if self.is_empty():
raise IndexError("Deque is empty")
return self._container.pop()
def size(self):
return len(self._container)
if __name__ == "__main__":
dq = Deque()
dq.add_front(10)
dq.add_front(20)
dq.add_rear(30)
dq.add_rear(40)
print(dq.size())
print(dq.remove_front())
print(dq.remove_front())
print(dq.remove_rear())
print(dq.remove_rear())