Queue in Data Structure

Table of Contents

Queue in Data Structure

  • It is a linear list in which deletion of data item take place at one end of the list called ‘Front’.
  • The insertion take place only at another end of list called ‘Rear’.
  • The first element inserted into a queue is the first element to be For this reason, queue is also FIFO (First In First Out) list.

Examples:

  • Line at Bus stop.
  • Time-sharing system, in which program with same priority from a queue for execution.

If one element is removed from queue, then

Now, if two more elements are added to queue.

 

QUEUE AS AN ABSTRACT DATA TYPE:

A queue is a linear list in which additions and deletions take place at different ends. The end at which new elements are added is called the rear and that from which old elements are deleted is called the front.

Instances: ordered list of elements; one end is called the front; the other is the rear.

 

Operations:

Create( ): create an empty queue.

Isempty( ): return true if queue is empty.

Isfull( ): return true if queue is full.

First( ): return first element of queue.

Last( ): return last element of queue.

Add(x): add element x to the queue.

Delete(x): delete front element from queue and put it in x;

 

Algorithm to insert an element into queue:

ENQUEUE (QUEUE, N, FRONT, REAR, ITEM)

This procedure inserts an element item into a queue having maximum N elements.

Step 1: [ Check if queue is full ]

If REAR = N, then

Write (‘Overflow! Queue is full’) and return.

[ End of If structure ]

Step 2: [ Find the new value for rear ]

If REAR = 0, then

FRONT := 1

REAR := 1

Else

REAR := REAR + 1

[ End of If structure ]

Step 3: [ Insert new element ]

QUEUE[REAR] := ITEM

Step 4: Return.

 

ALGORITHM TO DELETE AN ELEMENT FROM QUEUE

DEQUEUE (QUEUE, N, FRONT, REAR, ITEM)

This procedure deletes an element item into a queue having maximum N elements.

Step 1: [ Check if queue is empty ]

If FRONT = 0, then

Write (‘Underflow! Queue is empty’) and return.

[ End of If structure ]

Step 2: [ Remove the element ]

ITEM := QUEUE[FRONT]

Step 3: [ Find the new value for rear ]

If FRONT = REAR, then              [ Only one element in queue ]

FRONT := 0

REAR := 0

Else

FRONT := FRONT +1

[ End of If structure ]

Step 4: Return.

You May Like to Browers More