Stacks

Stacks:

Definition,
Array representation of stacks,
Linked representation of stacks,
Stack as ADT,

Definition

Array Representation of Stacks

Linked Representation of Stacks

In the linked representation of stacks, a singly linked list is used to implement the
stack. Each node in the list contains two fields:

1.​ INFO – stores the data (element of the stack)

2.​ LINK – stores the address (pointer) to the next node

The pointer TOP is used to represent the top of the stack. It is equivalent to the
START pointer in linked lists. The last node in the list has its LINK field as NULL,
which indicates the bottom of the stack.

This type of implementation is called a linked stack.

Basic Operations

Ju huPUSH operation – Inserting a new element at the top of the stack is done
by inserting a node at the beginning of the linked list.​

1.​ POP operation – Deleting an element from the top of the stack is done by
removing the first node of the list.​

Advantages over Array Representation

 ●​ In array-based stacks, a maximum size MAXSTK must be defined, and care must
be taken to avoid OVERFLOW (when TOP = MAXSTK) and UNDERFLOW (when
TOP = 0).​

●​ Linked stacks do not require MAXSTK. The size is not fixed and can grow or
shrink dynamically, limited only by the system's available memory.​

●​ OVERFLOW can only occur if the AVAIL list (free storage list) is empty, i.e.,
when there’s no free node left in memory.​

Procedure for PUSH Operation (PUSH_LINKSTACK)

To push an item into the linked stack:

Procedure: PUSH_LINKSTACK(INFO, LINK, TOP, AVAIL, ITEM)

1. [Check if space is available]​

If AVAIL = NULL​
Write: OVERFLOW and Exit​
​
2. [Remove node from AVAIL list]​
Set NEW := AVAIL​
Set AVAIL := LINK[AVAIL]​
​
3. [Assign ITEM to INFO field of new node]​
Set INFO[NEW] := ITEM​
​
4. [Link new node to the current top]​
Set LINK[NEW] := TOP​
​
5. [Make new node the new TOP]​
 Set TOP := NEW​
​
6. Exit

Procedure for POP Operation (POP_LINKSTACK)

To delete an item from the top of the linked stack:

Procedure: POP_LINKSTACK(INFO, LINK, TOP, AVAIL, ITEM)

1. [Check if stack is empty]​

If TOP = NULL​
Write: UNDERFLOW and Exit​
​
2. [Retrieve item from the top node]​
Set ITEM := INFO[TOP]​
​
3. [Move TOP to the next node]​
Set TEMP := TOP​
Set TOP := LINK[TOP]​
​
4. [Return removed node to AVAIL list]​
Set LINK[TEMP] := AVAIL​
Set AVAIL := TEMP​
​
5. Exit

Notes:
 ●​ AVAIL list is a list of free nodes available in memory. Every time a node is
deleted from the stack, it is returned to the AVAIL list.
●​ TOP = NULL is used to check for underflow.
●​ AVAIL = NULL is used to check for overflow.

This representation is efficient in memory management and avoids unnecessary

restrictions of fixed size. It is preferred when the maximum number of stack elements
is not known in advance.

Stack as an Abstract Data Type (ADT)

A stack is a linear data structure that follows the Last-In-First-Out (LIFO)

principle. This means the last element inserted into the stack is the first one to be
removed.

In the context of Abstract Data Type (ADT), a stack is defined by its behavior (what
operations it supports), not by its implementation (how it is implemented using arrays or
linked lists).

Definition of Stack ADT

A Stack ADT is a collection of elements with two main operations:

1.​ PUSH(x) – Inserts element x at the top of the stack.

2.​ POP() – Removes the topmost element from the stack.

Additionally, many stack implementations support:

●​ PEEK() or TOP() – Returns the top element without removing it.

●​ IS_EMPTY() – Checks whether the stack is empty.
●​ IS_FULL() – Checks whether the stack is full (in array implementation).

Properties of Stack ADT

