Queue

1. A queue can be defined as an ordered list which enables insert operations to be

performed at one end called REAR and delete operations to be performed at
another end called FRONT.

2. Queue is referred to be as First In First Out list.

3. For example, people waiting in line for a rail ticket form a queue.

Applications of Queue
Due to the fact that queue performs actions on first in first out basis which is quite
fair for the ordering of actions. There are various applications of queues discussed as
below.

1. Queues are widely used as waiting lists for a single shared resource like printer, disk,
CPU.
2. Queues are used in asynchronous transfer of data (where data is not being
transferred at the same rate between two processes) for eg. pipes, file IO, sockets.
3. Queues are used as buffers in most of the applications like MP3 media player, CD
player, etc.
4. Queue are used to maintain the play list in media players in order to add and remove
the songs from the play-list.
5. Queues are used in operating systems for handling interrupts.
Complexity
Data Time Complexity Space
Structu Complei
re ty

Average Worst Worst

Acces Searc Inserti Deleti Acce Searc Inserti Deleti

s h on on ss h on on

Queue θ(n) θ(n) θ(1) θ(1) O(n) O(n) O(1) O(1) O(n)

Types of Queue
In this article, we will discuss the types of queue. But before moving towards the
types, we should first discuss the brief introduction of the queue.

What is a Queue?
Queue is the data structure that is similar to the queue in the real world. A queue is a
data structure in which whatever comes first will go out first, and it follows the FIFO
(First-In-First-Out) policy. Queue can also be defined as the list or collection in which
the insertion is done from one end known as the rear end or the tail of the queue,
whereas the deletion is done from another end known as the front end or
the head of the queue.

The real-world example of a queue is the ticket queue outside a cinema hall, where
the person who enters first in the queue gets the ticket first, and the last person
enters in the queue gets the ticket at last. Similar approach is followed in the queue
in data structure.

The representation of the queue is shown in the below image -

Now, let's move towards the types of queue.

Types of Queue
There are four different types of queue that are listed as follows -

o Simple Queue or Linear Queue

o Circular Queue
o Priority Queue
o Double Ended Queue (or Deque)

Let's discuss each of the type of queue.

Simple Queue or Linear Queue
In Linear Queue, an insertion takes place from one end while the deletion occurs
from another end. The end at which the insertion takes place is known as the rear
end, and the end at which the deletion takes place is known as front end. It strictly
follows the FIFO rule.

The major drawback of using a linear Queue is that insertion is done only from the
rear end. If the first three elements are deleted from the Queue, we cannot insert
more elements even though the space is available in a Linear Queue. In this case, the
linear Queue shows the overflow condition as the rear is pointing to the last element
of the Queue.

Circular Queue
In Circular Queue, all the nodes are represented as circular. It is similar to the linear
Queue except that the last element of the queue is connected to the first element. It
is also known as Ring Buffer, as all the ends are connected to another end. The
representation of circular queue is shown in the below image -

The drawback that occurs in a linear queue is overcome by using the circular queue.
If the empty space is available in a circular queue, the new element can be added in
an empty space by simply incrementing the value of rear. The main advantage of
using the circular queue is better memory utilization.
Priority Queue
It is a special type of queue in which the elements are arranged based on the priority.
It is a special type of queue data structure in which every element has a priority
associated with it. Suppose some elements occur with the same priority, they will be
arranged according to the FIFO principle. The representation of priority queue is
shown in the below image -

Insertion in priority queue takes place based on the arrival, while deletion in the
priority queue occurs based on the priority. Priority queue is mainly used to
implement the CPU scheduling algorithms.

There are two types of priority queue that are discussed as follows -

o Ascending priority queue - In ascending priority queue, elements can be inserted in

arbitrary order, but only smallest can be deleted first. Suppose an array with elements
7, 5, and 3 in the same order, so, insertion can be done with the same sequence, but
the order of deleting the elements is 3, 5, 7.
o Descending priority queue - In descending priority queue, elements can be inserted
in arbitrary order, but only the largest element can be deleted first. Suppose an array
with elements 7, 3, and 5 in the same order, so, insertion can be done with the same
sequence, but the order of deleting the elements is 7, 5, 3.

AD
AD

Deque (or, Double Ended Queue)

In Deque or Double Ended Queue, insertion and deletion can be done from both
ends of the queue either from the front or rear. It means that we can insert and
delete elements from both front and rear ends of the queue. Deque can be used as a
palindrome checker means that if we read the string from both ends, then the string
would be the same.

Deque can be used both as stack and queue as it allows the insertion and deletion
operations on both ends. Deque can be considered as stack because stack follows
the LIFO (Last In First Out) principle in which insertion and deletion both can be
performed only from one end. And in deque, it is possible to perform both insertion
and deletion from one end, and Deque does not follow the FIFO principle.

The representation of the deque is shown in the below image -

There are two types of deque that are discussed as follows -

AD

o Input restricted deque - As the name implies, in input restricted queue, insertion
operation can be performed at only one end, while deletion can be performed from
both ends.

o Output restricted deque - As the name implies, in output restricted queue, deletion
operation can be performed at only one end, while insertion can be performed from
 both ends.

Now, let's see the operations performed on the queue.

Operations performed on queue

The fundamental operations that can be performed on queue are listed as follows -

o Enqueue: The Enqueue operation is used to insert the element at the rear end of the
queue. It returns void.
o Dequeue: It performs the deletion from the front-end of the queue. It also returns
the element which has been removed from the front-end. It returns an integer value.
o Peek: This is the third operation that returns the element, which is pointed by the
front pointer in the queue but does not delete it.
o Queue overflow (isfull): It shows the overflow condition when the queue is
completely full.
o Queue underflow (isempty): It shows the underflow condition when the Queue is
empty, i.e., no elements are in the Queue.

Now, let's see the ways to implement the queue.

Ways to implement the queue

There are two ways of implementing the Queue:

o Implementation using array: The sequential allocation in a Queue can be

implemented using an array.
Array representation of Queue
We can easily represent queue by using linear arrays. There are two variables i.e.
front and rear, that are implemented in the case of every queue. Front and rear
variables point to the position from where insertions and deletions are performed in
a queue. Initially, the value of front and queue is -1 which represents an empty
queue. Array representation of a queue containing 5 elements along with the
respective values of front and rear, is shown in the following figure.

The above figure shows the queue of characters forming the English word "HELLO".
Since, No deletion is performed in the queue till now, therefore the value of front
remains -1 . However, the value of rear increases by one every time an insertion is
performed in the queue. After inserting an element into the queue shown in the
above figure, the queue will look something like following. The value of rear will
become 5 while the value of front remains same.
After deleting an element, the value of front will increase from -1 to 0. however, the
queue will look something like following.

Algorithm to insert any element in a queue

Check if the queue is already full by comparing rear to max - 1. if so, then return an
overflow error.

If the item is to be inserted as the first element in the list, in that case set the value of
front and rear to 0 and insert the element at the rear end.
 Otherwise keep increasing the value of rear and insert each element one by one
having rear as the index.

Algorithm
o Step 1: IF REAR = MAX - 1
Write OVERFLOW
Go to step
[END OF IF]
o Step 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR = 0
ELSE
SET REAR = REAR + 1
[END OF IF]
o Step 3: Set QUEUE[REAR] = NUM
o Step 4: EXIT

AD

C Function
1. void insert (int queue[], int max, int front, int rear, int item)
2. {
3. if (rear + 1 == max)
4. {
5. printf("overflow");
6. }
7. else
8. {
9. if(front == -1 && rear == -1)
10. {
11. front = 0;
12. rear = 0;
13. }
14. else
15. {
16. rear = rear + 1;
17. }
18. queue[rear]=item;
19. }
20. }

Algorithm to delete an element from the queue

