Module 2

Data Structures Linear and Non Linear

• Arrays: 1D and 2D array- Stack, Queue - Types of Queue: Circular
Queue, Double Ended Queue (deQueue), List: Singly linked lists,
Doubly linked lists, Circular linked lists. Binary Tree: Definition and
Properties - Tree Traversals- Binary Search Trees, Application,
Balanced Binary Trees-AVL Tree, Graphs: representation, Traversal:
BFS & DFS, Hashing
Arrays
• A collection of elements stored in contiguous memory locations
• All elements are of the same data type
• Accessed using a single index

• Examples
• int A[10]
• float marks[50]
Characteristics of Arrays
• Fixed size
• Contiguous memory allocation
• Direct access: A[i] (constant-time)
• Efficient for indexed access
• Inefficient for insertions/deletions in the middle
Array Memory Representation
• Index: 0 1 2 3 4
• Value: 10 20 30 40 50
• Address: (base + index * size)
• Base address = address of A[0]
• Address formula:
• LOC 𝐴 𝑖 = Base 𝐴 + 𝑖 × size of element
Array Types

• One-dimensional array
• Example: int A[5]
• Two-dimensional array
• Example: int B[3][4]
• Multi-dimensional arrays
• Example: int C[2][3][4]
Operations on Arrays

• Traversal
• Insertion
• Deletion
• Searching
• Updating
• Sorting
Searching in Arrays

• Linear Search
• Check every element
• Time: O(n)
• Binary Search
• Requires sorted array
• Time: O(log n)
Applications of Arrays

• Storing lists of values

• Matrices and mathematical computations
• Lookup tables
• Implementing other data structures:
• Heaps
• Hash tables
• Strings
• Graph adjacency matrices
1D Array
• Declaration Form
dataType arrayName[arraySize];
• Examples
int marks[50];
float price[10];
char name[20];
• Size must be a positive integer
• Size is usually fixed (static)
• dynamic memory allocation using malloc()
Example: int A[6];
• Index: 0 1 2 3 4 5
• Content: [ ] [ ] [ ] [ ] [ ] [ ]

• Intialization:
int A[6] = {5,10,20,25,30,35};
• int A[5];
• A[0] = 10;
• A[1] = 20;
• A[2] = 30;
• A[3] = 40;
• A[4] = 50;
Accessing Array Elements
• syntax: arrayName[index]

• Example:
• int A[3] = {4, 7, 9};
• printf("%d", A[1]);

• Output: 7
Sum of N numbers
#include <stdio.h>
int main()
{
int n, i;
int arr[100]; // Maximum size of array
int sum = 0;

// Get number of elements

printf("Enter number of elements: ");
scanf("%d", &n);
 // Input array elements
printf("Enter the elements: ");
Enter number of elements:
for(i = 0; i < n; i++)
5
{ Enter the elements:
scanf("%d", &arr[i]); 10 20 30 40 50
}
// Compute sum Sum of elements = 150
for(i = 0; i < n; i++) {
sum = sum + arr[i];
}
// Print result
printf("Sum of elements = %d\n", sum);
return 0;
}
2 D Array
• An array of arrays
• A matrix consisting of rows and columns
Declaration of 2D Array
• Syntax
dataType arrayName[rows][columns];

• int A[3][4]; // 3 rows, 4 columns

• float matrix[2][5]; // 2 rows, 5 columns
• char grid[10][10]; // 10x10 character array
Initialization of 2D Array
int A[2][3] = {
{1, 2, 3},
{4, 5, 6}
};

int B[2][3] = {1, 2, 3, 4, 5, 6};

int D[][3] = { {1, 2, 3}, {4, 5, 6} };

Accessing Elements in 2D Array
• Syntax
arrayName[row][column]
int A[2][3] = {
{1, 2, 3},
{4, 5, 6}
};

• A[0][1] // Row 0, Column 1 → value 2

• A[1][2] // Row 1, Column 2 → value 6

