QUEUE ABSTRACT DATA STRUCTURE

A queue is an abstract data structure that contains a collection of

elements.

Queue implements the FIFO mechanism i.e. the element that is

inserted first is also deleted first.

In other words, the least recently added element is removed first in a

queue.
 QUEUE ABSTRACT DATA STRUCTURE

Basic Operations

The queue data structure includes the following operations:

Insert: Adds an item to the queue. Addition of an item to the queue is

always done at the rear of the queue.

Delete: Removes an item from the queue. An item is removed or de-

queued always from the front of the queue.

isEmpty: Checks if the queue is empty.

isFull: Checks if the queue is full.

peek: Gets an element at the front of the queue without removing it.
 QUEUE ABSTRACT DATA STRUCTURE
Insertion

In this process, the following steps are performed:

1. Check if the queue is full.
2. If full, produce overflow error and exit.
3. Else, increment ‘rear’.
4. Add an element to the location pointed by ‘rear’.
5. Return success.

Deletion

Deletion operation consists of the following steps:

1. Check if the queue is empty.
2. If empty, display an underflow error and exit.
3. Else, the access element is pointed out by ‘front’.
4. Increment the ‘front’ to point to the next accessible data.
5. Return success.
 QUEUE ABSTRACT DATA STRUCTURE

This is an empty queue and thus we have rear and empty set to -1.

Next, we add 1 to the queue and as a result, the rear pointer moves ahead by
one location.

In the next figure, we add element 2 to the queue by moving the rear pointer
ahead by another increment.
In the following figure, we add element 3 and move the rear pointer by 1.

At this point, the rear pointer has value 2 while the front pointer is at the
0th location.

Next, we delete the element pointed by the front pointer. As the front pointer
is at 0, the element that is deleted is 1.

Thus the first element entered in the queue i.e. 1 happens to be the first
element removed from the queue.
 Program to implements the queue using an array is given as follows

#include <iostream>
using namespace std;
int Q[100], n = 100, front = - 1, rear = - 1;
void Insert() {
int val;
if (rear == n - 1)
cout<<"Q Overflow"<<endl;
else {
if (front == - 1)
front = 0;
cout<<"Insert the element in Q : "<<endl;
cin>>val;
rear++;
Q[rear] = val;
}
}
 Program Continue…..
void Delete()
{
if (front == - 1 || front > rear)
{
cout<<"Q Underflow ";
}
else
{
cout<<"Element deleted from Q is : "<< Q[front] <<endl;
front++;
}
}
void Display()
{
if (front == - 1)
cout<<"Q is empty"<<endl;
else
{
cout<<"Q elements are : ";
for (int i = front; i <= rear; i++)
cout<<Q[i]<<" ";
cout<<endl;
}
}
 Program Continue…..
int main() {
int ch;
cout<<"1) Insert "<<endl;
cout<<"2) Delete "<<endl;
cout<<"3) Display "<<endl;
cout<<"4) Exit "<<endl;
do
{
cout<<"Enter your choice : "<<endl;
cin>>ch;
switch (ch)
{
case 1: Insert();
break;
case 2: Delete();
break;
case 3: Display();
break;
case 4: cout<<"Exit"<<endl;
break;
default: cout<<"Invalid choice"<<endl;
}
} while(ch!=4);

return 0;
}
 Stack Vs. Queue
Stacks and queues are secondary data structures which can be used to store
data. They can be programmed using the primary data structures like arrays
and linked lists.
Differences between these two data structures.

Stacks Queues
Uses LIFO (Last in, First out) Uses FIFO (First in, First out)
approach. approach.
Items are added or deleted from only Items are added from “Rear” end of
one end called “Top” of the stack. the queue and are removed from the
“front” of the queue.
The basic operations for the stack are The basic operations for a queue are
“push” and “Pop”. “enqueue” and “dequeue”.
We can do all operations on the stack In queues, we need to maintain two
by maintaining only one pointer to pointers, one to access the front of
access the top of the stack. the queue and the second one to
access the rear of the queue.

The stack is mostly used to solve Queues are used to solve problems
recursive problems. related to ordered processing.
 CIRCULAR QUEUE
A circular queue is a linear data structure that is used to store data
items. It performs operations by following the FIFO (First In, First Out)
approach and the last position in the queue is connected back to the first
position to form a circle. A circular queue is an extension of the basic queue
that we have discussed earlier. It is also known as “Ring buffer”.

Diagram shows a
circular queue

The above image shows a circular data structure of size 10. The
first six elements are already in the queue and we see that the first position
and last position are joined. Due to this arrangement, space doesn’t go
wasted as it happens in a linear queue.
 CIRCULAR QUEUE
Main Difference is:

In a linear queue after the queue is full, we delete the elements

from another end, and the status of the queue is still shown as full and we
cannot insert more elements.

In the circular queue, when the queue is full, and when we remove
elements from the front since last and first positions are connected, we can
insert the elements at the rear which was vacated by deleting the element.

Basic Operations
Some of the basic operations of the circular queue are as follows:
Front: Returns the front position in the circular queue.
Rear: Returns the rear position in the circular queue.
Insert: Enqueue (value) is used to insert an element in the circular
queue. The element is always inserted at the rear end of the
queue.
 CIRCULAR QUEUE
