Another way to understand Stack & Queue
A queue is a useful data structure in programming. It is similar
to the ticket queue outside a cinema hall, where the first person entering the
queue is the first person who gets the ticket.
Queue follows the First In First Out (FIFO) rule - the item that goes in first is the item that comes out first.
In the above image, since 1 was kept in the queue before 2, it is
the first to be removed from the queue as well. It follows
the FIFO rule.
In programming terms, putting items in the queue is
called enqueue, and removing items from the queue is called dequeue.
We can implement the queue in any programming language like C,
C++, Java, Python or C#, but the specification is pretty much the same.
Basic Operations of Queue
A queue is an object (an abstract data structure - ADT) that
allows the following operations:
Enqueue: Add an element to the end of the queue
Dequeue: Remove an element from the front of the queue
IsEmpty: Check if the queue is empty
IsFull: Check if the queue is full
Peek: Get the value of the front of the queue without removing it
Working of Queue
Queue operations work as follows:
two pointers FRONT and REAR
FRONT track the first element of the queue
REAR track the last element of the queue
initially, set value of FRONT and REAR to -1
Enqueue Operation
check if the queue is full
for the first element, set the value of FRONT to 0
increase the REAR index by 1
add the new element in the position pointed to by REAR
Dequeue Operation
check if the queue is empty
return the value pointed by FRONT
increase the FRONT index by 1
for the last element, reset the values
of FRONT and REAR to -1
Enqueue and Dequeue Operations
Applications of Queue
CPU scheduling, Disk Scheduling
When data is transferred asynchronously between two processes.The
queue is used for synchronization. For example: IO Buffers, pipes, file IO, etc
Handling of interrupts in real-time systems.
Call Center phone systems use Queues to hold people calling them
in order.
A queue is a useful data structure in programming. It is
similar to the ticket queue outside a cinema hall, where the first person
entering the queue is the first person who gets the ticket.
There are four different types of queues:
1. Simple Queue
2. Circular Queue
3. Priority Queue
4.
Double
Ended Queue
1. Simple Queue
In a simple queue, insertion takes place at the rear and removal
occurs at the front. It strictly follows the FIFO (First in First out) rule.
To learn more, visit Queue Data Structure.
2. Circular Queue
In a circular queue, the last element points to the first element
making a circular link.
Circular Queue Representation
The main advantage of a circular queue over a simple queue is
better memory utilization. If the last position is full and the first position
is empty, we can insert an element in the first position. This action is not
possible in a simple queue.
To learn more, visit Circular Queue Data
Structure.
3. Priority Queue
A priority queue is a special type of queue in which each element is associated with a priority and is served according to its priority. If elements with the same priority occur, they are served according to their order in the queue.
Priority Queue Representation
Insertion occurs based on the arrival of the values and removal
occurs based on priority.
4.Deque (Double Ended Queue)
In a double ended queue, insertion and removal of elements can be
performed from either from the front or rear. Thus, it does not follow the FIFO
(First In First Out) rule.
Circular queue avoids the wastage of space in a regular queue
implementation using arrays.
As you can see in the above image, after a bit of enqueuing and
dequeuing, the size of the queue has been reduced.
The indexes 0 and 1 can only be used after the queue is reset when
all the elements have been dequeued.
How Circular Queue Works
Circular Queue works by the process of circular increment i.e.
when we try to increment the pointer and we reach the end of the queue, we
start from the beginning of the queue.
Here, the circular increment is performed by modulo division with
the queue size. That is,
if REAR + 1 == 5 (overflow!), REAR = (REAR + 1)%5 = 0 (start of
queue)
Circular Queue Operations
The circular queue work as follows:
two pointers FRONT and REAR
FRONT track the first element of the queue
REAR track the last elements of the queue
initially, set value of FRONT and REAR to -1
1. Enqueue Operation
check if the queue is full
for the first element, set value of FRONT to 0
circularly increase the REAR index by 1 (i.e. if the
rear reaches the end, next it would be at the start of the queue)
add the new element in the position pointed to by REAR
2. Dequeue Operation
check if the queue is empty
return the value pointed by FRONT
circularly increase the FRONT index by 1
for the last element, reset the values
of FRONT and REAR to -1
Implementation of Queue using Array in C:
#include<stdio.h>
#define n 5
int main()
{
int
queue[n],ch=1,front=0,rear=0,i,j=1,x=n;
printf("Queue using
Array");
printf("\n1.Insertion \n2.Deletion \n3.Display \n4.Exit");
while(ch)
{
printf("\nEnter
the Choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:
if(rear==x)
printf("\n Queue is Full");
else
{
printf("\n Enter no %d:",j++);
scanf("%d",&queue[rear++]);
}
break;
case 2:
if(front==rear)
{
printf("\n Queue is empty");
}
else
{
printf("\n Deleted Element is %d",queue[front++]);
x++;
}
break;
case 3:
printf("\nQueue Elements are:\n ");
if(front==rear)
printf("\n Queue is Empty");
else
{
for(i=front;
i<rear; i++)
{
printf("%d",queue[i]);
printf("\n");
}
break;
case 4:
exit(0);
default:
printf("Wrong Choice: please see the options");
}
}
}
return 0;
}
OUTPUT:
Queue using Array
1.Insertion
2.Deletion
3.Display
4.Exit
Enter the Choice:1
Enter no 1:10
Enter the Choice:1
Enter no 2:54
Enter the Choice:1
Enter no 3:98
Enter the Choice:1
Enter no 4:234
Enter the Choice:3
Queue Elements are:
10
54
98
234
Enter the Choice:2
Deleted Element is 10
Enter the Choice:3
Queue Elements are:
54
98
234
Enter the Choice:4
C program to perform insert & delete operations on queue using
pointer.
Solution:
#include<stdio.h>
#include<stdlib.h>
#define max 10
int insertq ( int queue[max], int *rear , int *data)
{
if ( *rear == max -1 )
return(-1);
else
{
*rear =
*rear + 1;
queue[*rear]
= *data;
return(1);
}
}
int delq( int queue[max], int *front, int *rear , int *data)
{
if ( *front == *rear)
return(-1);
else
{
(*front)++;
*data =
queue[*front];
return(1);
}
}
int main()
{
int queue[max],data;
int front,rear,reply,option;
//... init queue
front = rear = -1;
printf("\tMenu");
printf("\n----------------------------");
printf("\n 1. Insert element in
queue");
printf("\n 2. Delete element from
queue");
printf("\n 3. Exit");
printf("\n----------------------------");
while(1)
{
printf("\nChoose
operation : ");
scanf("%d",&option);
switch(option)
{
case
1 ://insert
printf("\nEnter
Number : ");
scanf("%d",&data);
reply
= insertq(queue,&rear,&data);
if
( reply == - 1)
printf("Queue
is full");
else
printf("%d
is inserted in queue.\n",data);
break;
case
2 : //dele
reply
= delq(queue,&front,&rear,&data);
if
( reply == -1 )
printf("Queue
is empty ");
else
printf("\nDeleted
number is : %d\n", data);
break;
case
3 : exit(0);
}
}
}==========================
No comments:
Post a Comment