Chapter 2: Data Structures (Stacks &
Queues) - Class 12 Computer Science
2.1 Introduction to Data Structures
A data structure is a way of organizing and storing data efficiently.
Types of Data Structures:
1. Linear Data Structures → Elements are arranged sequentially.
o Examples: Arrays, Lists, Stacks, Queues
2. Non-Linear Data Structures → Elements are connected in a hierarchical manner.
o Examples: Trees, Graphs
This chapter focuses on Stacks and Queues, two important linear data structures.
2.2 Stack Data Structure
A stack is a linear data structure that follows the LIFO (Last In, First Out) principle.
2.2.1 Stack Operations
1. Push (Insertion) → Adds an element to the top of the stack.
2. Pop (Deletion) → Removes the top element from the stack.
3. Peek (Top Element) → Returns the top element without removing it.
4. isEmpty() → Checks if the stack is empty.
5. isFull() → Checks if the stack is full (if implemented using an array).
2.2.2 Implementation of Stack in Python (Using List)
python
Copy
class Stack:
def __init__(self):
[Link] = []
def push(self, item):
[Link](item)
def pop(self):
if not self.is_empty():
return [Link]()
else:
return "Stack is empty"
def peek(self):
if not self.is_empty():
return [Link][-1]
else:
return "Stack is empty"
def is_empty(self):
return len([Link]) == 0
# Example Usage
s = Stack()
[Link](10)
[Link](20)
print([Link]()) # Output: 20
print([Link]()) # Output: 10
2.2.3 Stack Applications
Expression Evaluation (Postfix, Prefix, Infix)
Backtracking Algorithms (like solving mazes)
Undo/Redo Operations in text editors
Function Call Management in recursion
2.3 Queue Data Structure
A queue is a linear data structure that follows the FIFO (First In, First Out) principle.
2.3.1 Queue Operations
1. Enqueue (Insertion) → Adds an element at the rear.
2. Dequeue (Deletion) → Removes an element from the front.
3. Front (Peek) → Returns the front element without removing it.
4. isEmpty() → Checks if the queue is empty.
2.3.2 Implementation of Queue in Python (Using List)
python
Copy
class Queue:
def __init__(self):
[Link] = []
def enqueue(self, item):
[Link](item)
def dequeue(self):
if not self.is_empty():
return [Link](0)
else:
return "Queue is empty"
def front(self):
if not self.is_empty():
return [Link][0]
else:
return "Queue is empty"
def is_empty(self):
return len([Link]) == 0
# Example Usage
q = Queue()
[Link](10)
[Link](20)
print([Link]()) # Output: 10
print([Link]()) # Output: 20
2.3.3 Applications of Queue
Job Scheduling in Operating Systems
Managing Requests in Web Servers
Call Center Customer Service
Print Queue in Printers
2.4 Types of Queues
1. Simple Queue → Follows FIFO (Example: Normal Queue at a shop).
2. Circular Queue → Last position is connected to the first (Used in memory
management).
3. Deque (Double-Ended Queue) → Allows insertion and deletion from both ends.
4. Priority Queue → Elements are dequeued based on priority (Example: Emergency
rooms in hospitals).
Summary of Chapter 2
Stacks → LIFO, Push, Pop, Peek, Applications.
Queues → FIFO, Enqueue, Dequeue, Applications.
Different types of queues → Simple, Circular, Deque, Priority Queue.