●​ Access is limited: Only the top element is accessible.

 ●​ Insertion and deletion both happen at one end – the top.
●​ The order in which data is retrieved is the reverse of the order in which it was
added.
●​ A stack can be bounded (fixed size – array implementation) or unbounded (linked
list implementation).

Abstract Representation

Stack S:

●​ Initially: S = empty
●​ After PUSH(x): x becomes the new top
●​ After POP(): the previous element becomes the top

Let the stack be S = [a, b, c] (with 'c' on top)

●​ After PUSH(d): S = [a, b, c, d]

●​ After POP(): S = [a, b, c]

Real-Life Analogies

●​ A stack of plates
●​ Undo operation in text editors
●​ Browser backtracking (Back button in browsers)

Applications of Stack ADT

●​ Expression evaluation and conversion (infix to postfix)

●​ Syntax parsing in compilers
●​ Function call and recursion handling
●​ Depth-first search in graphs
●​ Backtracking algorithms (e.g., maze solving)
Arithmetic Expressions:
Arithmetic Expressions:

Polish Notation,
Conversion of infix expression to postfix expression,
Evaluation of Postfix expression,
Application of Stacks,
Recursion,
Towers of Hanoi,
Implementation of recursive procedures by stack.

Arithmetic Expressions and Polish Notation (Postfix)

Let Q be an arithmetic expression that contains constants and binary operations. To

evaluate such an expression efficiently, we can convert it into Reverse Polish Notation
(RPN), also called Postfix Notation.

In postfix notation, operators come after their operands. It eliminates the need for
parentheses and operator precedence during evaluation, and the evaluation becomes
straightforward using a stack.

Operator Precedence Assumed

To handle arithmetic expressions in infix form, we follow these three levels of

precedence:

●​ Highest: Exponentiation (↑)

●​ Next Highest: Multiplication (*) and Division (/)
●​ Lowest: Addition (+) and Subtraction (–)

Note: The exponentiation symbol ↑ is used as in BASIC language.​

For simplicity, unary operators (like leading minus) are excluded.​
Also, operations with the same precedence level are assumed to be
evaluated from left to right, even for exponentiation (though not standard
in some languages).

Example
Evaluate the infix expression (without parentheses):

2 ↑ 3 + 5 * 2 ↑ 2 – 12 / 6

Step 1: Evaluate Exponentiations

●​ 2 ↑ 3 = 8
●​ 2 ↑ 2 = 4​
Expression becomes:

8 + 5 * 4 – 12 / 6

Step 2: Evaluate Multiplication and Division

●​ 5 * 4 = 20
●​ 12 / 6 = 2​
Expression becomes:

8 + 20 – 2

Step 3: Evaluate Addition and Subtraction

●​ 8 + 20 = 28
●​ 28 – 2 = 26

Final Result: 26

Here are simple, clear notes on Polish Notation as per your syllabus (Chapter 6.5),
written in a way that's easy to understand and remember:

Polish Notation (Prefix and Postfix)

1. Infix Notation

●​ This is the standard way we write expressions.

●​ The operator is written between operands.​
Example: A + B, C * D
 ●​ It requires parentheses or operator precedence rules to decide the order of
operations.​
For example:​
(A + B) * C ≠ A + (B * C)

2. Polish Notation (Prefix Notation)

●​ In prefix notation, the operator comes before the operands.​

Example: + A B or * + A B C
●​ No need for parentheses — the order of operations is fixed by the position of
operators and operands.
●​ Named after Polish mathematician Jan Lukasiewicz.
●​ Example conversions:
○​ (A + B) * C → * + A B C
○​ A + (B * C) → + A * B C
○​ (A + B)/(C – D) → / + A B – C D

3. Reverse Polish Notation (Postfix Notation)

●​ In postfix notation, the operator comes after the operands.​

Example: A B +, A B C + *
●​ Also does not need parentheses.
●​ Postfix is commonly used in computers and calculators because it is easy to
evaluate using a stack.