If, the value of front is -1 or value of front is greater than rear , write an underflow
message and exit.

Otherwise, keep increasing the value of front and return the item stored at the front
end of the queue at each time.

Algorithm
o Step 1: IF FRONT = -1 or FRONT > REAR
Write UNDERFLOW
ELSE
SET VAL = QUEUE[FRONT]
SET FRONT = FRONT + 1
[END OF IF]
o Step 2: EXIT

AD
AD

C Function
1. int delete (int queue[], int max, int front, int rear)
2. {
3. int y;
4. if (front == -1 || front > rear)
5.
6. {
7. printf("underflow");
8. }
9. else
10. {
11. y = queue[front];
12. if(front == rear)
13. {
14. front = rear = -1;
15. else
16. front = front + 1;
17.
18. }
19. return y;
20. }
21. }
AD

Menu driven program to implement queue using

array
1. #include<stdio.h>
2. #include<stdlib.h>
3. #define maxsize 5
4. void insert();
5. void delete();
6. void display();
7. int front = -1, rear = -1;
8. int queue[maxsize];
9. void main ()
10. {
11. int choice;
12. while(choice != 4)
13. {
14. printf("\n*************************Main Menu*****************************\n");
15. printf("\n==================================================
===============\n");
16. printf("\n1.insert an element\n2.Delete an element\n3.Display the queue\n4.Exit\n");
17. printf("\nEnter your choice ?");
18. scanf("%d",&choice);
19. switch(choice)
20. {
21. case 1:
22. insert();
23. break;
24. case 2:
25. delete();
26. break;
27. case 3:
28. display();
29. break;
30. case 4:
31. exit(0);
32. break;
33. default:
34. printf("\nEnter valid choice??\n");
35. }
36. }
37. }
38. void insert()
39. {
40. int item;
41. printf("\nEnter the element\n");
42. scanf("\n%d",&item);
43. if(rear == maxsize-1)
44. {
45. printf("\nOVERFLOW\n");
46. return;
47. }
48. if(front == -1 && rear == -1)
49. {
50. front = 0;
51. rear = 0;
52. }
53. else
54. {
55. rear = rear+1;
56. }
57. queue[rear] = item;
58. printf("\nValue inserted ");
59.
60. }
61. void delete()
62. {
63. int item;
64. if (front == -1 || front > rear)
65. {
66. printf("\nUNDERFLOW\n");
67. return;
68.
69. }
70. else
71. {
72. item = queue[front];
73. if(front == rear)
74. {
75. front = -1;
76. rear = -1 ;
77. }
78. else
79. {
80. front = front + 1;
81. }
82. printf("\nvalue deleted ");
83. }
84.
85.
86. }
87.
88. void display()
89. {
90. int i;
91. if(rear == -1)
92. {
93. printf("\nEmpty queue\n");
94. }
95. else
96. { printf("\nprinting values .....\n");
97. for(i=front;i<=rear;i++)
98. {
99. printf("\n%d\n",queue[i]);
100. }
101. }
102. }
C++ Program: Queue Implementation
#include <iostream>
#define maxsize 5

using namespace std;

void insert();
void deleteElement();
void display();

int front = -1, rear = -1;

int queue[maxsize];

int main() {
int choice;
while (choice != 4) {
cout << "\n*************************Main
Menu*****************************\n";
cout <<
"\n=================================================================\n";
cout << "\n1. Insert an element\n2. Delete an element\n3. Display
the queue\n4. Exit\n";
cout << "\nEnter your choice: ";
cin >> choice;
switch (choice) {
case 1:
insert();
break;
case 2:
deleteElement();
break;
case 3:
display();
break;
case 4:
exit(0);
default:
cout << "\nEnter a valid choice\n";
}
}
return 0;
}

void insert() {
int item;
cout << "\nEnter the element: ";
cin >> item;

if (rear == maxsize - 1) {
cout << "\nOVERFLOW\n";
return;
}

if (front == -1 && rear == -1) {

front = 0;
rear = 0;
} else {
rear++;
}
 queue[rear] = item;
cout << "\nValue inserted\n";
}

void deleteElement() {
int item;

if (front == -1 || front > rear) {

cout << "\nUNDERFLOW\n";
return;
} else {
item = queue[front];

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

cout << "\nValue deleted\n";

}
}

void display() {
if (rear == -1) {
cout << "\nEmpty queue\n";
} else {
cout << "\nPrinting values...\n";
for (int i = front; i <= rear; i++) {
cout << queue[i] << " ";
}
cout << endl;
}
}

Algorithm:

1. Start.
2. Initialize front and rear to -1.
3. Display the main menu with options: Insert, Delete, Display, and Exit.
4. Based on the user's choice:
o If choice = 1: Call insert() to add an element to the queue.
 If the queue is full, display "OVERFLOW".
 If the queue is empty (i.e., both front and rear are -1), initialize
front and rear to 0.
 Otherwise, increment rear and add the element.
o If choice = 2: Call deleteElement() to remove an element from the queue.
 If the queue is empty or front exceeds rear, display
"UNDERFLOW".
 Remove the element at front, increment front, or reset front and
rear if the queue becomes empty.
o If choice = 3: Call display() to display the queue.
 If the queue is empty, display "Empty queue".
 Otherwise, print all elements between front and rear.
 o If choice = 4: Exit the program.
5. Repeat until choice = 4.
6. End.

Pseudocode:
START
Initialize front = -1, rear = -1
WHILE (choice != 4)
Display main menu
Input choice
IF choice == 1 THEN
CALL insert()
ELSE IF choice == 2 THEN
CALL deleteElement()
ELSE IF choice == 3 THEN
CALL display()
ELSE IF choice == 4 THEN
EXIT program
ELSE
Display "Enter a valid choice"
END WHILE
END

FUNCTION insert()
IF rear == maxsize - 1 THEN
Display "OVERFLOW"
RETURN
IF front == -1 AND rear == -1 THEN
front = 0
rear = 0
ELSE
Increment rear
Input item
queue[rear] = item
Display "Value inserted"
END FUNCTION

FUNCTION deleteElement()
IF front == -1 OR front > rear THEN
Display "UNDERFLOW"
RETURN
SET item = queue[front]
IF front == rear THEN
front = -1
rear = -1
ELSE
Increment front
Display "Value deleted"
END FUNCTION

FUNCTION display()
IF rear == -1 THEN
Display "Empty queue"
RETURN
Display "Printing values..."
FOR i FROM front TO rear
 Display queue[i]
END FOR
END FUNCTION

Explanation:

This program simulates a queue using an array in C++. It has three main functions:

1. Insert:
o Adds an element to the rear of the queue. It first checks if the queue is full. If
not, it either initializes front and rear (for the first insertion) or increments
rear for subsequent insertions.
2. Delete:
o Removes an element from the front of the queue. It first checks if the queue is
empty. If not, it deletes the front element and updates the front pointer. If the
queue becomes empty after deletion, both front and rear are reset.
3. Display:
o Prints all the elements in the queue from front to rear. If the queue is empty,
it displays a message.

These functions allow basic queue operations—enqueue, dequeue, and displaying queue
contents—through a menu-driven interface.

Output:

*************Main Menu**************

==============================================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?1

Enter the element

123

Value inserted

*************Main Menu**************

==============================================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?1

Enter the element

90

Value inserted

*************Main Menu**************

===================================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?2

value deleted

*************Main Menu**************
==============================================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?3

printing values .....

90

*************Main Menu**************

==============================================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?4

AD

Drawback of array implementation

Although, the technique of creating a queue is easy, but there are some drawbacks
of using this technique to implement a queue.

o Memory wastage : The space of the array, which is used to store queue elements,
can never be reused to store the elements of that queue because the elements can
only be inserted at front end and the value of front might be so high so that, all the
space before that, can never be filled.
The above figure shows how the memory space is wasted in the array representation
of queue. In the above figure, a queue of size 10 having 3 elements, is shown. The
value of the front variable is 5, therefore, we can not reinsert the values in the place
of already deleted element before the position of front. That much space of the array
is wasted and can not be used in the future (for this queue).

o Deciding the array size

On of the most common problem with array implementation is the size of the array
which requires to be declared in advance. Due to the fact that, the queue can be
extended at runtime depending upon the problem, the extension in the array size is a
time taking process and almost impossible to be performed at runtime since a lot of
reallocations take place. Due to this reason, we can declare the array large enough so
that we can store queue elements as enough as possible but the main problem with
this declaration is that, most of the array slots (nearly half) can never be reused. It will
again lead to memory wastage.

o Implementation using Linked list: The linked list allocation in a Queue can be
implemented using a linked list.

Linked List implementation of Queue

Due to the drawbacks discussed in the previous section of this tutorial, the array
implementation can not be used for the large scale applications where the queues
are implemented. One of the alternative of array implementation is linked list
implementation of queue.
 The storage requirement of linked representation of a queue with n elements is o(n)
while the time requirement for operations is o(1).

In a linked queue, each node of the queue consists of two parts i.e. data part and the
link part. Each element of the queue points to its immediate next element in the
memory.

In the linked queue, there are two pointers maintained in the memory i.e. front
pointer and rear pointer. The front pointer contains the address of the starting
element of the queue while the rear pointer contains the address of the last element
of the queue.

Insertion and deletions are performed at rear and front end respectively. If front and
rear both are NULL, it indicates that the queue is empty.

The linked representation of queue is shown in the following figure.

Operation on Linked Queue

There are two basic operations which can be implemented on the linked queues. The
operations are Insertion and Deletion.

Insert operation
The insert operation append the queue by adding an element to the end of the
queue. The new element will be the last element of the queue.

Firstly, allocate the memory for the new node ptr by using the following statement.

1. Ptr = (struct node *) malloc (sizeof(struct node));

There can be the two scenario of inserting this new node ptr into the linked queue.
 In the first scenario, we insert element into an empty queue. In this case, the
condition front = NULL becomes true. Now, the new element will be added as the
only element of the queue and the next pointer of front and rear pointer both, will
point to NULL.

1. ptr -> data = item;

2. if(front == NULL)
3. {
4. front = ptr;
5. rear = ptr;
6. front -> next = NULL;
7. rear -> next = NULL;
8. }

In the second case, the queue contains more than one element. The condition front
= NULL becomes false. In this scenario, we need to update the end pointer rear so
that the next pointer of rear will point to the new node ptr. Since, this is a linked
queue, hence we also need to make the rear pointer point to the newly added
node ptr. We also need to make the next pointer of rear point to NULL.

1. rear -> next = ptr;

2. rear = ptr;
3. rear->next = NULL;

In this way, the element is inserted into the queue. The algorithm and the C
implementation is given as follows.

AD

Algorithm
o Step 1: Allocate the space for the new node PTR
o Step 2: SET PTR -> DATA = VAL
o Step 3: IF FRONT = NULL
SET FRONT = REAR = PTR
SET FRONT -> NEXT = REAR -> NEXT = NULL
ELSE
SET REAR -> NEXT = PTR
SET REAR = PTR
SET REAR -> NEXT = NULL
[END OF IF]
 o Step 4: END

C Function
1. void insert(struct node *ptr, int item; )
2. {
3.
4.
5. ptr = (struct node *) malloc (sizeof(struct node));
6. if(ptr == NULL)
7. {
8. printf("\nOVERFLOW\n");
9. return;
10. }
11. else
12. {
13. ptr -> data = item;
14. if(front == NULL)
15. {
16. front = ptr;
17. rear = ptr;
18. front -> next = NULL;
19. rear -> next = NULL;
20. }
21. else
22. {
23. rear -> next = ptr;
24. rear = ptr;
25. rear->next = NULL;
26. }
27. }
28. }

Deletion
Deletion operation removes the element that is first inserted among all the queue
elements. Firstly, we need to check either the list is empty or not. The condition front
== NULL becomes true if the list is empty, in this case , we simply write underflow on
the console and make exit.
 Otherwise, we will delete the element that is pointed by the pointer front. For this
purpose, copy the node pointed by the front pointer into the pointer ptr. Now, shift
the front pointer, point to its next node and free the node pointed by the node ptr.
This is done by using the following statements.

1. ptr = front;
2. front = front -> next;
3. free(ptr);

The algorithm and C function is given as follows.

AD

Algorithm
o Step 1: IF FRONT = NULL
Write " Underflow "
Go to Step 5
[END OF IF]
o Step 2: SET PTR = FRONT
o Step 3: SET FRONT = FRONT -> NEXT
o Step 4: FREE PTR
o Step 5: END

AD
AD

C Function
1. void delete (struct node *ptr)
2. {
3. if(front == NULL)
4. {
5. printf("\nUNDERFLOW\n");
6. return;
7. }
8. else
9. {
10. ptr = front;
11. front = front -> next;
12. free(ptr);
13. }
14. }
AD

Menu-Driven Program implementing all the

operations on Linked Queue
1. #include<stdio.h>
2. #include<stdlib.h>
3. struct node
4. {
5. int data;
6. struct node *next;
7. };
8. struct node *front;
9. struct node *rear;
10. void insert();
11. void delete();
12. void display();
13. void main ()
14. {
15. int choice;
16. while(choice != 4)
17. {
18. printf("\n*************************Main Menu*****************************\n");
19. printf("\n==================================================
===============\n");
20. printf("\n1.insert an element\n2.Delete an element\n3.Display the queue\n4.Exit\n");
21. printf("\nEnter your choice ?");
22. scanf("%d",& choice);
23. switch(choice)
24. {
25. case 1:
26. insert();
27. break;
28. case 2:
29. delete();
30. break;
31. case 3:
32. display();
33. break;
34. case 4:
35. exit(0);
36. break;
37. default:
38. printf("\nEnter valid choice??\n");
39. }
40. }
41. }
42. void insert()
43. {
44. struct node *ptr;
45. int item;
46.
47. ptr = (struct node *) malloc (sizeof(struct node));
48. if(ptr == NULL)
49. {
50. printf("\nOVERFLOW\n");
51. return;
52. }
53. else
54. {
55. printf("\nEnter value?\n");
56. scanf("%d",&item);
57. ptr -> data = item;
58. if(front == NULL)
59. {
60. front = ptr;
61. rear = ptr;
62. front -> next = NULL;
63. rear -> next = NULL;
64. }
65. else
66. {
67. rear -> next = ptr;
68. rear = ptr;
69. rear->next = NULL;
70. }
71. }
72. }
73. void delete ()
74. {
75. struct node *ptr;
76. if(front == NULL)
77. {
78. printf("\nUNDERFLOW\n");
79. return;
80. }
81. else
82. {
83. ptr = front;
84. front = front -> next;
85. free(ptr);
86. }
87. }
88. void display()
89. {
90. struct node *ptr;
91. ptr = front;
92. if(front == NULL)
93. {
94. printf("\nEmpty queue\n");
95. }
96. else
97. { printf("\nprinting values .....\n");
98. while(ptr != NULL)
99. {
100. printf("\n%d\n",ptr -> data);
101. ptr = ptr -> next;
102. }
103. }
104. }
C++ Code: Queue Implementation Using Linked List
#include <iostream>
using namespace std;

struct Node {
int data;
Node* next;
};

Node* front = NULL;

Node* rear = NULL;

void insert();
void deleteElement();
void display();

int main() {
int choice;
while (choice != 4) {
cout << "\n*************************Main
Menu*****************************\n";
cout <<
"\n=================================================================\n";
cout << "\n1. Insert an element\n2. Delete an element\n3. Display
the queue\n4. Exit\n";
cout << "\nEnter your choice: ";
cin >> choice;
switch (choice) {
case 1:
insert();
break;
case 2:
deleteElement();
break;
case 3:
display();
break;
case 4:
exit(0);
default:
cout << "\nEnter a valid choice\n";
}
}
return 0;
}

void insert() {
Node* ptr = new Node;
if (ptr == NULL) {
cout << "\nOVERFLOW\n";
return;
}

int item;
cout << "\nEnter value: ";
cin >> item;

ptr->data = item;
ptr->next = NULL;
 if (front == NULL) {
front = ptr;
rear = ptr;
} else {
rear->next = ptr;
rear = ptr;
}

cout << "\nValue inserted\n";

}

void deleteElement() {
if (front == NULL) {
cout << "\nUNDERFLOW\n";
return;
}

Node* ptr = front;

front = front->next;
delete ptr;

cout << "\nValue deleted\n";

}

void display() {
if (front == NULL) {
cout << "\nEmpty queue\n";
return;
}

Node* ptr = front;

cout << "\nPrinting values...\n";
while (ptr != NULL) {
cout << ptr->data << " ";
ptr = ptr->next;
}
cout << endl;
}

Algorithm:

1. Start.
2. Initialize front and rear pointers to NULL (empty queue).
3. Display the main menu with options: Insert, Delete, Display, and Exit.
4. Based on the user's choice:
o Insert:
 Create a new node using dynamic memory allocation.
 If memory allocation fails, display "OVERFLOW".
 If the queue is empty, set both front and rear to the new node.
 Otherwise, link the new node at the end of the queue and update rear.
o Delete:
 If the queue is empty, display "UNDERFLOW".
 Otherwise, remove the front node, update front, and free the memory.
o Display:
 If the queue is empty, display "Empty queue".
 Otherwise, traverse from front to rear and print the elements.
 o Exit: Terminate the program.
5. Repeat until choice = 4.
6. End.

Pseudocode:
START
Initialize front = NULL, rear = NULL
WHILE (choice != 4)
Display main menu
Input choice
IF choice == 1 THEN
CALL insert()
ELSE IF choice == 2 THEN
CALL deleteElement()
ELSE IF choice == 3 THEN
CALL display()
ELSE IF choice == 4 THEN
EXIT program
ELSE
Display "Enter a valid choice"
END WHILE
END

FUNCTION insert()
Create a new node (ptr)
IF ptr == NULL THEN
Display "OVERFLOW"
RETURN
Input item
ptr->data = item
ptr->next = NULL
IF front == NULL THEN
front = ptr
rear = ptr
ELSE
rear->next = ptr
rear = ptr
Display "Value inserted"
END FUNCTION

FUNCTION deleteElement()
IF front == NULL THEN
Display "UNDERFLOW"
RETURN
SET ptr = front
front = front->next
Free ptr
Display "Value deleted"
END FUNCTION

FUNCTION display()
IF front == NULL THEN
Display "Empty queue"
RETURN
SET ptr = front
WHILE ptr != NULL
 Display ptr->data
ptr = ptr->next
END WHILE
END FUNCTION

Explanation:

This C++ program implements a queue using a linked list structure. A queue follows the
FIFO (First In, First Out) principle, where elements are added at the rear and removed from
the front.

 Node Structure: Each node has two parts: data (to store the element) and next (a
pointer to the next node in the queue).
 Queue Operations:
o Insert:
 A new node is dynamically created using new. If memory allocation
fails, the program outputs "OVERFLOW".
 The new node is added to the queue. If the queue is empty, both front
and rear point to the new node. Otherwise, the new node is linked at
the end, and rear is updated.
o Delete:
 If the queue is empty, the program outputs "UNDERFLOW".
 The node at the front is removed, and the pointer front is updated.
The removed node is deallocated using delete.
o Display:
 The program traverses the queue from front to rear and prints the
data of each node.

The program uses a menu-driven approach, allowing the user to choose between inserting,
deleting, displaying the queue, or exiting the program.

Output:

AD

***********Main Menu**********

==============================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?1

Enter value?
123

***********Main Menu**********
==============================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?1

Enter value?
90

***********Main Menu**********

==============================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?3

printing values .....

123

90

***********Main Menu**********

==============================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?2

***********Main Menu**********

==============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?3

printing values .....

90

***********Main Menu**********

==============================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?4

Circular Queue
Why was the concept of the circular queue introduced?
There was one limitation in the array implementation of Queue. If the rear reaches to
the end position of the Queue then there might be possibility that some vacant
spaces are left in the beginning which cannot be utilized. So, to overcome such
limitations, the concept of the circular queue was introduced.

As we can see in the above image, the rear is at the last position of the Queue and
front is pointing somewhere rather than the 0th position. In the above array, there are
only two elements and other three positions are empty. The rear is at the last
position of the Queue; if we try to insert the element then it will show that there are
no empty spaces in the Queue. There is one solution to avoid such wastage of
memory space by shifting both the elements at the left and adjust the front and rear
end accordingly. It is not a practically good approach because shifting all the
elements will consume lots of time. The efficient approach to avoid the wastage of
the memory is to use the circular queue data structure.

What is a Circular Queue?

A circular queue is similar to a linear queue as it is also based on the FIFO (First In
First Out) principle except that the last position is connected to the first position in a
circular queue that forms a circle. It is also known as a Ring Buffer.

Operations on Circular Queue

The following are the operations that can be performed on a circular queue:

o Front: It is used to get the front element from the Queue.

o Rear: It is used to get the rear element from the Queue.
o enQueue(value): This function is used to insert the new value in the Queue. The new
element is always inserted from the rear end.
o deQueue(): This function deletes an element from the Queue. The deletion in a
Queue always takes place from the front end.

Applications of Circular Queue

The circular Queue can be used in the following scenarios:

o Memory management: The circular queue provides memory management. As we

have already seen that in linear queue, the memory is not managed very efficiently.
But in case of a circular queue, the memory is managed efficiently by placing the
elements in a location which is unused.
o CPU Scheduling: The operating system also uses the circular queue to insert the
processes and then execute them.
o Traffic system: In a computer-control traffic system, traffic light is one of the best
examples of the circular queue. Each light of traffic light gets ON one by one after
every jinterval of time. Like red light gets ON for one minute then yellow light for one
minute and then green light. After green light, the red light gets ON.

AD
Enqueue operation
The steps of enqueue operation are given below:

o First, we will check whether the Queue is full or not.

o Initially the front and rear are set to -1. When we insert the first element in a Queue,
front and rear both are set to 0.
o When we insert a new element, the rear gets incremented, i.e., rear=rear+1.

Scenarios for inserting an element

There are two scenarios in which queue is not full:

o If rear != max - 1, then rear will be incremented to mod(maxsize) and the new
value will be inserted at the rear end of the queue.
o If front != 0 and rear = max - 1, it means that queue is not full, then set the value of
rear to 0 and insert the new element there.

There are two cases in which the element cannot be inserted:

o When front ==0 && rear = max-1, which means that front is at the first position of
the Queue and rear is at the last position of the Queue.
o front== rear + 1;

Algorithm to insert an element in a circular queue

Step 1: IF (REAR+1)%MAX = FRONT

Write " OVERFLOW "
Goto step 4
[End OF IF]

Step 2: IF FRONT = -1 and REAR = -1

SET FRONT = REAR = 0
ELSE IF REAR = MAX - 1 and FRONT ! = 0
SET REAR = 0
ELSE
SET REAR = (REAR + 1) % MAX
[END OF IF]

Step 3: SET QUEUE[REAR] = VAL

Step 4: EXIT
Dequeue Operation
The steps of dequeue operation are given below:

o First, we check whether the Queue is empty or not. If the queue is empty, we cannot
perform the dequeue operation.
o When the element is deleted, the value of front gets decremented by 1.
o If there is only one element left which is to be deleted, then the front and rear are
reset to -1.

Algorithm to delete an element from the circular queue

Step 1: IF FRONT = -1
Write " UNDERFLOW "
Goto Step 4
[END of IF]

Step 2: SET VAL = QUEUE[FRONT]

AD

Step 3: IF FRONT = REAR

SET FRONT = REAR = -1
ELSE
IF FRONT = MAX -1
SET FRONT = 0
ELSE
SET FRONT = FRONT + 1
[END of IF]
[END OF IF]

Step 4: EXIT

Let's understand the enqueue and dequeue operation through the

diagrammatic representation.
 Implementation of circular queue using Array

1. #include <stdio.h>
2.
3. # define max 6
4. int queue[max]; // array declaration
5. int front=-1;
6. int rear=-1;
7. // function to insert an element in a circular queue
8. void enqueue(int element)
9. {
10. if(front==-1 && rear==-1) // condition to check queue is empty
11. {
12. front=0;
13. rear=0;
14. queue[rear]=element;
15. }
16. else if((rear+1)%max==front) // condition to check queue is full
17. {
18. printf("Queue is overflow..");
19. }
20. else
21. {
22. rear=(rear+1)%max; // rear is incremented
23. queue[rear]=element; // assigning a value to the queue at the rear position.
24. }
25. }
26.
27. // function to delete the element from the queue
28. int dequeue()
29. {
30. if((front==-1) && (rear==-1)) // condition to check queue is empty
31. {
32. printf("\nQueue is underflow..");
33. }
34. else if(front==rear)
35. {
36. printf("\nThe dequeued element is %d", queue[front]);
37. front=-1;
38. rear=-1;
39. }
40. else
41. {
42. printf("\nThe dequeued element is %d", queue[front]);
43. front=(front+1)%max;
44. }
45. }
46. // function to display the elements of a queue
47. void display()
48. {
49. int i=front;
50. if(front==-1 && rear==-1)
51. {
52. printf("\n Queue is empty..");
53. }
54. else
55. {
56. printf("\nElements in a Queue are :");
57. while(i<=rear)
58. {
59. printf("%d,", queue[i]);
60. i=(i+1)%max;
61. }
62. }
63. }
64. int main()
65. {
66. int choice=1,x; // variables declaration
67.
68. while(choice<4 && choice!=0) // while loop
69. {
70. printf("\n Press 1: Insert an element");
71. printf("\nPress 2: Delete an element");
72. printf("\nPress 3: Display the element");
73. printf("\nEnter your choice");
74. scanf("%d", &choice);
75.
76. switch(choice)
77. {
78.
79. case 1:
80.
81. printf("Enter the element which is to be inserted");
82. scanf("%d", &x);
83. enqueue(x);
84. break;
85. case 2:
86. dequeue();
87. break;
88. case 3:
89. display();
90.
91. }}
92. return 0;
93. }

C++ Code
#include <iostream>
#define max 6

using namespace std;

int queue[max]; // Array declaration

int front = -1;
int rear = -1;

// Function to insert an element in a circular queue

void enqueue(int element) {
if (front == -1 && rear == -1) { // Check if the queue is empty
front = 0;
rear = 0;
queue[rear] = element;
} else if ((rear + 1) % max == front) { // Check if the queue is full
cout << "Queue is overflow.." << endl;
} else {
rear = (rear + 1) % max; // Increment rear
queue[rear] = element; // Assign the value to the queue at rear
}
}

// Function to delete the element from the queue

int dequeue() {
if (front == -1 && rear == -1) { // Check if the queue is empty
cout << "Queue is underflow.." << endl;
} else if (front == rear) { // Check if only one element is present
cout << "The dequeued element is " << queue[front] << endl;
front = -1;
rear = -1;
} else {
cout << "The dequeued element is " << queue[front] << endl;
front = (front + 1) % max; // Increment front
}
return 0;
}

// Function to display the elements of the queue

void display() {
if (front == -1 && rear == -1) {
cout << "Queue is empty.." << endl;
} else {
int i = front;
cout << "Elements in the Queue are: ";
while (i != rear) {
cout << queue[i] << ",";
i = (i + 1) % max;
}
cout << queue[rear] << endl; // Display the last element
}
}

int main() {
int choice = 1, x; // Variable declaration

while (choice < 4 && choice != 0) { // While loop for menu

cout << "\nPress 1: Insert an element";
cout << "\nPress 2: Delete an element";
cout << "\nPress 3: Display the elements";
cout << "\nEnter your choice: ";
cin >> choice;

switch (choice) {
case 1:
cout << "Enter the element to be inserted: ";
cin >> x;
enqueue(x);
break;
case 2:
dequeue();
break;
case 3:
display();
break;
default:
cout << "Invalid choice!" << endl;
}
}
return 0;
}

Pseudocode
Initialize queue as an array of fixed size max
Set front and rear to -1

Function enqueue(element):
If front == -1 and rear == -1:
Set front = 0
Set rear = 0
Set queue[rear] = element
Else if (rear + 1) % max == front: // Queue is full
Print "Queue is overflow"
Else:
Increment rear using (rear + 1) % max
Set queue[rear] = element

Function dequeue():
 If front == -1 and rear == -1: // Queue is empty
Print "Queue is underflow"
Else if front == rear: // Only one element
Print the dequeued element
Set front = -1
Set rear = -1
Else:
Print the dequeued element
Increment front using (front + 1) % max

Function display():
If front == -1 and rear == -1: // Queue is empty
Print "Queue is empty"
Else:
Initialize i = front
Loop while i != rear:
Print queue[i]
Set i = (i + 1) % max
Print the last element queue[rear]

Main program:
Repeat until user chooses to exit:
Display options to insert, delete, or display
Perform corresponding operation based on user input

Algorithm

1. Initialize the Queue:

o Create an array of size max to store the queue.
o Set front and rear to -1 indicating an empty queue.
2. Enqueue Operation:
o If front == -1 and rear == -1, the queue is empty. Set both front and
rear to 0, and insert the element.
o If (rear + 1) % max == front, the queue is full, and no more elements can
be added.
o Otherwise, increment the rear position using (rear + 1) % max and insert
the element at that position.
3. Dequeue Operation:
o If front == -1 and rear == -1, the queue is empty, and there is no element
to dequeue.
o If front == rear, there is only one element in the queue. Dequeue the
element and reset front and rear to -1.
o Otherwise, increment front using (front + 1) % max and return the
dequeued element.
4. Display Operation:
o If front == -1 and rear == -1, the queue is empty.
o Otherwise, loop through the queue starting from front to rear using modulo
arithmetic to handle the circular nature of the queue, and print all elements.
Explanation

This C++ program demonstrates a circular queue using an array. A circular queue allows
elements to be stored in a cyclic manner, meaning when the rear of the queue reaches the last
position of the array, it wraps around to the beginning if there's free space. The enqueue
function inserts elements into the queue, while the dequeue function removes elements from
the front. The display function prints all the elements currently in the queue.

 Enqueue adds an element at the rear end of the queue and ensures the queue doesn't
overflow by checking if it's full.
 Dequeue removes an element from the front and ensures the queue doesn't
underflow by checking if it's empty.
 The circular nature is maintained using modulo arithmetic ( % max), which allows the
queue to wrap around when the rear or front reaches the end of the array.

Output:
 Implementation of circular queue using linked list
As we know that linked list is a linear data structure that stores two parts, i.e., data
part and the address part where address part contains the address of the next node.
Here, linked list is used to implement the circular queue; therefore, the linked list
follows the properties of the Queue. When we are implementing the circular queue
using linked list then both the enqueue and dequeue operations take O(1) time.

AD

1. #include <stdio.h>
2. // Declaration of struct type node
3. struct node
4. {
5. int data;
6. struct node *next;
7. };
8. struct node *front=-1;
9. struct node *rear=-1;
10. // function to insert the element in the Queue
11. void enqueue(int x)
12. {
13. struct node *newnode; // declaration of pointer of struct node type.
14. newnode=(struct node *)malloc(sizeof(struct node)); // allocating the memory to the ne
wnode
15. newnode->data=x;
16. newnode->next=0;
17. if(rear==-1) // checking whether the Queue is empty or not.
18. {
19. front=rear=newnode;
20. rear->next=front;
21. }
22. else
23. {
24. rear->next=newnode;
25. rear=newnode;
26. rear->next=front;
27. }
28. }
29.
30. // function to delete the element from the queue
31. void dequeue()
32. {
33. struct node *temp; // declaration of pointer of node type
34. temp=front;
35. if((front==-1)&&(rear==-1)) // checking whether the queue is empty or not
36. {
37. printf("\nQueue is empty");
38. }
39. else if(front==rear) // checking whether the single element is left in the queue
40. {
41. front=rear=-1;
42. free(temp);
43. }
44. else
45. {
46. front=front->next;
47. rear->next=front;
48. free(temp);
49. }
50. }
51.
52. // function to get the front of the queue
53. int peek()
54. {
55. if((front==-1) &&(rear==-1))
56. {
57. printf("\nQueue is empty");
58. }
59. else
60. {
61. printf("\nThe front element is %d", front->data);
62. }
63. }
64.
65. // function to display all the elements of the queue
66. void display()
67. {
68. struct node *temp;
69. temp=front;
70. printf("\n The elements in a Queue are : ");
71. if((front==-1) && (rear==-1))
72. {
73. printf("Queue is empty");
74. }
75.
76. else
77. {
78. while(temp->next!=front)
79. {
80. printf("%d,", temp->data);
81. temp=temp->next;
82. }
83. printf("%d", temp->data);
84. }
85. }
86.
87. void main()
88. {
89. enqueue(34);
90. enqueue(10);
91. enqueue(23);
92. display();
93. dequeue();
94. peek();
95. }

C++ Code
#include <iostream>
#include <cstdlib> // for malloc and free
using namespace std;

// Declaration of struct node

struct node {
int data;
struct node *next;
};

struct node *front = nullptr;

struct node *rear = nullptr;

// Function to insert an element into the queue

void enqueue(int x) {
struct node *newnode; // Declaration of pointer of struct node type
newnode = (struct node *)malloc(sizeof(struct node)); // Allocating
memory
newnode->data = x;
newnode->next = nullptr;

if (rear == nullptr) { // Check if the queue is empty

front = rear = newnode;
 rear->next = front;
} else {
rear->next = newnode;
rear = newnode;
rear->next = front;
}
}

// Function to delete an element from the queue

void dequeue() {
struct node *temp;
temp = front;

if (front == nullptr && rear == nullptr) { // Check if queue is empty

cout << "\nQueue is empty";
} else if (front == rear) { // Check if only one element is in the
queue
front = rear = nullptr;
free(temp);
} else {
front = front->next;
rear->next = front;
free(temp);
}
}

// Function to get the front element of the queue

int peek() {
if (front == nullptr && rear == nullptr) {
cout << "\nQueue is empty";
return -1; // Return a default value
} else {
cout << "\nThe front element is " << front->data;
return front->data;
}
}

// Function to display all the elements in the queue

void display() {
struct node *temp;
temp = front;

if (front == nullptr && rear == nullptr) {

cout << "\nQueue is empty";
} else {
cout << "\nThe elements in a Queue are: ";
while (temp->next != front) {
cout << temp->data << ",";
temp = temp->next;
}
cout << temp->data;
}
}

int main() {
enqueue(34);
enqueue(10);
enqueue(23);
display();
dequeue();
peek();
 return 0;
}

Pseudo Code
STRUCT node
int data
node* next

DECLARE front = nullptr

DECLARE rear = nullptr

FUNCTION enqueue(x):
CREATE newnode
newnode.data = x
newnode.next = nullptr

IF rear IS nullptr:
front = rear = newnode
rear.next = front
ELSE:
rear.next = newnode
rear = newnode
rear.next = front

FUNCTION dequeue():
IF front IS nullptr AND rear IS nullptr:
PRINT "Queue is empty"
ELSE IF front == rear:
front = rear = nullptr
ELSE:
front = front.next
rear.next = front

FUNCTION peek():
IF front IS nullptr AND rear IS nullptr:
PRINT "Queue is empty"
ELSE:
PRINT "The front element is" front.data

FUNCTION display():
IF front IS nullptr AND rear IS nullptr:
PRINT "Queue is empty"
ELSE:
SET temp = front
WHILE temp.next IS NOT front:
PRINT temp.data
SET temp = temp.next
PRINT temp.data

Algorithm

1. Enqueue Operation:
o Allocate memory for a new node and assign the value to data.
o If the queue is empty (both front and rear are nullptr):
 Set both front and rear to the new node and point rear->next to
front.
 o Otherwise:
 Add the new node at the rear and update rear->next to point to
front.
2. Dequeue Operation:
o Check if the queue is empty:
 If front and rear are both nullptr, the queue is empty.
o If there is only one element in the queue (when front equals rear):
 Remove the node by setting both front and rear to nullptr.
o Otherwise:
 Set front to the next node and update rear->next to point to the new
front.
3. Peek Operation:
o If the queue is empty, print a message.
o Otherwise, display the data of the front node.
4. Display Operation:
o If the queue is empty, print a message.
o Otherwise, traverse from front to rear, displaying each element.

Explanation

This program implements a circular queue using a linked list. Each node contains an integer
(data) and a pointer to the next node. The queue follows FIFO (First In, First Out) order,
where elements are inserted at the rear and removed from the front. In a circular queue, the
rear node points to the front node, creating a circular link.

Key Operations:

 enqueue(x): Adds an element x at the rear of the queue. If the queue is empty, the
front and rear are both initialized to the new node.
 dequeue(): Removes the front element from the queue. If there's only one element,
both front and rear are reset to nullptr.
 peek(): Displays the element at the front of the queue without removing it.
 display(): Shows all elements in the queue, starting from the front to the rear.

This approach ensures efficient memory usage, and the circular link allows the queue to
behave cyclically, where the rear connects back to the front.

Output:
Deque (or double-ended queue)
In this article, we will discuss the double-ended queue or deque. We should first see
a brief description of the queue.

What is a queue?
A queue is a data structure in which whatever comes first will go out first, and it
follows the FIFO (First-In-First-Out) policy. Insertion in the queue is done from one
end known as the rear end or the tail, whereas the deletion is done from another
end known as the front end or the head of the queue.

The real-world example of a queue is the ticket queue outside a cinema hall, where
the person who enters first in the queue gets the ticket first, and the person enters
last in the queue gets the ticket at last.

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

AD

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 -

AD

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.

AD

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. }

C++ Code:
#include <iostream>
#define size 5
using namespace std;
int deque[size];
int f = -1, r = -1;

// insert_front function will insert the value from the front

void insert_front(int x) {
if ((f == 0 && r == size - 1) || (f == r + 1)) {
cout << "Overflow";
} else if ((f == -1) && (r == -1)) {
f = r = 0;
deque[f] = x;
} else if (f == 0) {
f = size - 1;
deque[f] = x;
} else {
f--;
deque[f] = x;
}
}

// insert_rear function will insert the value from the rear

void insert_rear(int x) {
if ((f == 0 && r == size - 1) || (f == r + 1)) {
cout << "Overflow";
} else if ((f == -1) && (r == -1)) {
r = 0;
deque[r] = x;
} else if (r == size - 1) {
r = 0;
deque[r] = x;
} else {
r++;
deque[r] = x;
}
}

// display function prints all the values of deque

void display() {
int i = f;
cout << "\nElements in the deque are: ";
if (f == -1 && r == -1) {
cout << "Deque is empty";
return;
}
while (i != r) {
cout << deque[i] << " ";
i = (i + 1) % size;
}
cout << deque[r] << endl;
}

// getfront function retrieves the first value of the deque

void getfront() {
if ((f == -1) && (r == -1)) {
cout << "Deque is empty" << endl;
} else {
cout << "\nThe value of the element at front is: " << deque[f] <<
endl;
}
}
// getrear function retrieves the last value of the deque
void getrear() {
if ((f == -1) && (r == -1)) {
cout << "Deque is empty" << endl;
} else {
cout << "The value of the element at rear is: " << deque[r] <<
endl;
}
}

// delete_front function deletes the element from the front

void delete_front() {
if ((f == -1) && (r == -1)) {
cout << "Deque is empty" << endl;
} else if (f == r) {
cout << "\nThe deleted element is " << deque[f];
f = -1;
r = -1;
} else if (f == size - 1) {
cout << "\nThe deleted element is " << deque[f];
f = 0;
} else {
cout << "\nThe deleted element is " << deque[f];
f++;
}
}

// delete_rear function deletes the element from the rear

void delete_rear() {
if ((f == -1) && (r == -1)) {
cout << "Deque is empty" << endl;
} else if (f == r) {
cout << "\nThe deleted element is " << deque[r];
f = -1;
r = -1;
} else if (r == 0) {
cout << "\nThe deleted element is " << deque[r];
r = size - 1;
} else {
cout << "\nThe deleted element is " << deque[r];
r--;
}
}

int main() {
insert_front(20);
insert_front(10);
insert_rear(30);
insert_rear(50);
insert_rear(80);
display();
getfront();
getrear();
delete_front();
delete_rear();
display();
return 0;
}
Pseudo Code:
START
INITIALIZE deque array of fixed size
SET front (f) = -1, rear (r) = -1

FUNCTION insert_front(x):
IF deque is full:
PRINT "Overflow"
ELSE IF deque is empty:
SET f = r = 0
deque[f] = x
ELSE IF f == 0:
SET f = size - 1
deque[f] = x
ELSE:
DECREMENT f
deque[f] = x

FUNCTION insert_rear(x):
IF deque is full:
PRINT "Overflow"
ELSE IF deque is empty:
SET r = 0
deque[r] = x
ELSE IF r == size - 1:
SET r = 0
deque[r] = x
ELSE:
INCREMENT r
deque[r] = x

FUNCTION display:
SET i = f
PRINT "Elements in deque are: "
LOOP until i != r:
PRINT deque[i]
SET i = (i + 1) % size
PRINT deque[r]

FUNCTION getfront:
IF deque is empty:
PRINT "Deque is empty"
ELSE:
PRINT deque[f]

FUNCTION getrear:
IF deque is empty:
PRINT "Deque is empty"
ELSE:
PRINT deque[r]

FUNCTION delete_front:
IF deque is empty:
PRINT "Deque is empty"
ELSE IF f == r:
PRINT deque[f]
SET f = r = -1
ELSE IF f == size - 1:
PRINT deque[f]
SET f = 0
 ELSE:
PRINT deque[f]
INCREMENT f

FUNCTION delete_rear:
IF deque is empty:
PRINT "Deque is empty"
ELSE IF f == r:
PRINT deque[r]
SET f = r = -1
ELSE IF r == 0:
PRINT deque[r]
SET r = size - 1
ELSE:
PRINT deque[r]
DECREMENT r

END

Algorithm:

1. Initialize the deque with a fixed size.

2. Insert Front:
o Check if the deque is full.
o If deque is empty, insert at the first position.
o If the front is at the beginning, wrap around to the last index.
o Else, decrement the front pointer and insert the value.
3. Insert Rear:
o Check if the deque is full.
o If deque is empty, insert at the first position.
o If the rear is at the last index, wrap around to the first index.
o Else, increment the rear pointer and insert the value.
4. Display the deque elements in circular order.
5. Get Front:
o If the deque is empty, print "Deque is empty."
o Else, return the front value.
6. Get Rear:
o If the deque is empty, print "Deque is empty."
o Else, return the rear value.
7. Delete Front:
o If the deque is empty, print "Deque is empty."
o If there’s only one element, reset the deque.
o If the front is at the end, wrap around to the beginning.
o Else, increment the front pointer.
8. Delete Rear:
o If the deque is empty, print "Deque is empty."
o If there’s only one element, reset the deque.
o If the rear is at the beginning, wrap around to the end.
o Else, decrement the rear pointer.

Explanation:
  A deque is a double-ended queue, which allows insertion and deletion from both
ends.
 This implementation uses a circular array to efficiently manage the deque's wrap-
around behavior.
 Insertions at the front and rear follow different rules depending on the current
positions of the front and rear pointers.
 Deletions adjust the pointers accordingly, ensuring the deque's circular behavior.
 The getfront and getrear functions allow retrieving elements from the deque
without removing them.

Output:

So, that's all about the article. Hope, the article will be helpful and informative to you.

What is a priority queue?

A priority queue is an abstract data type that behaves similarly to the normal queue
except that each element has some priority, i.e., the element with the highest priority
would come first in a priority queue. The priority of the elements in a priority queue
will determine the order in which elements are removed from the priority queue.

The priority queue supports only comparable elements, which means that the
elements are either arranged in an ascending or descending order.

For example, suppose we have some values like 1, 3, 4, 8, 14, 22 inserted in a priority
queue with an ordering imposed on the values is from least to the greatest.
Therefore, the 1 number would be having the highest priority while 22 will be having
the lowest priority.

Characteristics of a Priority queue

A priority queue is an extension of a queue that contains the following
characteristics:

o Every element in a priority queue has some priority associated with it.
 o An element with the higher priority will be deleted before the deletion of the lesser
priority.
o If two elements in a priority queue have the same priority, they will be arranged using
the FIFO principle.

Let's understand the priority queue through an example.

We have a priority queue that contains the following values:

1, 3, 4, 8, 14, 22

All the values are arranged in ascending order. Now, we will observe how the priority
queue will look after performing the following operations:

o poll(): This function will remove the highest priority element from the priority queue.
In the above priority queue, the '1' element has the highest priority, so it will be
removed from the priority queue.
o add(2): This function will insert '2' element in a priority queue. As 2 is the smallest
element among all the numbers so it will obtain the highest priority.
o poll(): It will remove '2' element from the priority queue as it has the highest priority
queue.
o add(5): It will insert 5 element after 4 as 5 is larger than 4 and lesser than 8, so it will
obtain the third highest priority in a priority queue.

AD

Types of Priority Queue

There are two types of priority queue:

o Ascending order priority queue: In ascending order priority queue, a lower priority
number is given as a higher priority in a priority. For example, we take the numbers
from 1 to 5 arranged in an ascending order like 1,2,3,4,5; therefore, the smallest
 number, i.e., 1 is given as the highest priority in a priority queue.

o Descending order priority queue: In descending order priority queue, a higher

priority number is given as a higher priority in a priority. For example, we take the
numbers from 1 to 5 arranged in descending order like 5, 4, 3, 2, 1; therefore, the
largest number, i.e., 5 is given as the highest priority in a priority queue.

Representation of priority queue

Now, we will see how to represent the priority queue through a one-way list.

We will create the priority queue by using the list given below in which INFO list
contains the data elements, PRN list contains the priority numbers of each data
element available in the INFO list, and LINK basically contains the address of the next
node.
Let's create the priority queue step by step.

In the case of priority queue, lower priority number is considered the higher
priority, i.e., lower priority number = higher priority.

Step 1: In the list, lower priority number is 1, whose data value is 333, so it will be
inserted in the list as shown in the below diagram:

Step 2: After inserting 333, priority number 2 is having a higher priority, and data
values associated with this priority are 222 and 111. So, this data will be inserted
based on the FIFO principle; therefore 222 will be added first and then 111.

Step 3: After inserting the elements of priority 2, the next higher priority number is 4
and data elements associated with 4 priority numbers are 444, 555, 777. In this case,
elements would be inserted based on the FIFO principle; therefore, 444 will be added
first, then 555, and then 777.

Step 4: After inserting the elements of priority 4, the next higher priority number is 5,
and the value associated with priority 5 is 666, so it will be inserted at the end of the
queue.

AD
Implementation of Priority Queue
The priority queue can be implemented in four ways that include arrays, linked list,
heap data structure and binary search tree. The heap data structure is the most
efficient way of implementing the priority queue, so we will implement the priority
queue using a heap data structure in this topic. Now, first we understand the reason
why heap is the most efficient way among all the other data structures.

C++ Code for Priority Queue

#include <iostream>
#include <vector>
#include <queue> // for priority_queue
using namespace std;

int main() {
// Creating a max-heap (priority queue) using priority_queue
priority_queue<int> pq;

// Insert elements into the priority queue

pq.push(20);
pq.push(50);
pq.push(10);
pq.push(40);
pq.push(30);

// Display and remove elements from the priority queue

cout << "Elements in the priority queue: ";
while (!pq.empty()) {
cout << pq.top() << " "; // Get the highest priority element (max
element)
pq.pop(); // Remove the top element
}
cout << endl;

return 0;
}
Output