• Modifying
• A[1][1] = 10;
Reading and Printing a 2D Array
#include <stdio.h>
int main()
{
int A[2][3];
int rows = 2, cols = 3;
int i, j;
printf("Enter 6 elements for a 2x3 array:\n");
// Input
for(i = 0; i < rows; i++) {
for(j = 0; j < cols; j++) {
scanf("%d", &A[i][j]);
}
}
// Output
printf("The array is:\n");
for(i = 0; i < rows; i++) {
Enter 6 elements for a 2x3 array:
for(j = 0; j < cols; j++) { 123456
printf("%d ", A[i][j]); The array is:
} 123
printf("\n"); 456

return 0;
}
Lab 1 Practice exercises
1. Write a C program to find the element in an array
a) Linear Search
b) Binary Search
2. Write a C program to order the numbers in ascending order
a) Selection Sort
b) Insertion Sort
3. Write a C program to find the sum of numbers in 2D Array
4. Write a C program to find the element in 2D Array and display its
position
Stack
• Stack is a linear data structure
• In stacks, elements are stored one over another, and these
elements get removed in the reverse order of the arrival i.e. LIFO
( Last In First Out) concept is followed.
Operations on a stack
• INSERT operation on a stack is often called PUSH
• DELETE operation which does not take an element argument, is
called POP.
• All insertions and deletions occur at one end only, called TOP
TOP Index of the topmost element
Push Insert an element into the stack
Pop Remove an element from the stack
Peek / Top View top element without removing
Overflow Stack is full, cannot push
Underflow Stack is empty, cannot pop
Array implementation of a stack
• we can implement a stack of at most n elements with an array S(1 to
n)
• The array has an attribute [Link] that indexes the most recently
inserted element
• We can test to see whether the stack is empty by query operation
STACK-EMPTY
• If we attempt to pop an empty stack, we say the stack underflows,
which is normally an error.
• If [Link] exceeds n, the stack overflows.
Stack Insertion: push()

1. Checks if the stack is full.

2. If the stack is full, produces an error and exit.
3. If the stack is not full, increments top to point next empty space.
4. Adds data element to the stack location, where top is pointing.
Stack Insertion: push()
STACK_FULL() PUSH(data)
1. if top == MAXSIZE − 1 1. if NOT STACK_FULL()
2. return TRUE 2. top = top + 1
3. stack[top] = data
3. else
4. else
4. return FALSE 5. print "Stack is full"

stack[0 … MAXSIZE − 1] → array representing stack

O(1) Time
top → index of the top element
Initially: top = -1
Stack is full, OVERFLOW
Stack Deletion: pop()
1. Checks if the stack is empty.
2. If the stack is empty, produces an error and exit.
3. If the stack is not empty, accesses the data element at which top is
pointing.
4. Decreases the value of top by 1
5. Returns the accessed data
Stack Deletion: pop()
STACK_EMPTY() POP()
1. if top == −1 1. if STACK_EMPTY()
2. print "Stack Underflow"
2. return TRUE 3. else
3. else 4. data = stack[top]
4. return FALSE 5. top = top − 1
6. return data

O(1) Time
Stack is Empty, UNDERFLOW
PEEK() / TOP()
PEEK()
1. if STACK_EMPTY()
2. print "Stack is empty"
3. else
4. return stack[top]

• PEEK returns the top element without removing it

• Stack remains unchanged
• Useful to view current top element
• O(1) Time
Applications of Stacks
• Function calls: Stacks are used to keep track of the return addresses
of function calls, allowing the program to return to the correct
location after a function has finished executing.
• Recursion: Stacks are used to store the local variables and return
addresses of recursive function calls, allowing the program to keep
track of the current state of the recursion.
• Expression evaluation: Stacks are used to evaluate expressions in
postfix notation (Reverse Polish Notation).
• Syntax parsing: Stacks are used to check the validity of syntax in
programming languages and other formal languages.
• Memory management: Stacks are used to allocate and manage
memory in some operating systems and programming languages.
Expression Evaluation
• Three different ways to write arithmetic and logical expressions,
• Infix
• Prefix
• Postfix
Infix Notation
• The operator is written between the operands.
• operand operator operand

• A+B
• (3 + 5) * 2
• A+B*C

• Easy for humans to read and write

