Understanding Stacks and Queues in Data Structures

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:

The first person in line is served first.
New people join at the end.

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.