Explanation

 A priority queue is a data structure similar to a regular queue or stack, but where
each element has a "priority" associated with it.
 In this implementation, we used a max-heap priority queue where the largest number
has the highest priority and is served first.
 priority_queue<int> by default implements a max-heap. The largest element is
always on the top.
 Functions used:
o push(): Insert an element into the priority queue.
o top(): Access the element with the highest priority.
o pop(): Remove the element with the highest priority.

In the example, we insert values into the priority queue: 20, 50, 10, 40, and 30. The priority
queue automatically arranges the elements in descending order based on their priority (value
in this case). So when we pop elements, the largest value (50) is popped first, followed by 40,
30, etc.

Algorithm (for Priority Queue using Max-Heap)

1. Create a priority queue initialized to an empty state.

2. Insert elements into the priority queue.
o For each insertion, the element is added at the proper position to maintain heap
order.
3. Access the top element:
o The element with the highest priority (in a max-heap, the maximum element)
is at the top.
4. Remove elements:
o The highest-priority element is removed, and the heap is reorganized to
maintain the priority order.
5. Repeat steps 3 and 4 until the priority queue is empty.

Pseudo Code
PriorityQueue pq = new PriorityQueue()

// Inserting elements into the priority queue

pq.push(20)
pq.push(50)
pq.push(10)
pq.push(40)
pq.push(30)

