Iteration and Recursion

1. Iteration
 Definition: Iteration means repeatedly executing a set of instructions until a condition is
met.
 Implemented using loops (for, while, do-while).
 Flow: Control goes back to the loop condition after each execution.
 Memory: Uses a single memory block (no function call overhead).

Diagram (Iteration Loop Flow):

┌───────────┐
│ Initialize │
└─────┬─────┘
│
┌─────▼─────┐
│ Condition │◄───────────┐
└─────┬─────┘ │
│True │
┌─────▼─────┐ │
│ Statements│ │
└─────┬─────┘ │
│ │
└──────────────────┘
│False
▼
Exit Loop

2. Recursion
 Definition: Recursion is when a function calls itself directly or indirectly to solve a
problem.
 Each recursive call creates a new activation record on the call stack.
 Best suited for problems that can be divided into smaller sub-problems.

Diagram (Recursive Function Flow):

Function Call f(n)

|
├── Base Case? → Yes → Return Result
|
└── Recursive Case
 f(n) → f(n-1) → f(n-2) → ... → f(1)

3. Principle of Recursion
1. Base Case: Stops recursion (prevents infinite loop).
Example: if (n == 0) return 1;
2. Recursive Case: Function calls itself with smaller input.
Example: return n * fact(n-1);
3. Progress Towards Base Case: Input size must decrease to reach termination.

4. Types of Recursion
a) Head Recursion

 The recursive call is made at the beginning of the function.

 Work is done after the recursive call.
 Example:
 void headRec(int n) {
 if(n==0) return;
 headRec(n-1);
 printf("%d ", n);
 }

(Work happens after recursion)

b) Tail Recursion

 The recursive call is made at the end of the function.

 Work is done before the recursive call.
 Example:
 void tailRec(int n) {
 if(n==0) return;
 printf("%d ", n);
 tailRec(n-1);
 }

(Work happens before recursion)

Diagram Difference:

 Head Recursion: Call → Call → Call → Work → Work → Work

  Tail Recursion: Work → Call → Work → Call → Work

5. Removal of Recursion (Conversion to Iteration)

 Recursive programs can be rewritten using stacks or loops.
 Useful when recursion depth is too high (risk of stack overflow).

Example: Factorial

 Recursive:
 int fact(int n) {
 if (n==0) return 1;
 return n * fact(n-1);
 }
 Iterative:
 int fact(int n) {
 int result = 1;
 for(int i=1; i<=n; i++) result *= i;
 return result;
 }

6. Problem Solving Examples

A) Binary Search

 Recursive:

int binarySearch(int arr[], int l, int r, int x) {

if (l <= r) {
int mid = (l+r)/2;
if (arr[mid] == x) return mid;
else if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);
else return binarySearch(arr, mid+1, r, x);
}
return -1;
}

 Iterative:

int binarySearch(int arr[], int n, int x) {

int l=0, r=n-1;
while(l <= r) {
int mid = (l+r)/2;
if(arr[mid]==x) return mid;
 else if(arr[mid] > x) r = mid-1;
else l = mid+1;
}
return -1;
}

B) Fibonacci Series

 Recursive:

int fib(int n) {
if (n<=1) return n;
return fib(n-1)+fib(n-2);
}

 Iterative:

void fibIter(int n) {
int a=0, b=1, c;
for(int i=0; i<n; i++) {
printf("%d ", a);
c = a+b;
a=b; b=c;
}
}

C) Tower of Hanoi

 Recursive:

void TOH(int n, char from, char to, char aux) {

if(n==1) {
printf("Move disk 1 from %c to %c\n", from, to);
return;
}
TOH(n-1, from, aux, to);
printf("Move disk %d from %c to %c\n", n, from, to);
TOH(n-1, aux, to, from);
}

 Explanation:
o Move n-1 disks from source → auxiliary.
o Move nth disk from source → destination.
o Move n-1 disks from auxiliary → destination.

Diagram (Tower of Hanoi for n=3):

Source(A) → Aux(B) → Dest(C)

Step 1: Move 2 disks A→B using C

Step 2: Move disk 3 A→C
Step 3: Move 2 disks B→C using A

7. Trade-off between Iteration and Recursion

Aspect Iteration Recursion
Memory Usage Constant (single stack frame) Extra stack space for each call
Execution Faster (no overhead) Slower (function call overhead)
Speed
Readability Less intuitive for complex More natural for divide & conquer
problems
Termination Controlled by loop condition Controlled by base case
Risk Infinite loop if condition fails Stack overflow if base case fails
Use Case Simple, repetitive problems Recursive structures (trees, TOH,
DFS)

