In programming, Queue is a linear data structure in which new items are inserted from one end, whereas existing items are removed from other end. The end at which the items are inserted is called Tail or Back or Rear of the queue. The end from where items are removed is called Head or Front of the queue.
The item that is added at first into the queue is removed first. Similarly, the item that is added at the end is removed at the end. For this reason, a queue is referred to as Ftrst In First-Out (FIFO) data structure The insert and remove operations are also known as enqueue and dequeue respectively.
The above image shows a queue with 9 items. The item 1 is the frst item, while 9 is the last item. A new Item can be added after 9. Similarly, the Items can be removed starting at the front of the queue, For example, the first item to be removed will be 1 and to remove the item 9, all items in front of 9, such as 1, 2, 3, 4, 5, 6, 7 and 8 must be removed first.
Applications of Queues in Computer
Queues have many applications in computer systems. Most computers have only a single processor, so the job of only one user can be performed at a time. The jobs of other users are placed in a queue and are performed one after the other.
For example, if you want to print documents on the printer, the operating system (or a special print spooler) queues the documents by placing them in a special area called a print buffer or print queue. The document sent first is printed first and so on. Similarly, network operating system uses queue to process printing request. The documents are sent to the printer in network environment. (which may have single printer). The printer prints the document in the order in which they are received.
In electronic data communication systems, queues are also used to receive and send information packets. The information packets wait in queues in computer network.
Implementation of Queue
A queue can be implemented in computer programming languages using different ways. Normally, linear array and linked list are used to implement queues. The simplest and easiest way to implement a queue is by using a linear array.
Suppose an array QU represents a queue and the variables F and B represent the front and back of the queue respectively. If the array has capacity of storing ‘N’ elements, then whenever a new data item is added into the array, the value of B is increased by 1. If the value of B is greater than or equal to N, then queue is overflowed. Similarly, when a data item is removed from the queue, the value of F is increased by 1. If the value of F and B are equal then queue has only one item. If the value of F is -1, then queue is empty. Following table illustrates these operations;
| Queue Status | Operation |
|---|---|
| Take a queue of capacity of 5 elements. Initially there is only one item such as "X" in the queue, therefore F and B both are at 0 position. | |
| Add another item in the queue such as "Y". The value of B is increased by 1, i.e it becomes 1. | |
| Add another item in the queue such as "Z". The value of B is increased by 1, i.e it becomes 2. | |
| Delete the one item from the queue which is "X". The value of F is increased by 1, i.e it becomes 1. | |
| Delete another item from the front of queue which is "Y". The value of F is increased by 1, i.e it becomes 2. Both the values of F and B are equal. It means that only one item exists in the queue. | |
| Delete another item from the queue which is "X". The value of F is increased by 1, i.e it becomes 3. At this position, value of F is greater than B, so initialize value of F and B to -1. |
C++ Queue Example Programs:
Example program 1: The following source code insert and remove items from the queue.
#include
#include
class queue
{
private:
int B, F;
int QU[10];
public:
// constructor that initializes variables B & F
queue (void) {B = -1; F = -1;}
void insert (int);
void remove (void);
void display (void);
};
void main (void)
{
queue obj;
int n, opt, loop = 1;
while (loop)
{
cout
cout
cout
cout
cout
cin>>opt;
switch (opt)
{
case 1:
cout
cin>>n;
obj .insert (n);
break;
case 2:
obj .remove ();
break;
case 3:
cout
obj .display ();
break;
case 4:
loop = 0; break;
default:
cout
}
}
}
// member function to insert value into queues
void queue :: insert (int x)
{
if (B >= 9)
{
cout
getch();
return;
}
else
{
B = B + 1;
QU [B] = x;
}
if (F == -1)
F = 0;
}
// member function to remove value from queue
{
if (F == -1)
{
cout
getch();
return;
}
cout
getch();
QU[F] = NULL;
F = F + 1;
if (F>B)
F = B = -1;
}
// member function to display values of stack
{
if (F == -1)
{
cout
getch();
return;
}
for (int i = F; i
cout
getch();
}
What is Deques
The term deque stands for double-ended queue. It is a linear data structure in which items can be added or removed at either end (or side). It means that items can be added or removed at both ends of the deque. However, an item cannot be added or deleted in the middle of the deque. A deque-with values is shown in the following image.
Type of Deques
There are two types of deques, these are following:- Input-Restricted Deque: This type of deque allows insertions only at one end but allows deletions at both ends.
- Output-Restricted Deque: This type of deque allows deletions only at one end but allows insertions at both ends.
Implementation of Deque
The deque can be implemented in computer languages in several ways. Usually, It is implemented in similar way as circular queue is implemented. Normally, deque is implemented by using linear array with two pointer variables pointing to its two ends.
Suppose an array DQ represents a deque and the variable "F" and "B" represent the front and back of the deque respectively. The following points must be noted about the deque:
- When an item is added at the front of DQ, then F, is decreased by 1.
- When an item is removed at the front, then value of F is increased by 1
- When an item is added at the back, then B is increased by 1
- When an item is removed from back, then B is decreased by 1.
- If the values of F and B are equal, it indicates that the deque has only one item.
After deleting the last item in the deque, the values of both F and B are set to -1 (or NULL value). This indicates that the deque is empty. An image of deque is shown below having some items stored In it.
The values of F and B for the above deque are 2 and 4 respectively,
If two values 19 and 24 are removed from back of deque, then B decreases by 2. So the value of B becomes 2. The value of F and B are equal. It indicates that dequc has only one item which is 26. Example program 2: This program inserts and removes data items to and from the queue.
// program to insert and delete items in a circular duque
#include
#include
class duque
{
private:
int F, B, DQ[5];
Public:
deque() // constructor to initialize F & B
{ F = -1; B = -1; }
void insert_front (int);
void insert_back (int);
void del_front (void);
void del_back (void);
void print_deque (void);
};
void main (void)
{
duque obj;
int opt, val;
while (opt! = 5)
{
clrscr ();
cout
cout
cout
cout
cout
cout
cin>>opt;
switch (opt)
{
case 1:
cout
cin>>val;
obj .insert_front (val);
obj .print_deque ();
break;
case 2:
cout
cin>>val;
obj .insert_front (val);
obj .print_deque ();
break;
case 3:
obj .del_front ();
obj .del_deque ();
break;
case 4:
obj .del_back ();
}
}
}
// member function to insert item from front side of the deque
void deque :: insert_front (int n)
{
if (F == 0 && B == 4)
{
cout
return;
getch();
}
if (F == -1 && B == -1)
{
B = F = 0;
DQ [F] = n;
}
else if (F > 0)
{
F--;
DQ[F] = n;
}
else
{
cout
getch();
}
}
// member function to insert item from back side of the deque
void deque :: insert_bqck (int n)
{
if (F == 0 && B == 4)
{
cout
return;
getch();
}
if (F == -1 && B == -1)
{
B = F = 0;
DQ [B] = n;
}
else if (B > 0)
{
B!++;
DQ[B] = n;
}
else
{
cout
getch();
}
}
// member function to delete item from front side of the deque
void deque :: del_front (int n)
{
if (F == -1 && B == -1)
{
cout
return;
getch();
}
else
DQ[F] = NULL;
if (F == B) F = B = -1;
else if (F == 4) F == -1;
else
F++;
}
//member function to delete item from back side of the deque
void deque :: del_back (int n)
{
if (F == -1 && B == -1)
{
cout
return;
getch();
}
else
DQ[B] = NULL;
if (B == F) F = B = -1;
else if (F == 4) F == -1;
else
B--;
}
// member function to print data from deque
void deque :: print_deque ()
{
cout
if (F == -1)
{
cout
return;
getch();
}
for (int i = F; i
cout
getch();
}