• Requires operator precedence and parentheses
• Computers find it harder to evaluate directly because they must
consider precedence and brackets.
Prefix Notation (Polish Notation)
• The operator is written before the operands.
• operator operand operand

• +AB
• *+352
• +A*BC

• No need for parentheses

• No ambiguity in evaluation
• Evaluation is easy using a stack (scan right → left)
Postfix Notation (Reverse Polish Notation)
• The operator is written after the operands.
• operand operand operator
• AB+
• 35+2*
• ABC*+
• No parentheses needed
• No operator precedence rules required
• Very efficient evaluation using a stack (scan left → right)
• Used in:
• Stack-based calculators
• Compilers
• Expression evaluation algorithms
Example 1 - Infix to Prefix (No Stack)
• Infix: (A + B) * C

• Handle brackets
• (A + B)
• Move + in front:
• +AB

• Now expression becomes:(+ A B) * C

• Move * in front:
• *+ABC

Final Prefix : * + A B C
Infix to Postfix Conversion using stack
Steps: (Infix → Prefix)
1. Reverse the infix expression
2. Swap ( with )
3. Convert the modified expression to postfix
4. Reverse the postfix result → that is the prefix

• Operator Precedence
• ^ highest
•*/
• + - lowest
Example 1 - Infix to Prefix Conversion using stack
• Infix Expression
• (A + B) * C

Step 1: Reverse the expression

