Double Ended Queue (Deque) – 4 Marks
Definition:
A double ended queue (deque) is a linear data structure in which insertion and deletion
can be performed at both ends, i.e., front and rear.
Operations:
Insert at front
Insert at rear
Delete from front
Delete from rear
Types of Deque:
1. 1. Input-restricted deque – insertion allowed at one end only
2. 2. Output-restricted deque – deletion allowed at one end only
Application:
Used in scheduling algorithms, undo/redo operations, and sliding window problems.
Circular Queue with Applications – 4 marks
Definition:
A circular queue is a queue in which the last position is connected back to the first position,
forming a circle. This helps in better utilization of memory.
Key Concept:
When the rear reaches the end, it wraps around to the front if space is available.
Advantages:
Efficient memory utilization
Avoids false overflow
Applications:
CPU scheduling
Buffer management
Traffic signal systems
Stack PUSH and POP Operations with Example (6 marks)
Stack:
A stack is a linear data structure that follows LIFO (Last In, First Out) principle.
PUSH Operation
Definition:
PUSH inserts an element at the top of the stack.
Steps:
1. Check if stack is full (overflow)
2. Increment TOP
3. Insert element at TOP
POP Operation
Definition:
POP removes the element from the top of the stack.
Steps:
1. Check if stack is empty (underflow)
2. Remove element at TOP
3. Decrement TOP
Example
Initial stack (TOP = −1)
PUSH(10) → Stack: [10]
PUSH(20) → Stack: [10, 20]
PUSH(30) → Stack: [10, 20, 30] (TOP = 2)
POP() → Removes 30
Stack after POP: [10, 20]
Basic Queue Operations
1) ENQUEUE (Insertion)
ENQUEUE is the operation of adding an element at the REAR end of the queue.
Before insertion, check overflow condition (queue full).
Steps:
1. Check if rear == max − 1 → Queue Overflow
2. If queue is empty, set front = 0
3. Increment rear
4. Insert the element at queue[rear]
2) DEQUEUE (Deletion)
DEQUEUE is the operation of removing an element from the FRONT end of the
queue.
Before deletion, check underflow condition (queue empty).
Steps:
1. Check if front == -1 or front > rear → Queue Underflow
2. Remove the element at queue[front]
3. Increment front
Linked List:
A linked list is a linear data structure where elements (nodes) are stored in non-contiguous
memory locations. Each node contains data and a pointer to the next node. It allows
dynamic memory allocation and efficient insertion/deletion.
Types of Linked List:
1. Singly Linked List (SLL):
o Each node points to the next node.
o Traversal is forward only.
o Last node points to NULL.
2. Doubly Linked List (DLL):
o Each node has next and previous pointers.
o Traversal is forward and backward.
3. Circular Linked List (CLL):
o Last node points back to the first node, forming a circle.
o Can be singly or doubly linked.
o Traversal can start from any node.
Doubly Linked List (DLL):
A doubly linked list is a type of linked list in which each node contains:
1. Data – the value stored.
2. Next pointer – points to the next node.
3. Previous pointer – points to the previous node.
Features:
Allows forward and backward traversal.
The first node’s previous pointer and the last node’s next pointer are NULL.
Singly Linked List (SLL) and Doubly Linked List (DLL):
Feature Singly Linked List (SLL) Doubly Linked List (DLL)
Pointers in Node Only next pointer Next and previous pointers
Traversal Forward only Forward and backward
Memory Usage Less (one pointer per node) More (two pointers per node)
Slower if at the end or middle Faster, as previous node is directly
Insertion/Deletion
(need previous node) accessible
Complexity Simple to implement More complex to implement
First node’s previous and last
First and Last Node Last node points to NULL
node’s next are NULL