Here are professionally structured notes on Transforming Infix Expressions to

Postfix — aligned with academic standards and suitable for handouts or teaching
material.

Transforming Infix Expressions into Postfix Expressions

Introduction
In arithmetic expressions, the infix notation is commonly used, where the operator
appears between operands (e.g., A + B). However, this form is not suitable for
computers when evaluating expressions because it requires handling operator
precedence, associativity, and parentheses.

To simplify evaluation, we convert infix expressions to postfix notation (also called

Reverse Polish Notation), where operators follow operands (e.g., A B +). This form
eliminates the need for parentheses and makes the expression evaluation
straightforward using stacks.

Algorithm Overview

The algorithm uses a stack to hold operators and left parentheses during scanning. The
resulting postfix expression is constructed from left to right using operands and
operators removed from the stack.

Preprocessing:

●​ Push a left parenthesis ( onto the stack.

●​ Append a right parenthesis ) to the end of the infix expression Q.

Algorithm: POLISH(Q, P)

Input: Infix expression Q​

Output: Equivalent postfix expression P

Steps:

1.​ Push ( onto the stack.

2.​ Append ) to the end of Q.
3.​ Scan Q from left to right. For each symbol:
○​ Operand: Add directly to P.
○​ Left Parenthesis (: Push to stack.
○​ Operator ⊗:​
a. Repeatedly pop from stack and add to P each operator that has same
or higher precedence than ⊗.​
b. Push ⊗ onto the stack.
 ○​ Right Parenthesis ):​
a. Pop from the stack and add to P until a left parenthesis is
encountered.​
b. Discard the left parenthesis (do not add to P).
4.​ When the stack becomes empty, the algorithm is complete.​

Example

Infix Expression:​
A + ( B * C – ( D / E ↑ F ) * G ) * H

Step 1 – Add parentheses:​

( A + ( B * C – ( D / E ↑ F ) * G ) * H )

Postfix Conversion:​
Using the algorithm, we get:

Infix to Postfix Conversion Table

Step Symbol Scanned STACK Expression P (Postfix)