• C*)B+A(

• Step 2: Swap parentheses

• C*(B+A)
Step 3: Convert to Postfix (using stack) Symbol Stack Output
C * ( B + A ) (from previous step)
C Empty C
Rules : * * C
•Operands → output
•( → push to stack ( *( C
•) → pop until ( B *( CB
•Operator:
• pop higher or equal precedence + *(+ CB
operators A *(+ CBA
• then push current operator
C B A + POP
) *
till (
Step 4: Reverse postfix to get Prefix
end Empty C B A + * POP
*+ABC
Example 2 (No Stack)
• Infix A + B * C

• Apply Operator precedence Rule

• * comes first:
• B*C→*BC

• Expression becomes:
• A + (* B C)
• Move + in front
• +A*BC
Final Prefix: + A * B C
Example 2 - Infix to Prefix Conversion using stack
• Step 1: Reverse the infix expression
• A+B*C → C*B+A

• Step 2: Swap parentheses

• There are no brackets, so the same:
• C*B+A
• Step 3: Convert to Postfix (using stack)
• Operator Precedence * +
• From previous step: C * B + A
Symbol Stack Output
C Empty C
* * C
B * CB
C B * (POP *,
+ +
then PUSH +)
A + CB*A
end Empty C B * A + POP

Step 4: Reverse postfix to get Prefix

+ A * B C
Example 3 (No Stack)
• Infix (A + B) * (C - D)

• Convert each bracket

• (A + B) → + A B
• (C - D) → - C D

• Expression becomes:
• (+ A B) * (- C D)

• Move * in front
• *+AB-CD
Example 3 - Infix to Prefix Conversion using
stack
• Infix 𝐴 + 𝐵 ∗ 𝐶 − 𝐷

• Step 1: Reverse the infix expression

(A + B) * (C - D)
↓
)D-C(*)B+A(

• Step 2: Swap parentheses

• (D-C)*(B+A)
• Step 3: Convert to Postfix using stack
• Operator precedence * + -
• From previous step: ( D - C ) * ( B + A )
Symbol Stack Output
( ( Nil
D ( D
- (- D
C (- DC
) Empty DC- POP till (
* * DC-
( *( DC-
B *( DC-B Step 4: Reverse postfix to
get Prefix
+ *(+ DC-B
* + A B - C D
A *(+ DC-BA
) * DC-BA+ POP till (
end Empty DC-BA+*
Example 4 (No Stack)
• A + (B * C - D)
• Handle the bracket
• B*C → *BC
• (* B C - D)

• Handle subtraction
• *BC-D → -*BCD
• So expression becomes: A + (- * B C D)

• Handle addition
• +A-*BCD

Prefix + A - * B C D
Example 4 - Infix to Prefix Conversion using
stack
• Infix 𝐴 + 𝐵 ∗ 𝐶 − 𝐷

• Step 1: Reverse the infix expression

• Original: A + (B * C - D)
• Reversed: ) D - C * B ( + A

• Step 2: Swap parentheses

• (D-C*B)+A
• Step 3: Convert to Postfix using stack
• Operator precedence * + -
• From Previous step: ( D - C * B ) + A
Symbol Stack Output
( ( Nil
D ( D Step 4: Reverse postfix
- (- D to get Prefix
+ A - * B C D
C (- DC
* (- * DC
B (- * DCB
) Empty D C B * - POP till (
+ + DCB*-
A + DCB*-A
end Empty DCB*-A+
Try yourself - Convert infix to prefix using stack
• A*B+C
• A+B–C
• (A + B) * C - D
• (A + B * C) / (D - E)
• (A + B) * (C - D / E)
Answers
• +*ABC
• -+ABC
• -*+ABCD
• /+A*BC-DE
• *+AB-C/DE
ALGORITHM InfixToPrefix(expression)
1. Reverse the expression
2. Replace '(' with ')' and ')' with '('
3. Create an empty stack S
4. Create an empty string OUTPUT
5. FOR each symbol X in the expression (from left to right)
IF X is an operand THEN
OUTPUT ← OUTPUT + X
ELSE IF X = '(' THEN
PUSH X onto stack S
ELSE IF X = ')' THEN
WHILE top of stack S ≠ '(' DO
OUTPUT ← OUTPUT + POP from S
END WHILE
POP '(' from stack S // discard it
ELSE IF X is an operator THEN
WHILE stack S is not empty AND
precedence(top of S) ≥ precedence(X) DO
OUTPUT ← OUTPUT + POP from S
END WHILE
PUSH X onto stack S

END FOR

6. WHILE stack S is not empty DO

OUTPUT ← OUTPUT + POP from S
END WHILE

7. Reverse OUTPUT

8. RETURN OUTPUT // this is the PREFIX expression

Convert infix to postfix using stack
Rules:
• Operands → add directly to output
• Left parenthesis ( → push to stack
• Right parenthesis ) →
pop from stack to output until ( is found
then discard (
• Operators:
• While stack is not empty and
precedence(top of stack) ≥ precedence(current operator)
→ pop to output
• Then push current operator
• End of expression → pop all remaining operators from stack to output
Example - infix to postfix using stack
Infix: 9 + (2 * 3)

Symbol Stack Output

9 — 9
+ + 9
( +( 9
2 +( 92
* +(* 92
3 +(* 923
) + 923*
end — 923*+
Algorithm Infix to Postfix (Using Stack)
BEGIN
Create an empty stack S
Create an empty string POSTFIX
FOR each symbol X in the infix expression (left to right) DO
IF X is an operand THEN
Append X to POSTFIX
ELSE IF X is '(' THEN
Push '(' onto stack S
ELSE IF X is ')' THEN
WHILE top of stack S is not '(' DO
Pop from S and append to POSTFIX
END WHILE
Pop '(' from stack S // discard it
ELSE IF X is an operator THEN
WHILE S is not empty AND
precedence(top of S) ≥ precedence(X) DO
Pop from S and append to POSTFIX
END WHILE
Push X onto stack S
END IF
END FOR
// Pop remaining operators
WHILE S is not empty DO
Pop from S and append to POSTFIX
END WHILE
PRINT POSTFIX
END
Try yourself - Convert infix to postfix using
stack
Infix Expression Postfix Expression

A*B+C AB*C+

A+B-C AB+C-

(A + B) * C - D AB+C*D-

(A + B * C) / (D - E) ABC*+DE-/

(A + B) * (C - D / E) AB+CDE/-*
Evaluation of Prefix Expression (Using Stack)
• The operator comes before operands, so operands must be available
before applying the operator, Scan the prefix expression from RIGHT to
LEFT

Logic:
• Create an empty stack
• Scan expression from right to left
• If operand → push onto stack
• If operator: Operand1 = first pop
• Pop two operands from stack Operand2 = second pop
• Apply operator Result = Operand1 operator Operand2
• Push the result back onto stack
• After complete scan, the top of stack is the result
Example 1 Prefix Evaluation (Using Stack)
• Prefix Expression + 9 * 2 3

Symbol (Right → Left) Stack Action

3 3 Push operand

2 3, 2 Push operand
Pop 2,3
* 6
2 × 3 = 6 → push
9 6, 9 Push operand
Pop 9,6
+ 15
9 + 6 = 15 push
Example 2 Prefix Evaluation (Using Stack)
• Prefix - * 4 5 6

Symbol (Right → Left) Stack Action

6 6 Push
5 6, 5 Push
4 6, 5, 4 Push
Pop 4,5
* 6, 20
Push 4 × 5 = 20
Pop 20,6
- 14
Push 20 − 6 = 14
Example 3: Prefix Evaluation (Using Stack)
• Prefix Expression -*+823/93
Symbol (Right → Left) Stack Action
3 3 Push operand
9 3, 9 Push operand
Pop 9,3
/ 3
Push 9 ÷ 3 = 3
3 3, 3 Push operand
2 3, 3, 2 Push operand
8 3, 3, 2, 8 Push operand
Pop 8,2
+ 3, 3, 10
Push 8 + 2 = 10
Pop 10,3
* 3, 30
Push 10 × 3 = 30
Pop 30,3
- 27
Push 30 − 3 = 27
Evaluation of Prefix Expression - Algorithm
Pseudo-Code:
FOR each symbol from right to left
IF operand
PUSH onto stack
ELSE
op1 ← POP
op2 ← POP
result ← op1 operator op2
PUSH result
END FOR
PRINT POP (final result)
Evaluation of Postfix Expression (Using Stack)
• Scan the postfix expression from LEFT to RIGHT, Since in postfix notation,
the operator comes after operands.

Logic:
• Create an empty stack
• Scan the expression left → right
• If operand → push onto stack
Operand2 = first pop
• If operator: Operand1 = second pop
• Pop two operands Result = Operand1 operator Operand2
• Apply the operator
• Push the result back onto stack
• After scanning the full expression, the top of the stack is the result
Example 1: Postfix Evaluation (Using Stack)
• Postfix Expression 2 3 4 * +

Symbol (Left → Right) Stack Action

2 2 Push
3 2, 3 Push
4 2, 3, 4 Push
* 2, 12 3×4
+ 14 2 + 12
Example 2: Postfix Evaluation (Using Stack)
• Postfix 5 6 2 + *

Symbol (Left → Right) Stack Action

5 5 Push
6 5, 6 Push
2 5, 6, 2 Push
+ 5, 8 6+2
* 40 5×8
Example 3: Postfix Evaluation (Using Stack)
• Postfix Expression 5 2 + 8 * 4 -

Symbol (Left → Right) Stack Action

5 5 Push operand
2 5, 2 Push operand
+ 7 5+2=7
8 7, 8 Push operand
* 56 7 × 8 = 56
4 56, 4 Push operand
- 52 56 − 4 = 52
Evaluation of Postfix Expression - Algorithm
Pseudo-Code:
FOR each symbol from left to right
IF operand
PUSH onto stack
ELSE
operand2 ← POP
operand1 ← POP
result ← operand1 operator operand2
PUSH result
END FOR
PRINT POP (final result)
Lab 4 Exercises
• Implement the following operations using stack
• Infix to prefix conversion
• Infix to postfix conversion
• Prefix Evaluation
• Postfix Evaluation
*Get the input from the user and print the final result to user
Queue
• A Queue is a linear data structure that follows the principle:
• FIFO – First In, First Out
• The element that is inserted first is removed first, just like people standing
in a line.
• The queue has a head (front) and a tail (rear)

Operations of a Queue:
• Enqueue – Insert an element at the rear (tail)
• Dequeue – Remove an element from the front (head)
• Peek / Front – View the front element without removing it
• IsEmpty – Check if the queue is empty
• IsFull – Check if the queue is full
Types of Queue
• Linear (Simple) Queue
• Circular Queue
• Double Ended Queue (deQueue)
• Priority Queue
Linear Queue (Simple Queue)
• Insertion is done at the REAR and deletion is done from the FRONT.
• Front → points to the first element
• Rear → points to the last element
• Initially: Front = -1, Rear = -1
• Queue Full (Overflow):
• Rear == MAX – 1
• Queue Empty (Underflow):
• Front == -1
Linear Queue Insertion
• Steps for Insertion
• Check Overflow
• If queue is empty:
• Set Front = 0
• Increment Rear
• Insert element at Queue[Rear]
Linear Queue Insertion
IF Rear == MAX - 1
PRINT "Queue Overflow"
ELSE
IF Front == -1
Front = 0
END IF
Rear = Rear + 1
Queue[Rear] = Item
END IF
Linear Queue
Insertion
Deletion in Linear Queue (DEQUEUE)
Steps for Deletion:
• Check Underflow
• Front == -1 OR Front > Rear
• Remove element at Queue[Front]
• Increment Front
• If Front > Rear, reset:
• Front = -1
• Rear = -1
Deletion in Linear Queue (DEQUEUE)
IF Front == -1 OR Front > Rear
PRINT "Queue Underflow"
ELSE
Item = Queue[Front]
Front = Front + 1
IF Front > Rear //Rear stays where the last insertion was
Front = -1
Rear = -1
END IF
END IF
Deletion in Linear Queue (DEQUEUE)
PEEK Operation in Linear Queue
• PEEK (also called FRONT) is an operation that returns the front
element of the queue without deleting it.
• It only looks at the element, it does not remove it.

• IF Front == -1 OR Front > Rear

• PRINT "Queue is Empty"
• ELSE
• RETURN Queue[Front]
• END IF
• Limitation:
• Wasted space after deletions (in array implementation)
• After deletions, empty spaces at the front cannot be reused.
• Use Case:
• Basic applications
 Circular Queue
• A Circular Queue is a variation of a queue in which the last position is
connected to the first position, forming a circle.
• It follows FIFO but eliminates the space wastage problem of a linear
queue.
• reuse empty spaces at the front of the array.
• Empty Queue: Front == -1
• Full Queue: (Rear + 1) % MAX == Front
• Without this formula, Rear would just keep moving
right and cause false overflow.
Full Queue
(Rear + 1) % MAX == Front

MAX = 5
Rear = 4 (last index)
(4 + 1) % 5
Rear = 5 % 5 = 0 -> Front
Overflow
Full Queue
(Rear + 1) % MAX == Front

MAX = 5
Rear = 1
(1 + 1) % 5
2 % 5 = 2 -> Front
Overflow
Insertion (ENQUEUE) in Circular Queue
Steps:
• Check Overflow
• If queue is empty:
• Front = 0
• Rear = 0
• Else
• Rear = (Rear + 1) % MAX
• Insert element at Queue[Rear]
Insertion (ENQUEUE) in Circular Queue
IF (Rear + 1) % MAX == Front
PRINT "Queue Overflow"
ELSE
IF Front == -1
Front = 0
Rear = 0
ELSE
Rear = (Rear + 1) % MAX
END IF
Queue[Rear] = Item
END IF
Deletion (DEQUEUE) in Circular Queue
Steps:
• Check Underflow
• Remove element at Queue[Front]
• If only one element:
• Front = -1
• Rear = -1
• Else
• Front = (Front + 1) % MAX
Deletion (DEQUEUE) in Circular Queue
IF Front == -1
PRINT "Queue Underflow"
ELSE
Item = Queue[Front]
IF Front == Rear
Front = -1
Rear = -1
ELSE
Front = (Front + 1) % MAX
END IF
END IF
 PEEK in Circular Queue
BEGIN
IF Front == -1 THEN
PRINT "Queue is Empty"
ELSE
PRINT Queue[Front]
END IF
END

•Linear queue pointers move only forward

•Circular queue pointers wrap around
Applications of circular queue
• Applications
• CPU Scheduling
• Memory Management
• Traffic systems
• Producer–Consumer problem

Advantages
• No memory wastage
• Efficient use of array
• Suitable for buffering and scheduling
Double Ended Queue (Deque)
• A Double Ended Queue (Deque) is a linear data structure in which insertion and
deletion can be performed at both ends — front and rear.
• It follows FIFO, but with more flexibility than a normal queue.
• can act as both Stack and Queue
• Flexible insertion and deletion
• Deque can be implemented using:
• Array
• Linked list
• Circular array (most common)
Initial Values:
• Front = -1
• Rear = -1
Operations on Deque
InsertFront Insert element at front
InsertRear Insert element at rear
DeleteFront Remove element from front
DeleteRear Remove element from rear
PeekFront View front element
PeekRear View rear element
Double Ended Queue - INSERT AT FRONT
BEGIN
IF Front == 0 AND Rear == MAX-1 OR Front == Rear+1 THEN
PRINT "Deque Overflow"
ELSE IF Front == -1 THEN // First element
Front = 0
Rear = 0
ELSE IF Front == 0 THEN // wrap
Front = MAX-1
ELSE
Front = Front - 1
END IF
Deque[Front] = Item
END
Double Ended Queue - INSERT AT REAR
BEGIN
IF Front == 0 AND Rear == MAX-1 OR Front == Rear+1 THEN
PRINT "Deque Overflow"
ELSE IF Front == -1 THEN
Front = 0
Rear = 0
ELSE IF Rear == MAX-1 THEN
Rear = 0
ELSE
Rear = Rear + 1
END IF
Deque[Rear] = Item
END
Double Ended Queue - DELETE FROM FRONT
BEGIN
IF Front == -1 THEN
PRINT "Deque Underflow"
ELSE
Item = Deque[Front]
IF Front == Rear THEN
Front = -1
Rear = -1
ELSE IF Front == MAX-1 THEN
Front = 0
ELSE
Front = Front + 1
END IF
END IF
END
Double Ended Queue - DELETE FROM REAR
BEGIN
IF Front == -1 THEN
PRINT "Deque Underflow"
ELSE
Item = Deque[Rear]
IF Front == Rear THEN
Front = -1
Rear = -1
ELSE IF Rear == 0 THEN
Rear = MAX-1
ELSE
Rear = Rear - 1
END IF
END IF
END
Double Ended Queue - PEEK FRONT
BEGIN
IF Front == -1 THEN
PRINT "Deque is Empty"
ELSE
PRINT Deque[Front]
END IF
END
Double Ended Queue - PEEK REAR
BEGIN
IF Front == -1 THEN
PRINT "Deque is Empty"
ELSE
PRINT Deque[Rear]
END IF
END
Types of Deque
1. Input-Restricted Deque
• Insertion allowed at one end only
• Deletion allowed at both ends
• Insert → Rear only
• Delete → Front and Rear

2. Output-Restricted Deque
• Insertion allowed at both ends
• Deletion allowed at one end only
• Insert → Front and Rear
• Delete → Front only
Applications of Deque
• Palindrome checking
• Undo/Redo operations
• CPU scheduling
• Sliding window algorithms
Palindrome checking using DEQUE
• Insert all characters into a deque
• Repeatedly:
• delete one character from front
• delete one character from rear
• compare them
• If all pairs match → palindrome

• Examples:
• NOON
• MADAM
• LEVEL
Palindrome checking using DEQUE
BEGIN
Read the string
Insert all characters into the deque
WHILE deque size > 1 DO
frontChar = deleteFront()
rearChar = deleteRear()
IF frontChar != rearChar THEN
PRINT "Not a Palindrome"
STOP
END IF
END WHILE
PRINT "Palindrome"
END
Lab 5 Exercises
1. Write a menu-driven C program for linear queue operations.
2. Write a C program to count the number of elements in a linear queue.
3. Write a C program to reverse a linear queue.
4. Write a menu-driven C program for circular queue.
5. Write a program to count elements in a circular queue.
6. Write a program to reverse a circular queue.
7. Write a menu driven C program to implement deque using array.
• Write functions for:
• insertFront()
• insertRear()
• deleteFront()
• deleteRear()
• display deque elements
• Peekfront()
• Peekrear()
8. Write a program to implement input-restricted deque.
9. Write a C program to implement output-restricted deque.
10. Write a C program to check palindrome using deque