Balanced Parentheses and Delimiters

Write a C program that checks whether a string of parentheses is balanced or not using
stack.

An opening symbol that has a corresponding closing symbol is considered balanced

parentheses, where the parentheses are correctly nested and the opening and closing
symbols are the same.

Valid balanced parentheses:

 [[{{(())}}]]

 [][][](){}

Invalid balanced parentheses:

 ([)]

 ((()]))

 [{()]
Program for parentheses check and balance

#include <stdio.h>

#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 100

// Global variables for stack and top

char stack[MAX_SIZE];

int top = -1;

// Function to push a character onto the stack

void push(char data) {

if (top == MAX_SIZE - 1) {
printf("Overflow stack!\n");

return;
}

top++;
stack[top] = data;

}
// Function to pop a character from the stack

char pop() {
if (top == -1) {

printf("Empty stack!\n");
return ' ';

char data = stack[top];

top--;

return data;

// Function to check if two characters form a matching pair of parentheses

int is_matching_pair(char char1, char char2) {

if (char1 == '(' && char2 == ')') {

return 1;

} else if (char1 == '[' && char2 == ']') {

return 1;
} else if (char1 == '{' && char2 == '}') {

return 1;

} else {
return 0;

}
}

// Function to check if the expression is balanced

int isBalanced(char* text) {

 int i;
for (i = 0; i < strlen(text); i++) {

if (text[i] == '(' || text[i] == '[' || text[i] == '{') {

push(text[i]);

} else if (text[i] == ')' || text[i] == ']' || text[i] == '}') {

if (top == -1) {

return 0; // If no opening bracket is present

} else if (!is_matching_pair(pop(), text[i])) {

return 0; // If closing bracket doesn't match the last opening bracket

if (top == -1) {

return 1; // If the stack is empty, the expression is balanced

} else {

return 0; // If the stack is not empty, the expression is not balanced

// Main function

int main() {
char text[MAX_SIZE];

printf("Input an expression in parentheses: ");

scanf("%s", text);

// Check if the expression is balanced or not

if (isBalanced(text)) {
 printf("The expression is balanced.\n");
} else {

printf("The expression is not balanced.\n");

}

return 0; }
 [ DATA STRUCTURES]
Chapter - 05 : “Queues
Queues”
QUEUES

Queue is a non-primitive linear data structure that permits insertion of an element at

one end and deletion of an element at the other end. The end at which the deletion of an
element take place is called front, and the end at which insertion of a new element can
take place is called rear. The deletion or insertion of elements can take place only at the
front and rear end of the list respectively.
The first element that gets added into the queue is the first one to get removed from
the list. Hence, Queue is also referred to as First-In-First-Out (FIFO) list. The name
‘Queue’ comes from the everyday use of the term. Consider a railway reservation booth,
at which we have to get into the reservation queue. New customers got into the queue
from the rear end, whereas the customers who get their seats reserved leave the queue
from the front end. It means the customers are serviced in the order in which they arrive
the service center (i.e. first come first serve type of service). The same characteristics
apply to our Queue. Fig. 1. shows the pictorial representation of a Queue.

10 20 30 40 50 60 70 80

Front Rear

Fig. (1) : Pictorial representation of a Queue

In fig (1), 10 is the first element and 80 is the last element added to the
Queue. Similarly, 10 would be the first element to get removed and 80 would be the last element
to get removed.

Figures 2(a) to 2(d) shows queue graphically during insertion operation :

F = -1 and R = -1

0 1 2 3 4 5 6

F R
Fig. 2(a) Empty Queue
 F = 0 and R = 0
20

F R
Fig. 2(b) One Element Queue

F = 0 and R = 1
20 30

F R
Fig. 2(c) Two Element Queue

F = 0 and R = 2
20 30 40

F R
Fig. 2(d) Three Element Queue

It is clear from the above figures that whenever we insert an element in the queue,
the value of Rear is incremented by one i.e.
Rear = Rear + 1

Also, during the insertion of the first element in the queue we always incremented
the Front by one i.e.
Front = Front + 1

Afterwards the Front will not be changed during the entire operation. The following
figures show Queue graphically during deletion operation :

F = 1 and R = 2
30 40

F R
 Fig. 2(e) One Element (20) Deleted from Front

F = 2 and R = 2
40

F R
Fig. 2(f) Second Element (30) Deleted from Front

This is clear from Fig. 2(e) and 2(f), that whenever an element is removed from the queue,
the value of Front is incremented by one i.e.,

Front = Front + 1

Now, if we insert any element in the queue, the queue will look like :

F = 2 and R = 3
40 50

F R
Fig. 2(g) Insertion after Deletion

Sequential implementation of Linear queues

Queues can be implemented in two ways :
1. Static implementation (using arrays)
2. Dynamic implementation (using pointers)

Static implementation :
Static implementation of Queue is represented by arrays. If Queue is implemented
using arrays, we must be sure about the exact number of elements we want to store in the
queue, because we have to declare the size of the array at design time or before the
processing starts. In this case, the beginning of the array will become the front for the
queue and the last location of the array will act as rear for the queue. Fig. (3) shows the
representation of a queue as an array.

arr[0] arr[1] arr[2] arr[3] arr[4] arr[5] arr[6] arr[7]

10 20 30 40 50 60 70 80

Front Rear
 Fig. (3) Representation of a Queue as an array

The following relation gives the total number of elements present in the queue,
when implemented using arrays :

rear – front + 1

Also note that if front > rear, then there will be no element in the queue or queue is
empty.

OPERATIONS ON A QUEUE
The basic operations that can be performed on queue are :

1. To Insert an element in a Queue

2. To Delete an element from a Queue.
3. To Traverse all elements of a Queue.

ALGORITHMS & FUNCTIONS FOR INSERTION AND DELETION IN A LINEAR QUEUE

(USING ARRAYS)

(1) Algorithm for Insertion in a Linear Queue

Let QUEUE[MAXSIZE] is an array for implementing the Linear Queue & NUM is the
element to be inserted in linear queue, FRONT represents the index number of the element at the
beginning of the queue and REAR represents the index number of the element at the end of the
Queue.

Step 1 :If REAR = (MAXSIZE –1) : then

Write : “Queue Overflow” and return
[End of If structure]
Step 2 : Read NUM to be inserted in Linear Queue.
Step 3 : Set REAR := REAR + 1
Step 4 : Set QUEUE[REAR] := NUM
Step 5 : If FRONT = –1 : then
Set FRONT=0.
[End of If structure]
Step 6 : Exit
Function for insertion in a linear queue (using arrays)

void lqinsert()
{
int num;
if(rear==MAXSIZE-1)
{
printf("\nQueue is full (Queue overflow)");
return;
}
printf("\nEnter the element to be inserted : ");
scanf("%d",&num);
rear++;
queue[rear]=num;
if(front==-1)
front=0;
}

(2) Algorithm for Deletion from a Linear Queue

Let QUEUE[MAXSIZE] is an array for implementing the Linear Queue & NUM is the
element to be deleted from linear queue, FRONT represents the index number of the element at
the beginning of the queue and REAR represents the index number of the element at the end of
the Queue.

Step 1 : If FRONT = -1 : then

Write : “Queue Underflow” and return
[End of If structure]
Step 2 : Set NUM := QUEUE[FRONT]
Step 3 : Write “Deleted item is : ”, NUM
Step 4 : Set FRONT := FRONT + 1.
Step 5 : If FRONT>REAR : then
Set FRONT := REAR := -1.
[End of If structure]
Step 6 : Exit
Function(Procedure) for Deletion from a Linear Queue

void lqdelete()
{
if(front == -1)
{
printf("\nQueue is empty (Queue underflow)");
return;
}
int num;
num=queue[front];
printf("\nDeleted element is : %d",num);
front++;
if(front>rear)
front=rear=-1;
}
Program 1 : Static implementation of Linear Queues using arrays
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define MAXSIZE 5
void initialize();
void lqinsert();
void lqdelete();
void lqtraverse();
int queue[MAXSIZE];
int front,rear;

void main()
{
clrscr();
initialize();
int choice;
while(1)
{
clrscr();
printf("\nSTATIC IMPLEMENTATION OF LINEAR QUEUE");
printf("\n-------------------------------------");
printf("\n1. Insert");
printf("\n2. Delete");
printf("\n3. Traverse");
printf("\n4. Exit");
printf("\n-------------------------------------");
printf("\n\nEnter your choice [1/2/3/4] : ");
scanf("%d",&choice);
switch(choice)
{
case 1 : lqinsert();
break;
case 2 : lqdelete();
break;
case 3 : lqtraverse();
break;
case 4 : exit(0);
default : printf("\nInvalid choice");
}
getch();
}
}
// Function to initialize queue

void initialize()
{
front=rear=-1;
}

// Function to insert an element into queue

void lqinsert()
{
int num;
if(rear==MAXSIZE-1)
{
printf("\nQueue is full (Queue overflow)");
return;
}
printf("\nEnter the element to be inserted : ");
scanf("%d",&num);
rear++;
queue[rear]=num;
if(front==-1)
front=0;
}

// Function for Delete an element from queue

void lqdelete()
{
if(front==-1)
{
printf("\nQueue is empty (Queue underflow)");
return;
}
int num;
num=queue[front];
printf("\nDeleted element is : %d",num);
front++;
if(front>rear)
front=rear=-1;
}
 1. // Function to display Queue

void lqtraverse()
{
if(front==-1)
{
printf("\nQueue is empty (Queue underflow)");
return;
}
else
{
printf("\nQueue elements are : \n");
for(int i=front;i<=rear;i++)
printf("%d\t",queue[i]);
}
}

DYNAMIC IMPLEMENTATION OF LINEAR QUEUE

ALGORITHM FOR INSERTION AND DELETION IN A LINEAR QUEUE (USING
POINTERS)

Let queue be a structure whose declarations looks like follows :

struct queue
{
int info;
struct queue *link;
}*start=NULL;
ALGORITHMS FOR INSERTION & DELETION IN A LINEAR QUEUE FOR DYNAMIC
IMPLEMENTATION USING LINKED LIST

(1) Algorithm for inserting an element in a Linear Queue :

Let PTR is the structure pointer which allocates memory for the new node & NUM is the
element to be inserted into linear queue, INFO represents the information part of the node and
LINK represents the link or next pointer pointing to the address of next node. FRONT
represents the address of first node, REAR represents the address of the last node. Initially,
Before inserting first element in the queue, FRONT=REAR=NULL.
Step 1 : Allocate memory for the new node using PTR.
Step 2 : Read NUM to be inserted into linear queue.
Step 3 : Set PTR->INFO = NUM
Step 4 : Set PTR->LINK= NULL
Step 5 : If FRONT = NULL : then
Set FRONT=REAR=PTR
Else
Set REAR->LINK=PTR;
Set REAR=PTR;
[End of If Else Structure]
Step 6 : Exit

Function(Procedure) for Inserting an element in a Linear Queue :

void lqinsert()
{
struct queue *ptr;
int num;
ptr=(struct queue*)malloc(sizeof(struct queue));
printf("\nEnter element to be inserted in queue : ");
scanf("%d",&num);
ptr->info=num;
ptr->link=NULL;
if(front==NULL)
{
front=ptr;
rear=ptr;
}
else
{
rear->link=ptr;
rear=ptr;
}
}
(2) Algorithm for Deleting a node from a Linear Queue :

Let PTR is the structure pointer which deallocates memory of the first node in the
linear queue & NUM is the element to be deleted from queue, INFO represents the
information part of the deleted node and LINK represents the link or next pointer of the
deleted node pointing to the address of next node. FRONT represents the address of first
node, REAR represents the address of the last node.
Step 1 : If FRONT = NULL : then
Write ‘Queue is Empty(Queue Underflow)’ and return.
[End of If structure]
Step 2 : Set PTR = FRONT
Step 3 : Set NUM = PTR->INFO
Step 4 : Write ‘Deleted element from linear queue is : ‘,NUM.
Step 5 : Set FRONT = FRONT->LINK
Step 6 : If FRONT = NULL : then
Set REAR = NULL.
[End of If Structure].
Step 7 : Deallocate memory of the node at the beginning of queue using PTR.
Step 8 : Exit.

Function(Procedure) for deleting a node from a Linear Queue

void lqdelete()
{
if(front==NULL)
{
printf("\nQueue is empty (Queue underflow)");
return;
}
struct queue *ptr;
int num;
ptr=front;
num=ptr->info;
printf("\nThe deleted element is : %d",num);;
front=front->link;
if(front==NULL)
rear=NULL;
free(ptr);
}
}
Program 2 : Dynamic implementation of linear queue using pointers
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct queue
{
int info;
struct queue *link;
}*front,*rear;

void initialize();
void lqinsert();
void lqdelete();
void lqtraverse();

void main()
{
int choice;
initialize();
while(1)
{
clrscr();
printf("\nDYNAMIC IMPLEMENTATION OF LINEAR QUEUE");
printf("\n1. Insert");
printf("\n2. Delete");
printf("\n3. Traverse");
printf("\n4. Exit");
printf("\n\nEnter your choice [1/2/3/4] : ");
scanf("%d",&choice);
switch(choice)
{
case 1: lqinsert();
break;
case 2: lqdelete();
break;
case 3: lqtraverse();
break;
case 4: exit(0);;
default : printf("\nInvalid choice");
}
getch();
}
}
// Function for initialize linear Queue

void initialize()
{
front=rear=NULL;
}

// Function to insert element in Linear queue

void lqinsert()
{
struct queue *ptr;
int num;
ptr=(struct queue*)malloc(sizeof(struct queue));
printf("\nEnter element to be inserted in queue : ");
scanf("%d",&num);
ptr->info=num;
ptr->link=NULL;
if(front==NULL)
{
front=ptr;
rear=ptr;
}
else
{
rear->link=ptr;
rear=ptr;
}
}

// Function to delete element from Linear queue

void lqdelete()
{
if(front==NULL)
{
printf("\nQueue is empty (Queue underflow)");
return;
}
 struct queue *ptr;
int num;
ptr=front;
num=ptr->info;
printf("\nThe deleted element is : %d",num);;
front=front->link;
if(front==NULL)
rear=NULL;
free(ptr);
}

// Function to display Linear Queue

void lqtraverse()
{
struct queue *ptr;
if(front==NULL)
{
printf("\nQueue is empty (Queue underflow)");
return;
}
else
{
ptr=front;
printf("\n\nQueue elements are : \n");
printf("\nROOT");
while(ptr!=NULL)
{
printf(" -> %d",ptr->info);
ptr=ptr->link;
}
printf(" -> NULL");
}
}

CIRCULAR QUEUES

The queue that we implemented using an array suffers from one limitation. In that
implementation there is a possibility that the queue is reported as full (since rear has
reached the end of the array), even though in actuality there might be empty slots at the
beginning of the queue. To overcome this limitation we can implement the queue as a
circular queue. Here as we go on adding elements to the queue and reach the end of the
array, the next element is stored in the first slot the array (provided it is free). Suppose an
array arr of n elements is used to implement a circular queue we may reach arr[n-1]. We
cannot add any more elements to the queue since we have reached at the end of the
array. Instead of reporting the queue as full, if some elements in the queue have been
deleted then there might be empty slots at the beginning of the queue. In such a case
these slots would be filled by new elements being added to the queue. In short just
because we have reached the end of the array, the queue would not be reported as full.
The queue would be reported as full only when all the slots in the array stand occupied.
Figure (4) shows the pictorial representation of a circular queue.

Rear
Q[0]

50 Front

Q[4] 10 Q[1]
40

30 20

Q[3] Q[2]

Fig. (4) : Pictorial representation of a circular queue

ALGORITHM FOR INSERTION AND DELETION IN A CIRCULAR QUEUE (USING ARRAYS)

(1) Algorithm for Insertion in a Circular Queue

Let CQUEUE[MAXSIZE] is an array for implementing the Circular Queue, where MAXSIZE
represents the max. size of array. NUM is the element to be inserted in circular queue, FRONT
represents the index number of the element at the beginning of the queue and REAR represents
the index number of the element at the end of the Queue.

Step 1 : If FRONT = (REAR + 1) % MAXSIZE : then

Write : “Queue Overflow” and return.
[End of If structure]
Step 2 : Read NUM to be inserted in Circular Queue.
Step 3 : If FRONT= -1 : then
Set FRONT = REAR =0.
Else
Set REAR=(REAR + 1) % MAXSIZE.
[End of If Else structure]
Step 4 : Set CQUEUE[REAR]=NUM;
Step 5 : Exit
Function(Procedure) for Insertion in a Circular Queue using arrays:

void cqinsert()
{
int num;
if(front==(rear+1)%MAXSIZE)
{
printf("\nQueue is Full(Queue overflow)");
return;
}
printf("\nEnter the element to be inserted in circular queue : ");
scanf("%d",&num);
if(front==-1)
front=rear=0;
else
rear=(rear+1) % MAXSIZE;
cqueue[rear]=num;
}

(2) Algorithm for Deletion from a Linear Queue :

Let CQUEUE[MAXSIZE] is an array for implementing the Circular Queue, where

MAXSIZE represents the max. size of array. NUM is the element to be deleted from
circular queue, FRONT represents the index number of the first element inserted in the
Circular Queue and REAR represents the index number of the last element inserted in the
Circular Queue.

Step 1 : If FRONT = - 1 : then

Write : “Queue Underflow” and return.
[End of If Structure]
Step 2 : Set NUM = CQUEUE[FRONT].
Step 3 : Write ‘Deleted element from circular queue is : ",NUM.
Step 4 : If FRONT = REAR : then
Set FRONT = REAR = -1;
Else
Set FRONT = (FRONT + 1) % MAXSIZE.
Step 5 : Exit
Function(Procedure) to Delete an element from a Queue
void cqdelete()
{
int num;
if(front==-1)
{
printf("\nQueue is Empty (Queue underflow)");
return;
}
num=cqueue[front];
printf("\nDeleted element from circular queue is : %d",num);

if(front==rear)
front=rear=-1;
else
front=(front+1)%MAXSIZE;
}

Program 3 : Static implementation of Circular queue using arrays

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define MAXSIZE 5
void cqinsert();
void cqdelete();
void cqdisplay();

int cqueue[MAXSIZE];
int front=-1,rear=-1;
void main()
{
int choice;
while(1)
{
clrscr();
printf("\nSTATIC IMPLEMENTATION OF CIRCULAR QUEUE");
printf("\n-------------------------------------");
printf("\n1. Insert");
printf("\n2. Delete");
printf("\n3. Traverse");
printf("\n4. Exit");
printf("\n-------------------------------------");
 printf("\n\nEnter your choice [1/2/3/4] : ");
scanf("%d",&choice);
switch(choice)
{
case 1 : cqinsert();
break;
case 2 : cqdelete();
break;
case 3 : cqdisplay();
break;
case 4 : exit(0);
default : printf("\nInvalid choice");
}
getch();
}
}

// Function to insert element in the Circular Queue

void cqinsert()
{
int num;
if(front==(rear+1)%MAXSIZE)
{
printf("\nQueue is Full(Queue overflow)");
return;
}
printf("\nEnter the element to be inserted in circular queue : ");
scanf("%d",&num);
if(front==-1)
front=rear=0;
else
rear=(rear+1) % MAXSIZE;
cqueue[rear]=num;
}
// Function to delete element from the circular queue
void cqdelete()
{
int num;
if(front==-1)
{
printf("\nQueue is Empty (Queue underflow)");
return;
}
 num=cqueue[front];
printf("\nDeleted element from circular queue is : %d",num);

if(front==rear)
front=rear=-1;
else
front=(front+1)%MAXSIZE;
}

// Function to display circular queue

void cqdisplay()
{
int i;
if(front==-1)
{
printf("\nQueue is Empty (Queue underflow)");
return;
}
printf("\n\nCircular Queue elements are : \n");
for(i=front;i<=rear;i++)
printf("\ncqueue[%d] : %d",i,cqueue[i]);
if(front>rear)
{
for(i=0;i<=rear;i++)
printf("cqueue[%d] : %d\n",i,cqueue[i]);
for(i=front;i<MAXSIZE;i++)
printf("cqueue[%d] : %d\n",i,cqueue[i]);
}
}

Advantages of Circular queue over linear queue :

In a linear queue with max. size 5, after inserting element at the last location (4) of
array, the elements can’t be inserted, because in a queue the new elements are always
inserted from the rear end, and rear here indicates to last location of the array (location
with subscript 4) even if the starting locations before front are free. But in a circular queue,
if there is element at the last location of queue, then we can insert a new element at the
beginning of the array.
PRIORITY QUEUE
A priority queue is a collection of elements where the elements are stored according to
their priority levels. The order in which the elements get added or removed is decided by the
priority of the element.
Following rules are applied to maintain a priority queue :
(1) The element with a higher priority is processed before any element of lower priority.
(2) If there are elements with the same priority, then the element added first in the queue
would get processed.

Priority queues are used for implementing job scheduling by the operating system where
jobs with higher priorities are to be processed first. Another application of Priority queues is
simulation systems where priority corresponds to event times.
There are mainly two ways of maintaining a priority queue in memory. One uses a one-
way list, and the other uses multiple queues. The ease or difficultly in adding elements to or
deleting them from a priority queue clearly depends on the representation that one chooses.

One-way List Representation of a Priority Queue :

One way to maintain a priority queue in memory is by means of a one-way list, as follows :
(a) Each node in the list will contain three items of information; an information field INFO, a
priority number PRN and a link number LINK.
(b) A node X precedes a node Y in the list
(I) When X has higher priority then Y and
(II) When both have the same priority but X is added to the list before Y. This means that
the order in the one-way list corresponds to the order of the priority queue.
Priority queues will operate in the usual way : the lower the priority number, the higher the
priority.

Array representation of a Priority Queue :

Another way to maintain a priority queue in memory is to use a separate queue for each
level of priority (or for each priority number). Each such queue will appear in its own circular array
and must have its own pair of pointers, FRONT and REAR. In fact, each queue is allocated the
same amount of space, a two-dimensional array QUEUE can be used instead of the linear arrays.
Out of these two ways of representing a Priority Queue, the array representation of a
priority queue is more time-efficient than the one way list. This is because when adding an
element to a one-way list, one must perform a linear search on the list. On the other hand, the
one-way list representation of the priority queue may be more space-efficient than the array
representation. This is because in using the array representation overflow occurs when the
number of elements in any single priority level exceeds the capacity for that level, but in using the
one-way list, overflow occurs only when the total number of elements exceeds the total capacity.
Another alternative is to use a linked list for each priority level.
APPLICATIONS OF QUEUES :
1. Round Robin technique for processor scheduling is implemented using queues.
2. All types of customer service (like railway ticket reservation ) center software’s are
designed using queues to store customers information.
Printer server routines are designed using queues. A number of users share a printer using
printer server ( a dedicated computer to which a printer is connected), the printer server then
spools all the jobs from all the users, to the server’s hard disk in a queue. From here jobs are
printed one-by-one according to their number in the queue.
Deque (or double-ended queue)
What is a Deque (or double-ended queue)
The deque stands for Double Ended Queue. Deque is a linear data structure where the
insertion and deletion operations are performed from both ends. We can say that deque
is a generalized version of the queue.

Though the insertion and deletion in a deque can be performed on both ends, it does
not follow the FIFO rule. The representation of a deque is given as follows -

Types of deque
There are two types of deque -

o Input restricted queue

o Output restricted queue

Input restricted Queue

In input restricted queue, insertion operation can be performed at only one end, while
deletion can be performed from both ends.

Output restricted Queue

In output restricted queue, deletion operation can be performed at only one end, while
insertion can be performed from both ends.

Operations performed on deque

There are the following operations that can be applied on a deque -

o Insertion at front
 o Insertion at rear
o Deletion at front
o Deletion at rear

We can also perform peek operations in the deque along with the operations listed
above. Through peek operation, we can get the deque's front and rear elements of the
deque. So, in addition to the above operations, following operations are also supported
in deque -

o Get the front item from the deque

o Get the rear item from the deque
o Check whether the deque is full or not
o Checks whether the deque is empty or not

Now, let's understand the operation performed on deque using an example.

Insertion at the front end

In this operation, the element is inserted from the front end of the queue. Before
implementing the operation, we first have to check whether the queue is full or not. If
the queue is not full, then the element can be inserted from the front end by using the
below conditions -

o If the queue is empty, both rear and front are initialized with 0. Now, both will
point to the first element.
o Otherwise, check the position of the front if the front is less than 1 (front < 1),
then reinitialize it by front = n - 1, i.e., the last index of the array.

Insertion at the rear end

In this operation, the element is inserted from the rear end of the queue. Before
implementing the operation, we first have to check again whether the queue is full or
not. If the queue is not full, then the element can be inserted from the rear end by using
the below conditions -
 o If the queue is empty, both rear and front are initialized with 0. Now, both will
point to the first element.
o Otherwise, increment the rear by 1. If the rear is at last index (or size - 1), then
instead of increasing it by 1, we have to make it equal to 0.

Deletion at the front end

In this operation, the element is deleted from the front end of the queue. Before
implementing the operation, we first have to check whether the queue is empty or not.

If the queue is empty, i.e., front = -1, it is the underflow condition, and we cannot
perform the deletion. If the queue is not full, then the element can be inserted from the
front end by using the below conditions -

If the deque has only one element, set rear = -1 and front = -1.

Else if front is at end (that means front = size - 1), set front = 0.

Else increment the front by 1, (i.e., front = front + 1).

Deletion at the rear end

In this operation, the element is deleted from the rear end of the queue. Before
implementing the operation, we first have to check whether the queue is empty or not.

If the queue is empty, i.e., front = -1, it is the underflow condition, and we cannot
perform the deletion.

If the deque has only one element, set rear = -1 and front = -1.

If rear = 0 (rear is at front), then set rear = n - 1.

Else, decrement the rear by 1 (or, rear = rear -1).

 Check empty

This operation is performed to check whether the deque is empty or not. If front = -1, it
means that the deque is empty.

Check full

This operation is performed to check whether the deque is full or not. If front = rear + 1,
or front = 0 and rear = n - 1 it means that the deque is full.

The time complexity of all of the above operations of the deque is O(1), i.e., constant.

Applications of deque
o Deque can be used as both stack and queue, as it supports both operations.
o Deque can be used as a palindrome checker means that if we read the string
from both ends, the string would be the same.

Implementation of deque
Now, let's see the implementation of deque in C programming language.

1. #include <stdio.h>
2. #define size 5
3. int deque[size];
4. int f = -1, r = -1;
5. // insert_front function will insert the value from the front
6. void insert_front(int x)
7. {
8. if((f==0 && r==size-1) || (f==r+1))
9. {
10. printf("Overflow");
11. }
12. else if((f==-1) && (r==-1))
13. {
14. f=r=0;
15. deque[f]=x;
16. }
17. else if(f==0)
18. {
19. f=size-1;
20. deque[f]=x;
21. }
22. else
23. {
24. f=f-1;
25. deque[f]=x;
26. }
27. }
28.
29. // insert_rear function will insert the value from the rear
30. void insert_rear(int x)
31. {
32. if((f==0 && r==size-1) || (f==r+1))
33. {
34. printf("Overflow");
35. }
36. else if((f==-1) && (r==-1))
37. {
38. r=0;
39. deque[r]=x;
40. }
41. else if(r==size-1)
42. {
43. r=0;
44. deque[r]=x;
45. }
46. else
47. {
48. r++;
49. deque[r]=x;
50. }
51.
52. }
53.
54. // display function prints all the value of deque.
55. void display()
56. {
57. int i=f;
58. printf("\nElements in a deque are: ");
59.
60. while(i!=r)
61. {
62. printf("%d ",deque[i]);
63. i=(i+1)%size;
64. }
65. printf("%d",deque[r]);
66. }
67.
68. // getfront function retrieves the first value of the deque.
69. void getfront()
70. {
71. if((f==-1) && (r==-1))
72. {
73. printf("Deque is empty");
74. }
75. else
76. {
77. printf("\nThe value of the element at front is: %d", deque[f]);
78. }
79.
80. }
81.
82. // getrear function retrieves the last value of the deque.
83. void getrear()
84. {
85. if((f==-1) && (r==-1))
86. {
87. printf("Deque is empty");
88. }
89. else
90. {
91. printf("\nThe value of the element at rear is %d", deque[r]);
92. }
93.
94. }
95.
96. // delete_front() function deletes the element from the front
97. void delete_front()
98. {
99. if((f==-1) && (r==-1))
100. {
101. printf("Deque is empty");
102. }
103. else if(f==r)
104. {
105. printf("\nThe deleted element is %d", deque[f]);
106. f=-1;
107. r=-1;
108.
109. }
110. else if(f==(size-1))
111. {
112. printf("\nThe deleted element is %d", deque[f]);
113. f=0;
114. }
115. else
116. {
117. printf("\nThe deleted element is %d", deque[f]);
118. f=f+1;
119. }
120. }
121.
122. // delete_rear() function deletes the element from the rear
123. void delete_rear()
124. {
125. if((f==-1) && (r==-1))
126. {
127. printf("Deque is empty");
128. }
129. else if(f==r)
130. {
131. printf("\nThe deleted element is %d", deque[r]);
132. f=-1;
133. r=-1;
134.
135. }
136. else if(r==0)
137. {
138. printf("\nThe deleted element is %d", deque[r]);
139. r=size-1;
140. }
141. else
142. {
143. printf("\nThe deleted element is %d", deque[r]);
144. r=r-1;
145. }
146. }
147.
148. int main()
149. {
150. insert_front(20);
151. insert_front(10);
152. insert_rear(30);
153. insert_rear(50);
154. insert_rear(80);
155. display(); // Calling the display function to retrieve the values of deque
156. getfront(); // Retrieve the value at front-end
157. getrear(); // Retrieve the value at rear-end
158. delete_front();
159. delete_rear();
160. display(); // calling display function to retrieve values after deletion
161. return 0;
162. }