About Queues

Lists permit deletions to be performed at one end of a list and insertions at the other end. The information in such a list is processed in the same order as it was received, i.e. on a first-in, first-out (FIFO) or first-come first-serve (FCFS) basis. This type of list is referred to as a Queue.

QUEUE STRUCTURE

D = { d , F , A }

Where,

d : Array or a node (structure)
d = { a , FRONT, REAR }
Here, a : Simple array or structure

FRONT : Pointer to the front element of a queue

REAR : Pointer to the rear element of a queue

F : QINSERT, QDELETE, Q DISPLAY, QMODIFY

A : QFULL, QEMPTY

Types of Queues

Linear Queue
Circular Queue
Priority Queue

The insertion operation is referred to as QINSERT and the deletion operation as QDELETE. We can insert an item at the rear end using QINSERT and remove an item at the front end using QDELETE as shown in the fig(a).

Picture

A pointer FRONT and REAR

FRONT and REAR, pointers to the front and rear elements of queue respectively. Each time a new element is inserted in the queue, the REAR pointer is incremented by 1. The FRONT pointer is incremented by 1 each time a deletion is made from the queue. FRONT and REAR pointers should be reset to -1 once they are found equal.

ALGORITHM : LINEAR QUEUE

Procedure QINSERT(Q,F,MAX,X) : Given F and R, pointers to the front and rear elements of a queue. A QUEUE Q consisting of MAX elements and an element X. this procedure inserts X at the rear end of the queue prior to the first invocation of the procedure, F and R have been set to -1.
Non-linear Data Structure : Trees, Graphs, etc.

ALGORITHM : LINEAR QUEUE

Procedure QINSERT (Q,F,MAX,X) : Given F and R, pointers to the front and rear elements of a queue. A QUEUE Q consisting of MAX elements and an element X. this procedure inserts X at the rear end of the queue prior to the first invocation of the procedure, F and R have been set to -1.

STEP 1: [Is front pointer properly set]
if (F==R)
then F <-- R <-- -1

STEP 2: [Check for overflow condition]
             if (R>=(MAX-1))
             then write ('Error : Overflow')
             Return

STEP 3: [Increment rear pointer]
R <-- R+1

STEP 4: [Insert element]
Q[R] <-- X
Return

Procedure QDELETE(Q,F,R) : Given F and R,the pointers to the front and rear elements of a queue respectively and the queue Q to which they correspond. This procedure delets and returns the element at the front end of the queue .Here X is a temporary variable.

STEP 1: [Check for underflow condition]
             if (F>=R)
             then write('Error : Underflow']
             Return

STEP 2: [Increment the front pointer]
F <-- F+1

STEP 3: [Delete element]
Y <-- Q[F]
Return Y

Linear Queue source code written in C.

Back

Next