// Display and remove elements from the priority queue

while pq is not empty:
print pq.top() // Get the highest priority element
pq.pop() // Remove the highest priority element

Explanation of Operations in a Priority Queue

1. Insert Operation (push): When inserting an element into the priority queue, the
element is placed in the correct position to maintain heap property. In a max-heap,
this ensures that the largest element is always on the top.
2. Access Operation (top): This operation retrieves the element with the highest
priority without removing it from the queue.
3. Delete Operation (pop): This operation removes the highest-priority element (in a
max-heap, the largest element). After removal, the heap reorganizes itself to maintain
the priority ordering.
4. Heap Structure: The priority queue is internally implemented using a binary heap,
which is a complete binary tree where each parent node is larger than its children in
the case of a max-heap.

C++ Code for Double Ended Queue (Deque)

A Double Ended Queue (Deque) is a data structure that allows insertion and deletion at both
ends (front and rear). In C++, we can use the deque container from the Standard Template
Library (STL).

#include <iostream>
#include <deque> // for deque container
using namespace std;

int main() {
deque<int> dq;

// Inserting elements at the rear

dq.push_back(10);
dq.push_back(20);
dq.push_back(30);

// Inserting elements at the front

dq.push_front(5);
dq.push_front(1);

// Display the deque elements

cout << "Deque elements: ";
for (int i : dq) {
cout << i << " ";
}
 cout << endl;

// Removing elements from the front and rear

dq.pop_front(); // Removes 1 from the front
dq.pop_back(); // Removes 30 from the rear

// Display the deque elements after popping front and back

cout << "Deque after popping front and rear: ";
for (int i : dq) {
cout << i << " ";
}
cout << endl;

// Accessing the front and rear elements

cout << "Front element: " << dq.front() << endl;
cout << "Rear element: " << dq.back() << endl;

return 0;
}

