Queue
Queue is a linear data structure in which deletions can only occur at one end, known as the
front, and insertions can only occur at the other end, known as the rear. It is similar to the
real-life queue where the first person entering the queue is the first person who comes out of the
queue. Thus queues are also called FIFO(First In First Out) lists.
Basic Operations of Queue
A queue allows the following basic operations:
Enqueue – Add new element to the end of the queue.
Dequeue – Remove an element from the front of the queue.
Every queue includes two pointers, FRONT and REAR, which indicate the position where
deletion and insertion can be performed. Initially, values of FRONT and REAR is set to -1.
Enqueue Operation
Inserting a new element in the position pointed by REAR is called the enqueue operation. We
must check if the queue is full before insertion. After the enqueue operation the REAR is
incremented by 1 and will point to the newly inserted element.
For inserting the first element in a queue, the value of FRONT has to be set to 0.
Consider a queue of size 5. Suppose we have to insert A, B, C, D and E into the queue. The
following changes will be made to the queue.
Dequeue Operation
Deleting an element in the position pointed by FRONT is called the dequeue operation. We
must check if the queue is empty before deletion. After the dequeue operation, the FRONT is
incremented by 1.
After deleting the last element in a queue, the value of FRONT and REAR has to be set to 0.
Consider the following example where we dequeue elements one by one until the queue
becomes empty.
Representation of Queues
Queue is usually represented in the computer using a linear array or a one-way linked list.
Array Representation of Queue
A queue can be represented in a program by using a linear array of elements and three pointer
variables FRONT, REAR and MAX.
The queue is empty if FRONT = REAR = -1. The queue is full if FRONT =1 and REAR = MAX -
1.
Array Representation of a Queue
The size of the above queue is 5. It has 3 elements A, B and C. The FRONT, REAR and MAX
pointers will have values 0, 2 and 5 respectively
The algorithms for enqueue and dequeue operations are given below.
Algorithm: ENQUEUE(QUEUE, MAX, FRONT, REAR, ITEM)
Step 1: IF REAR = MAX-1
Write OVERFLOW
Goto step 4
[END OF IF]
Step 2: IF FRONT=-1 and REAR=-1
SET FRONT = REAR = 0
ELSE
SET REAR = REAR + 1
[END OF IF]
Step 3: SET QUEUE[REAR] = ITEM
Step 4: EXIT
Print overflow and exit if the queue is full.
For adding first element make FRONT = 0.
Increment REAR by 1.
Insert new element in the position pointed by REAR.
Algorithm DEQUEUE(QUEUE, MAX, FRONT, REAR, ITEM)
Step 1: IF FRONT = -1 OR FRONT > REAR
Write UNDERFLOW
ELSE
SET ITEM = QUEUE[FRONT]
SET FRONT = FRONT + 1
[END OF IF]
Step 2: EXIT
Print underflow and exit if the queue is empty.
Return the value pointed by FRONT.
Increment FRONT by 1.
Set FRONT = REAR = -1 for the last element.
Linked Representation of Queues
The disadvantage of using an array to represent a queue is that the array must be specified to
have a fixed size. If the array size cannot be known ahead of time, then the linked
representation is used.
The HEAD pointer of the linked list is used as the FRONT. Also, use another pointer called
REAR to store the address of the last element of the queue.
The algorithms for enqueue and dequeue operations are given below.
Algorithm: LINK_ENQUEUE
Step 1: Allocate memory for the new node and name it as PTR
Step 2: SET PTR -> DATA = VAL
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]
Step 4: END
Inserting an element in a linked queue
Algorithm: LINK_DEQUEUE
Step 1: IF FRONT = NULL
Write Underflow
Go to Step 5
[END OF IF]
Step 2: SET PTR = FRONT
Step 3: SET FRONT = FRONT -> NEXT
Step 4: FREE PTR
Step 5: END
Disadvantage of Queue
Look at the following queue.
You cannot insert a new value now, because the queue is completely full. Consider the following
case: two consecutive deletions are made.
Even though there is enough space to hold a new element, the overflow condition still occurs
since the condition REAR = MAX – 1 is still valid. This is a major drawback of a linear queue. A
solution to this problem is to make the queue circular.
Types of Queues
A queue data structure can be classified into the following types:
Circular Queue.
Priority Queue.
Dequeue.
Application of Queue
Manage resource sharing such as CPU scheduling, disk scheduling..etc
When data is sent and received between two processes asynchronously.
Hadling of inrepputs in real time.
Call waiting systems in call centers.