1 A ( A

2 + (+ A

3 ( (+( A

4 B (+( AB
5 * (+(* AB

6 C (+(* ABC

7 – (+(– ABC*

8 ( (+(–( ABC*

9 D (+(–( ABC*D

10 / (+(–(/ ABC*D

11 E (+(–(/ ABC*DE

12 ↑ (+(–(/↑ ABC*DE

13 F (+(–(/↑ ABC*DEF

14 ) (+(– ABC*DEF↑/

15 * (+(–* ABC*DEF↑/

16 G (+(–* ABC*DEF↑/G

17 ) (+ ABC*DEF↑/G*–
 18 * (+* ABC*DEF↑/G*–

19 H (+* ABC*DEF↑/G*–H

20 ) ABC*DEF↑/G*–H*+

​
Postfix Expression:​
A B C * D E F ↑ / G * – H * +

Advantages of Postfix Notation

●​ No need for parentheses to indicate order.

●​ Evaluation is straightforward using a stack.
●​ Ideal for compiler implementation and expression parsing.

Evaluation of a Postfix Expression

A postfix expression (also called Reverse Polish Notation) is an arithmetic expression

where the operator appears after its two operands.

Example:​
Infix: 5 * (6 + 2) – 12 / 4​
Postfix: 5 6 2 + * 12 4 / –

Algorithm to Evaluate Postfix Expression

Let P be the postfix expression.

Steps:

1.​ Add a right parenthesis ) at the end of P (acts as a sentinel).

 2.​ Scan P from left to right, and for each symbol do:
○​ If the symbol is an operand, push it onto the stack.
○​ If the symbol is an operator (like +, *, /), then:
■​ Pop two elements from the stack.​
Let A be the top and B be the next.
■​ Evaluate the expression B ⊗ A.
■​ Push the result back onto the stack.
3.​ When the ) is encountered, stop scanning.
4.​ The only element left on the stack is the final result.

Example: Postfix Expression

Let​
P = 5 6 2 + * 12 4 / –

Equivalent Infix:​
5 * (6 + 2) – 12 / 4

Step-by-step Evaluation:

Step Action Stack

1 Read 5 (operand) 5

2 Read 6 (operand) 5, 6

3 Read 2 (operand) 5, 6, 2

4 Read + (operator) 5, 8

5 Read * (operator) 40
6 Read 12 (operand) 40, 12

7 Read 4 (operand) 40, 12, 4

8 Read / (operator) 40, 3

9 Read – (operator) 37

Final Value = 37

Key Points

●​ Stack is the main tool used for postfix evaluation.

●​ Each operator uses the top two elements of the stack.
●​ Final answer is the only value left in the stack after evaluation.

Application of Stacks

1. Function Call Management (Recursion)

●​ Used in programming languages to manage function calls and recursion.

●​ The call stack stores function calls in order, and when a function completes, it is
removed from the stack.​

●​ Example: Recursive algorithms like QuickSort, MergeSort, and Factorial

Calculation.

2. Expression Evaluation & Conversion

●​ Used to evaluate arithmetic expressions.

●​ Converts infix expressions (e.g., A + B * C) into postfix/prefix notation (e.g.,
A B C * +).
●​ Example: Expression Parsing, Postfix Evaluation using Stacks.
3. Undo/Redo Operations

●​ Stacks maintain history for undo/redo functionality in text editors, graphics

software, and IDEs.
●​ Example: CTRL + Z (Undo) and CTRL + Y (Redo) in MS Word.

4. Browser Back & Forward Navigation

●​ Browsers use two stacks:

○​ Back Stack: Stores previously visited pages.
○​ Forward Stack: Stores pages after clicking the back button.
●​ Example: Chrome, Firefox browsing history navigation.

5. Memory Management (Stack Memory)

●​ Used in memory allocation for local variables and function calls.

●​ Stack Overflow occurs when the stack memory exceeds its limit.
●​ Example: C and Java function execution memory handling.

Recursion

Recursion: Concept, Working, and Examples

Introduction

Recursion is a programming technique where a function calls itself to solve a problem.

It is used when a problem can be broken down into smaller subproblems of the same
type.

Key Properties of Recursion

1.​ Base Case – A condition where the recursion stops.

2.​ Recursive Case – The function calls itself with a smaller problem.
3.​ Stack Memory Usage – Every function call is stored in a call stack until the
base case is reached.​

Factorial Using Recursion

Definition

Factorial of a number nn is the product of all positive integers from 1 to n:

n!=n×(n−1)!

Base Case: 0!=1, 1!=1

Recursive Function for Factorial in C

#include <stdio.h>​
​
// Recursive function to calculate factorial​
long long factorial(int n) {​
if (n == 0 || n == 1) // Base case​
return 1;​
return n * factorial(n - 1); // Recursive case​
}​
​
int main() {​
int num;​
printf("Enter a number: ");​
scanf("%d", &num);​
​
if (num < 0)​
printf("Factorial is not defined for negative numbers.\n");​
else​
printf("Factorial of %d is %lld\n", num, factorial(num));​
​
return 0;​
}

How It Works?

Function Call Returns

factorial(5) 5 × factorial(4)
 factorial(4) 4 × factorial(3)

factorial(3) 3 × factorial(2)

factorial(2) 2 × factorial(1)

factorial(1) 1 (Base Case)

Final Result 5 × 4 × 3 × 2 × 1 = 120

Output Example

Enter a number: 5

Factorial of 5 is 120

Fibonacci Series Using Recursion

Definition

Fibonacci series follows the rule:

F(n)=F(n−1)+F(n−2)

Base Cases:

●​ F(1) = 0​

●​ F(2) = 1​

Recursive Function for Fibonacci in C

#include <stdio.h>​
​
// Recursive function to find Fibonacci number​
int fibonacci(int n) {​
if (n == 1)​
return 0;​
else if (n == 2)​
return 1;​
return fibonacci(n - 1) + fibonacci(n - 2);​
}​
​
int main() {​
int num;​
printf("Enter the number of terms: ");​
scanf("%d", &num);​
​
printf("Fibonacci Series: ");​
for (int i = 1; i <= num; i++) {​
printf("%d ", fibonacci(i));​
}​
​
printf("\n");​
return 0;​
}

How It Works?

Function Call Returns

fibonacci(5) fibonacci(4) + fibonacci(3)

fibonacci(4) fibonacci(3) + fibonacci(2)

fibonacci(3) fibonacci(2) + fibonacci(1)

 fibonacci(2) 1 (Base Case)

fibonacci(1) 0 (Base Case)

Output Example

Enter the number of terms: 7

Fibonacci Series: 0 1 1 2 3 5 8

Advantages of Recursion

Simplifies complex problems​

Works well for tree-based and divide-and-conquer problems​
Makes code more readable

Disadvantages of Recursion

High memory usage (stack overflow risk for deep recursion)​

Repeated calculations (especially in Fibonacci, which can be optimized using
memoization)

Tower of Hanoi

Introduction

The Tower of Hanoi is a mathematical puzzle involving three pegs (A, B, and C) and N
disks arranged in decreasing size on one peg. The goal is to move all disks from the
source peg (A) to the destination peg (C) using the auxiliary peg (B) while following
three rules:

1.​ Only one disk can be moved at a time.

2.​ A larger disk cannot be placed on a smaller disk.
3.​ Only the topmost disk of any peg can be moved.
Working Principle (Recursive Approach)

The problem follows a divide-and-conquer strategy, where:

1.​ Move N-1 disks from source (A) to auxiliary (B).

2.​ Move the Nth (largest) disk from source (A) to destination (C).
3.​ Move N-1 disks from auxiliary (B) to destination (C).​

Base Case

If there is only one disk, move it directly from the source to the destination.

Recursive Algorithm
#include <stdio.h>​
​
// Recursive function for Tower of Hanoi​
void towerOfHanoi(int n, char source, char auxiliary, char destination)
{​
if (n == 1) {​
printf("Move disk 1 from %c to %c\n", source, destination);​
return;​
}​
​
// Move N-1 disks from source to auxiliary​
towerOfHanoi(n - 1, source, destination, auxiliary);​
​
// Move the nth disk from source to destination​
printf("Move disk %d from %c to %c\n", n, source, destination);​
​
// Move N-1 disks from auxiliary to destination​
towerOfHanoi(n - 1, auxiliary, source, destination);​
}​
​
int main() {​
int num_disks;​
printf("Enter number of disks: ");​
scanf("%d", &num_disks);​
​
 towerOfHanoi(num_disks, 'A', 'B', 'C');​
​
return 0;​
}​

Example Execution (N = 3)
Enter number of disks: 3​
Move disk 1 from A to C​
Move disk 2 from A to B​
Move disk 1 from C to B​
Move disk 3 from A to C​
Move disk 1 from B to A​
Move disk 2 from B to C​
Move disk 1 from A to C

Time Complexity

●​ T(n) = 2T(n-1) + 1
●​ Solution: O(2ⁿ - 1) (Exponential complexity)

Applications

1.​ Recursion Learning – Helps in understanding recursion and divide-and-conquer.

2.​ Algorithm Design – Basis for backtracking and dynamic programming.
3.​ Data Structure Manipulation – Used in stack-based operations.
4.​ Network Routing – Used in packet switching and scheduling.​
Queues:
Queues:

Definition

A queue is a linear data structure in which elements are inserted from one end and removed
from the other end. The end where insertion takes place is called the rear, and the end
where deletion takes place is called the front.​
This follows the FIFO (First-In First-Out) principle, where the element that is inserted first is
the one to be removed first.

Queues are used in real life and in computer applications where processing is done in the
order of arrival. Some examples include:

●​ People standing in a line (first person gets served first),

●​ Print job scheduling in printers,
●​ CPU job scheduling in operating systems (time-sharing).

Representation of Queues

Queues can be represented in two ways:

1.​ Using Arrays (Linear or Circular)

2.​ Using Linked Lists

Here we focus on array representation.

We use:

●​ An array QUEUE[] to hold the elements,

●​ Two integer variables FRONT and REAR to point to the front and rear positions of the
queue.

If FRONT = NULL, it indicates that the queue is empty.

Linear Array Representation

In a linear array-based queue:

●​ Insertion is done at REAR and deletion at FRONT.

●​ After each insertion: REAR := REAR + 1
●​ After each deletion: FRONT := FRONT + 1​
However, this leads to inefficient use of space. Once REAR reaches the last index of the
array (even if elements are deleted from the front), new insertions are not possible unless we
shift all elements to the beginning, which is costly in terms of time.

Circular Queue

To overcome the problem of unused space in a linear queue, we use the concept of a
circular queue.

In a circular queue:

●​ The last position is connected back to the first position of the array.
●​ If REAR = N and an insertion is to be made, REAR is set to 1.
●​ Similarly, if FRONT = N and deletion happens, FRONT is set to 1.

This is similar to modular arithmetic, where positions wrap around.

Queue Empty and Full Conditions

●​ Empty Queue: If FRONT = NULL

●​ Full Queue:​
If FRONT = 1 and REAR = N,​
or if FRONT = REAR + 1 (in case of circular queue)

Special Case

If the queue contains only one element:

●​ FRONT = REAR ≠ NULL​

On deletion:
●​ Set both FRONT := NULL and REAR := NULL

This indicates the queue has become empty.

Algorithm for Insertion (QINSERT)

This procedure inserts an element ITEM into the queue.

Algorithm: QINSERT(QUEUE, N, FRONT, REAR, ITEM)

 Step 1: [Check for Overflow]​
If (FRONT = 1 AND REAR = N) OR (FRONT = REAR + 1) then​
Print "OVERFLOW"​
Exit​
Step 2: [Check if queue is empty]​
If FRONT = NULL then​
Set FRONT := 1​
Set REAR := 1​
Else if REAR = N then​
Set REAR := 1​
Else​
Set REAR := REAR + 1​
Step 3: [Insert the item]​
Set QUEUE[REAR] := ITEM​
Step 4: Exit

Algorithm for Deletion (QDELETE)

This procedure removes an element from the front of the queue and stores it in variable
ITEM.

Algorithm: QDELETE(QUEUE, N, FRONT, REAR, ITEM)

Step 1: [Check for Underflow]​

If FRONT = NULL then​
Print "UNDERFLOW"​
Exit​
​
Step 2: [Store the front item]​
Set ITEM := QUEUE[FRONT]​
​
Step 3: [Check if only one element is left]​
If FRONT = REAR then​
Set FRONT := NULL​
Set REAR := NULL​
Else if FRONT = N then​
Set FRONT := 1​
Else​
Set FRONT := FRONT + 1​
​
Step 4: Exit
Linked Representation of Queues (Linked Queue)
In the linked representation of a queue, we use a linked list instead of an array. It uses two
pointer variables:

●​ FRONT → points to the first (front) node of the queue

●​ REAR → points to the last (rear) node of the queue

Each node in the linked queue has two parts:

●​ INFO → holds the data (item)

●​ LINK → holds the pointer to the next node

Structure of Linked Queue

Advantages over Array Representation

●​ No fixed size limitation like arrays.

●​ No need to check for circular queue.
●​ Efficient in memory usage, nodes can be dynamically added or removed.
●​ No need to shift elements on deletion like arrays.​

Insertion in Linked Queue

To insert an element at the rear end of the queue:

Steps (Simplified)

1.​ Check if there is any free space (AVAIL list). If not, overflow.
2.​ Take a node from the AVAIL list.
3.​ Store the new item in the node.
4.​ Make the LINK part of the new node as NULL.
5.​ If the queue is empty (FRONT is NULL):
○​ Make both FRONT and REAR point to the new node.
6.​ Else:
○​ Link the current REAR to the new node.
 ○​ Update REAR to the new node.

Algorithm: LINKQ_INSERT
Procedure LINKQ_INSERT(INFO, LINK, FRONT, REAR, AVAIL, ITEM)​
​
1. If AVAIL == NULL​
Print "OVERFLOW"​
Exit​
​
2. NEW = AVAIL​
AVAIL = LINK[AVAIL]​
​
3. INFO[NEW] = ITEM​
LINK[NEW] = NULL​
​
4. If FRONT == NULL then​
FRONT = REAR = NEW​
Else​
LINK[REAR] = NEW​
REAR = NEW​
​
5. Exit

Deletion in Linked Queue

To delete an element from the front end of the queue:

Steps (Simplified)

1.​ Check if the queue is empty (FRONT == NULL). If yes, underflow.

2.​ Store FRONT in a temporary variable TEMP.
3.​ Get the item from TEMP.
4.​ Move FRONT to the next node.
5.​ Add the deleted node back to the AVAIL list.​

Algorithm: LINKQ_DELETE
Procedure LINKQ_DELETE(INFO, LINK, FRONT, REAR, AVAIL, ITEM)​
​
 1. If FRONT == NULL​
Print "UNDERFLOW"​
Exit​
​
2. TEMP = FRONT​
​
3. ITEM = INFO[TEMP]​
​
4. FRONT = LINK[TEMP]​
​
5. LINK[TEMP] = AVAIL​
AVAIL = TEMP​
​
6. Exit

Types of Queues
In data structures, different types of queues are used depending on the application and the
type of operation needed. The basic structure of a queue follows FIFO (First-In, First-Out),
but there are variations to serve specific use cases.

The main types of queues are:

1. Simple Queue (Linear Queue)

Definition:​
A simple queue is the basic form of queue in which insertion is done at the rear end, and
deletion is done from the front end. It follows FIFO order strictly.

Operations:

●​ Enqueue (Insertion): Adds an element at the rear.​

●​ Dequeue (Deletion): Removes an element from the front.​

Drawback:​
Even if there are empty spaces at the front, we cannot reuse them without shifting. This
leads to wastage of space.

Example:
FRONT → [10][20][30] ← REAR

2. Circular Queue

Definition:​
A circular queue overcomes the limitation of the simple queue by connecting the last
position back to the first position. In this way, it forms a circle, and the space can be
reused efficiently.

Representation:​
A circular queue is usually implemented using arrays with modular arithmetic for wrapping
around.

Advantages:

●​ Efficient use of memory.

●​ No need for shifting elements.

Example (using array of size 5):​

If REAR is at index 4 and one more element is inserted, it goes to index 0 (if space is
available).

Formulas:

●​ Insertion: REAR = (REAR + 1) % size

●​ Deletion: FRONT = (FRONT + 1) % size

3. Double-Ended Queue (Deque)

Definition:​
A Double-Ended Queue or Deque is a type of queue where insertion and deletion can be
done from both ends: front and rear.

Types of Deque:

●​ Input Restricted Deque: Insertion allowed only at one end, deletion from both.​

●​ Output Restricted Deque: Deletion allowed only at one end, insertion from both.​

Use Case:​
Deques are useful in certain algorithms like palindrome checking, undo mechanisms, etc.

Example:
Insert at both ends ⇄ [10][20][30] ⇄ Delete at both ends

4. Priority Queue

Definition:​
A Priority Queue is a type of queue where each element is assigned a priority, and the
element with the highest priority is served first, even if it was inserted later.

Key Features:

●​ Not strictly FIFO.

●​ Implemented using arrays, linked lists, heaps, or trees.

Types:

●​ Ascending Priority Queue: Lower priority number gets served first.

●​ Descending Priority Queue: Higher priority number gets served first.

Example:

Insert(40, priority=2), Insert(30, priority=1), Insert(50, priority=3)

Dequeues in order: 30 → 40 → 50

Summary Table
Type of Insertion Deletion Special Feature
Queue

Simple Queue Rear Front FIFO, limited by array size

Circular Rear (circular) Front (circular) Reuses array space efficiently

Queue

Deque Both ends Both ends Flexible insertion and deletion

Priority Queue Based on Based on Not FIFO, serves based on

priority priority importance

Operations on Queues
A queue is a linear data structure that follows the FIFO (First-In, First-Out) principle. The
basic operations that can be performed on a queue are:
1. Enqueue (Insertion)

This operation adds a new element to the rear of the queue.

●​ In array representation, we increase the REAR pointer and insert the item.
●​ In linked list representation, a new node is created, and it is linked at the end of the
list, updating the REAR pointer.

Check for:

●​ Overflow condition in array queues (when REAR reaches maximum size and no
space is available).
●​ In linked queues, overflow occurs only if memory is full (i.e., AVAIL list is empty).​

2. Dequeue (Deletion)

This operation removes an element from the front of the queue.

●​ The FRONT pointer is moved to the next position.

●​ The deleted value is usually stored in a temporary variable or returned.

Check for:

●​ Underflow condition: If FRONT is NULL (linked queue) or FRONT > REAR (array),
the queue is empty.

3. Peek / Front (Accessing the Front Element)

Returns the element at the front of the queue without deleting it. It does not affect the
FRONT pointer.

4. isFull (Queue Full Check)

This operation checks if the queue has reached its maximum capacity. This is applicable
only in array-based queues.

5. isEmpty (Queue Empty Check)

This operation checks if the queue is empty.

 ●​ In array-based queues: If FRONT > REAR or FRONT == -1.
●​ In linked queues: If FRONT == NULL.

Other Auxiliary Operations

Depending on the type of queue (circular, deque, priority), other operations like:

●​ enqueueFront
●​ enqueueRear
●​ dequeueFront
●​ dequeueRear
●​ insertByPriority​
may also be defined.​

Applications of Queues
Queues are widely used in computer systems and real-world situations where order of
processing matters.

1. Job Scheduling / Process Scheduling in Operating Systems

Operating systems use queues to manage processes waiting for CPU time or I/O operations.

●​ Ready Queue: Stores processes that are ready to execute.

●​ Waiting Queue: Stores processes waiting for resources.

2. Printer Queue

When multiple documents are sent to a printer, they are kept in a queue and printed one by
one in the order they were received.

3. Call Center / Customer Service Systems

Customer requests are stored in a queue and answered in the order they arrive (FIFO).
4. CPU Task Scheduling and Interrupt Handling

Hardware interrupts are handled in the order of arrival using a queue.

5. Data Buffers (e.g., IO Buffers, Keyboard Buffers)

Key presses are stored in a queue and processed in the same order by the system.

6. Traffic Management and Ticket Booking Systems

Vehicles at a traffic signal or passengers booking tickets are handled using queues.

7. BFS (Breadth-First Search) in Graphs

Queues are used in BFS to explore graph nodes level by level.

8. Message Queues in Networking / Multithreading

In distributed systems and real-time applications, message queues manage communication

between different threads or systems.

9. Simulation Systems

Events in simulations (like queue at bank counters, toll booths) are processed using queues.

Summary of Applications
Application Area Use of Queue

Operating System CPU Scheduling, I/O buffering

Networking Packet routing, message queues

Printer Management Print job handling

Web Servers Request processing

Graph Algorithms BFS, level-order traversal

Real-life systems Ticket counters, call centers, traffic