Insert:
1) Check if the circular queue is full:
test ((rear == SIZE-1 && front == 0) || (rear == front-1)),
where ‘SIZE’ is the size of the circular queue.
2) If the circular queue is full then it displays a message as
“Queue is full”.
If queue is not full then,
check if (rear == SIZE – 1 && front != 0).
If it is true then set rear=0 and insert element.

Delete:
1) Check if the circular queue is Empty: check if (front==-1).
2) If it is empty then display the message “Queue is empty”.
If queue is not empty then perform step 3.
3) Check if (front==rear). If it is true then set
front=rear= -1
else
check if (front==size-1),
if it is true then set front=0 and return the element.
A detailed illustration of adding/removing elements in the circular
queue.
Consider the following circular queue of 5 elements as shown below:

Next, we insert item 1 in the queue.

Next, we insert an item with value 3.

When we insert the elements to make a queue full, the representation

will be as shown below.

Now we delete the two elements i.e. item 1 and item 3 from the
queue as shown below
Next, we insert or enqueue element 11 in the circular queue as
represented below.

Again let us insert element 13 in the circular queue. The queue will
look as shown below.

We see that in the circular queue we move or insert elements

in a circle. Hence we can consume the entire space of the queue till
it becomes full.
 DEQUEUE OR DOUBLE ENDED QUEUE
Dequeue or Double Ended Queue is a generalized version of
Queue data structure that allows insert and delete at both ends.

Some basic operations of dequeue are:

insert_at_beg(): inserts an item at the front of Dequeue.

insert_at_end(): inserts an item at the rear of Dequeue.

delete_fr_beg(): Deletes an item from front of Dequeue.

delete_fr_rear(): Deletes an item from rear of Dequeue.

The difference between Queue and Deque is that it does not follow
the FIFO (First In, First Out) approach. The second feature of Deque
is that we can insert and remove elements from either front or rear
ends.
 DEQUEUE OR DOUBLE ENDED QUEUE
Basic Deque Operations

The following are the basic operations that can be performed on deque:

insertFront: Insert or add an item at the front of the deque.

insertLast: Insert or add an item at the rear of the deque.

deleteFront: Delete or remove the item from the front of the queue.

deleteLast: Delete or remove the item from the rear of the queue.

getFront: Retrieves the front item in the deque.

getLast: Retrieves the last item in the queue.

isEmpty: Checks if the deque is empty.

isFull: Checks if the deque is full.

 DEQUEUE OR DOUBLE ENDED QUEUE
Algorithm
Begin
Declare a class dequeue to declare front f and rear r and following functions:

function insert_at_beg(int) to insert item at front:

If queue is not completely filled up, insert element at the front and update front and rear
Otherwise print overflow.

function insert_at_end(int) to insert item at rear:

If queue is not completely filled up, insert element at the rear and update front and rear
Otherwise print overflow.

function delete_fr_beg() to delete item from front:

If queue is empty, print underflow otherwise delete the front element and update front.

function delete_fr_end() to delete item from end:

If queue is empty, print underflow otherwise delete the rear element and update rear.
End
 DEQUEUE OR DOUBLE ENDED QUEUE
Double Ended Queue Classification

Deque can be classified as follows:

Input-restricted Dequeue: In input-restricted, deletion can be done

from both the ends but insertion can be done only at the rear end of the
queue.

Output-restricted Dequeue: In the output-restricted queue, insertion

can be done from both the ends but deletion is done only at one end i.e. the
front end of the queue.
 DEQUEUE OR DOUBLE ENDED QUEUE
insert_at_end(int i) {
if(r>=SIZE-1)
{
cout<<"\n insertion is not possible, overflow!!!!";
}
else
{
if(f==-1)
{
f++;
r++;
}
else
{
r=r+1;
}
a[r]=i;
cout<<"\nInserted item is"<<a[r];
}
}
 Tower of Hanoi

Tower of Hanoi is a mathematical puzzle where we have three rods

and n disks and invented by the French mathematician Edouard
Lucas in 1883.The objective of the puzzle is to move the entire stack
to another rod, obeying the following simple rules:

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

2) Each move consists of taking the upper disk from one of the
stacks and placing it on top of another stack i.e. a disk can
only be moved if it is the uppermost disk on a stack.

3) No disk may be placed on top of a smaller disk.

illustration for 3 disks :
If n=1 then move the disk from source to destination

If no. of disks greater than 1 then Move n-1 disks from source
to auxiliary with the help of destination.

Move the last disk from source to destination.

Move n-1 disks from auxiliary to destination with the help of

source.
#include<iostream>
using namespace std;

//tower of HANOI function implementation

void TOH(int n,char Sour, char Aux, char Des) {
if(n==1) {
cout<<"Move Disk "<<n<<" from "<<Sour<<" to "<<Des<<endl;
return;
}
TOH(n-1,Sour,Aux, Des);
cout<<"Move Disk "<<n<<" from "<<Sour<<" to "<<Des<<endl;
TOH(n-1,Aux, Des, Sour);
}

//main program
int main() {
int n;
cout<<"Enter no. of disks:";
cin>>n;

//calling the TOH

TOH(n,'A','B','C');
return 0;
}
C++ recursive function to solve tower of hanoi problem