Queue

A 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.

enqueue-operation-queue-inserting-elements
Enqueue Operation on a 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.

dequeue example 1
Dequeue Operation on a Queue

Representation of Queues

Stack 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 queue
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.

linked list representation of queue
Linked Representation of a Queue

The algorithms for enqueue and dequeue operations are given below.

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
queuue inserting an element in the end of a linked list 1
Inserting an element in a linked queue
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
queue deleting first node of a linked list 1 1

Disadvantage of Queue

Look at the following queue.

a full queue

You cannot insert a new value now, because the queue is completely full. Consider the following case: two consecutive deletions are made.

queue after dequeue

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:

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.
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments