C For Swimmers : Mastering C step-by-step

About Queues

Definition : 

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
• Prioirity 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).

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.

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

Click Here: Linear Queue source code written in C.