Queue

Queue is a data structure which works on FIFO( Fisrt In First Out)rule i.e elements are inserted and deleted in FIFO fashion.


Let us assume the queue scenario as students standing in a line.New additions to a line made to the back of the queue, while removal (or serving) happens in the front. In the queue only two operations are allowed enqueue and dequeue. Enqueue means to insert an item into the back of the queue, dequeue means removing the front item.

The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.

The basic operations that can be performed on queue are
1. Insert (or add) an element to the queue (push)--> Enqueue

2. Delete (or remove) an element from a queue (pop)--> Dequeue

Implementation Of Queue :

Queue in C or C++  can be implemented using an Array, Stack or Linked List. The easiest way of implementing a queue is by using an Array. Initially the head(FRONT) and the tail(REAR) of the queue points at the first index of the array (starting the index of array from 0). As we add elements to the queue, the tail keeps on moving ahead, always pointing to the position where the next element will be inserted, while the head remains at the first index.

When we remove an element from Queue, we can follow two possible approaches (mentioned [A] and [B] in above diagram). In [A] approach, we remove the element at head position, and then one by one shift all the other elements in forward position. In approach [B] we remove the element from headposition and then move head to the next position.

In approach [A] there is an overhead of shifting the elements one position forward every time we remove the first element. In approach [B] there is no such overhead, but whenever we move head one position ahead, after removal of first element, the size on Queue is reduced by one space each time.

Let us discuss underflow and overflow conditions when a queue is implemented using arrays.

If we try to pop (or delete or remove) an element from queue when it is empty, underflow occurs. It is not possible to delete (or take out) any element when there is no element in the queue.

Suppose maximum size of the queue (when it is implemented using arrays) is 50. If we try to push (or insert or add) an element to queue, overflow occurs. When queue is full it is naturally not possible to insert any more elements.

ALGORITHM FOR QUEUE OPERATIONS:

Let Q be the array of some specified size say SIZE
INSERTING AN ELEMENT INTO THE QUEUE

1. Initialize front=0 rear = –1
2. Input the value to be inserted and assign to variable “data”
3. If (rear >= SIZE)
(a) Display “Queue overflow”
(b) Exit
4. Else
(a) Rear = rear +1
5. Q[rear] = data
6. Exit

DELETING AN ELEMENT FROM QUEUE
1. If (rear< front)
(a) Front = 0, rear = –1
(b) Display “The queue is empty”
(c) Exit
68 PRINCIPLES OF DATA STRUCTURES USING C AND C++
2. Else
(a) Data = Q[front]
3. Front = front +1
4. Exit

Types Of Queue:

There are three major variations in a simple queue. They are

1. Circular Queue:Circular Queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle.

2. Double ended queue (de-queue):Double Ended Queue is also a Queue data structure in which the insertion and deletion operations are performed at both the ends (front and rear). That means, we can insert at both front and rear positions and can delete from both front and rear positions.

3. Priority Queue:A priority queue is a collection in which items can be added at any time, but the only item that can be removed is the one with the highest priority.

Priority queue is generally implemented using linked list

APPLICATIONS OF QUEUE:

1. Round robin techniques for processor scheduling is implemented using queue.

2. Printer server routines (in drivers) are designed using queues.

3. All types of customer service software (like Railway/Air ticket reservation) are designed using queue to give proper service to the customers.

Analysis of Queue

Enqueue : O(1)

Dequeue : O(1)

Size : O(1)