Output

Explanation

 Deque (Double Ended Queue) is a data structure that allows the addition and
removal of elements from both ends (front and rear).
 We use the C++ STL deque to implement this structure.
 Operations in the deque:
o push_front(): Adds an element to the front of the deque.
o push_back(): Adds an element to the rear of the deque.
o pop_front(): Removes an element from the front.
o pop_back(): Removes an element from the rear.
o front(): Accesses the element at the front.
o back(): Accesses the element at the rear.

In the code:

 Elements are added using push_back() at the rear and push_front() at the front.
 The initial deque has elements 1 5 10 20 30.
 After removing the front (1) and rear (30), the deque becomes 5 10 20.
 We then access and display the front ( 5) and rear (20) elements.
Algorithm (for Deque)

1. Initialize the deque as an empty structure.

2. Insert elements at the rear using push_back() and at the front using
push_front().
3. Display the elements of the deque by iterating from front to rear.
4. Remove elements from the front using pop_front() and from the rear using
pop_back().
5. Access the front element using front() and the rear element using back().
6. Continue operations based on the application, adding and removing from either end
as necessary.

Pseudo Code
Initialize deque as empty

// Insertion
push_front(deque, element) // Insert element at the front
push_back(deque, element) // Insert element at the rear

// Deletion
pop_front(deque) // Remove element from the front
pop_back(deque) // Remove element from the rear

// Access front and rear

front_element = front(deque) // Access the front element
rear_element = back(deque) // Access the rear element

// Display elements
for each element in deque:
print element

Operations in Deque and Explanation

1. Insertion at Front (push_front):

o Adds an element to the front of the deque. The new element is inserted before
the current front element.
2. Insertion at Rear (push_back):
o Adds an element to the rear of the deque. The new element is inserted after the
current rear element.
3. Removal from Front (pop_front):
o Removes the element at the front of the deque.
4. Removal from Rear (pop_back):
o Removes the element at the rear of the deque.
5. Access Front (front):
o Retrieves the element at the front without removing it.
6. Access Rear (back):
o Retrieves the element at the rear without removing it.
Advantages of Deque

 Flexibility: It allows insertions and deletions from both ends, making it more flexible
than a standard queue or stack.
 Efficient Access: It allows efficient access to both front and rear elements, unlike
regular queues where only one end is accessible at a time.

Applications of Deque

 Sliding Window Problems: Deque is commonly used in problems involving sliding

windows, where efficient access to both ends is necessary.
 Palindrome Checking: It can be used to check if a sequence of characters is a
palindrome.
 Job Scheduling: Deque can be used in applications where jobs/tasks need to be added
and removed from both ends, such as task scheduling.