Introduction
When studying data structures, two of the most important linear structures after arrays and linked lists are Stacks and Queues.
They are widely used in programming, algorithm design, and even real-world systems like task scheduling, expression evaluation, and memory management.
What is a Stack?
A Stack is a linear data structure that follows the principle of LIFO (Last In, First Out). This means the last element added to the stack will be the first one removed β just like a stack of plates or books.
Real-Life Example
Imagine stacking books:
You put book A, then B, then C on top.
When you remove one, you take C first, because itβs on top.
Stack Representation
Top β [C]
[B]
[A]
The last element you pushed (C) will be the first one to pop out.
Stack Operations
| Operation | Description | Example | Time Complexity |
|---|
| push(x) | Add an element x to the top | push(10) | O(1) |
| pop() | Remove the top element | pop() β 10 | O(1) |
| peek() / top() | View the top element without removing it | peek() β 10 | O(1) |
| isEmpty() | Check if stack is empty | True / False | O(1) |
Python Implementation of Stack
Python does not have a built-in Stack class, but you can easily implement one using lists or collections.deque.
Example 1: Stack using List
class Stack:
def __init__(self):
self.items = []
def push(self, data):
self.items.append(data)
def pop(self):
if not self.is_empty():
return self.items.pop()
return "Stack is empty"
def peek(self):
if not self.is_empty():
return self.items[-1]
return "Stack is empty"
def is_empty(self):
return len(self.items) == 0
def display(self):
print("Stack:", self.items)
# Example usage
s = Stack()
s.push(10)
s.push(20)
s.push(30)
s.display()
print("Popped:", s.pop())
print("Top Element:", s.peek())
Output:
Stack: [10, 20, 30]
Popped: 30Top Element: 20
Real-Life Uses of Stack
Undo/Redo operations in text editors
Backtracking algorithms (like solving mazes, DFS in graphs)
Function call management (call stack in programming)
Expression evaluation (Postfix, Prefix conversion)
Web browser history (back button uses stack behavior)
What is a 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 removed β like a line of people waiting for tickets.
Real-Life Example
Imagine a queue at a ticket counter:
Queue Representation
Front β [A][B][C] β Rear
If A entered first, A will also leave first.
Queue Operations
| Operation | Description | Example | Time Complexity |
|---|
| enqueue(x) | Add an element x at the end | enqueue(10) | O(1) |
| dequeue() | Remove the element from the front | dequeue() β 10 | O(1) |
| peek() / front() | Get the front element | front() β 20 | O(1) |
| isEmpty() | Check if queue is empty | True / False | O(1) |
Python Implementation of Queue
You can use collections.deque for an efficient queue implementation.
from collections import deque
class Queue:
def __init__(self):
self.queue = deque()
def enqueue(self, data):
self.queue.append(data)
def dequeue(self):
if not self.is_empty():
return self.queue.popleft()
return "Queue is empty"
def peek(self):
if not self.is_empty():
return self.queue[0]
return "Queue is empty"
def is_empty(self):
return len(self.queue) == 0
def display(self):
print("Queue:", list(self.queue))
# Example usage
q = Queue()
q.enqueue(10)
q.enqueue(20)
q.enqueue(30)
q.display()
print("Dequeued:", q.dequeue())
print("Front Element:", q.peek())
Output:
Queue: [10, 20, 30]
Dequeued: 10Front Element: 20
Types of Queues
1. Simple Queue
Follows standard FIFO rule. (First In β First Out)
2. Circular Queue
The last position is connected to the first position to make a circle.
Used in memory-efficient systems.
3. Priority Queue
Each element is assigned a priority.
Elements with higher priority are dequeued first (not necessarily in order of arrival).
4. Double-Ended Queue (Deque)
Insertion and deletion can occur at both ends.
Real-Life Uses of Queues
Printer queue β Tasks are printed in the order they were received.
CPU scheduling β Processes wait for CPU time in a queue.
Call centers / Ticket counters β Requests handled in order.
Messaging systems β Messages stored in a queue until processed.
Breadth-First Search (BFS) in graph traversal.
Stack vs Queue
| Feature | Stack | Queue |
|---|
| Working Principle | LIFO (Last In, First Out) | FIFO (First In, First Out) |
| Insertion Point | Top | Rear |
| Deletion Point | Top | Front |
| Access | Only top element | Only front and rear elements |
| Example | Undo feature, recursion | Task scheduling, BFS |
| Python Structure | List / deque | deque |
When to Use Stack or Queue
| Situation | Use |
|---|
| Need to reverse data or backtrack | Stack |
| Need to process data in order of arrival | Queue |
| Need memory management or function call tracking | Stack |
| Need scheduling or event handling | Queue |
Summary
Stacks and Queues are both linear data structures that manage elements in specific order patterns.
Stack β LIFO, where the last item added is the first to be removed.
Queue β FIFO, where the first item added is the first to be removed.
Both structures are essential in programming, algorithms, and system design.
Python offers easy ways to implement both using lists or collections.deque.
Mastering them helps you understand more advanced topics like trees, graphs, and memory management.