Chapter: Programming and Data Structures - Linear Data Structures - Stacks, Queues

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Queue ADT - Linear Data Structures

“A queue is an ordered list in which all inse at another end called FRONT”. squeue are some times referred to as First In First Out (FIFO) lists.

QUEUE ADT

 

“A queue is an ordered list in which all inse at another end called FRONT”. squeue are some times referred to as First In First Out (FIFO) lists.


Example

1.     The people waiting in line at a bank cash counter form a queue. 

 

2.     In computer, the jobs waiting in line to use the processor for execution. This queue is 

 

called Job Queue.

 

Operations Of Queue

There are two basic queue operations. They are,

 

Enqueue –Inserts an item / element at the rear end of the queue. An error occurs if the queue is full.

 

Dequeue –Removes an item / element from the front end of the queue, and returns it to the user. An error occurs if the queue is empty.


1. Addition into a queue

procedure addq (item : items); 

{add item to the queue q} 

begin

 

if rear=n then queuefull 

else begin

 

rear :=rear+1; q[rear]:=item;

 

end; 

end;

{of addq}

 

2.  Deletion in a queue

procedure deleteq (var item : items); 

{delete from the front of q and put into item} 

begin

 

if front = rear then queueempty 

else begin

 

front := front+1 

item := q[front];

 

end; 

end


Uses of Queues ( Application of queue )

 

Queues remember things in first-in-first-out (FIFO) order. Good for fair (first come first served) ordering of actions.

 

Examples of use: (Application of stack )

 

1•      scheduling

 

processing of GUI events printing request

 

2•      simulation orders the events

 

models real life queues (e.g. supermarkets checkout, phone calls on hold)

 


CIRCULAR QUEUE IMPLEMENTATION:

 

Location of queue are viewed in a circular form. The first location is viewed after the last one. Overflow occurs when all the locations are filled.


Algorithm Circular Queue Insert

Void  CQInsert ( int queue[ ], front, rear, item)

 

{

if ( front = = 0 )

 

front = front +1;

if ( ( ( rear = maxsize ) && ( front = = 1 ) )  || ( ( rear ! = 0 ) && ( front = rear +1)))

 

{

printf(               “     queue   overflow   “);

 

if( rear = = maxsize ) rear = 1;

else

 

rear = rear + 1; q [ rear ] = item;

 

}

}

 

Algorithm Circular Queue Delete int CQDelete ( queue [ ], front, rear )

{

 

if ( front = = 0 )

printf             (   “   queue   underflow   “);

 

else

{

 

item = queue [ front ]; if(front = = rear )

 

{

front = 0; rear = 0;

 

}

else if ( front = = maxsize )

 

{

front = 1;

}

 

else

front = front + 1;

 

}

return item;

 

}

 

 

DOUBLE ENDED QUEUE IMPLEMENTATION

 

deque (short for double-ended queue) is an abstract data structure for which elements can be added to or removed from the front or back(both end). This differs from a normal queue, where elements can only be added to one end and removed from the other. Both queues and stacks can be considered specializations of deques, and can be implemented using dequeue.


Two types of Dqueue are

 

1.   Input Restricted Dqueue 

2.   Ouput Restricted Dqueue. 

 

1.   Input Restricted Dqueue 

 

Where the input (insertion) is restricted to the rear end and the deletions has the options either end

 

2. Ouput Restricted Dqueue.

Where the output (deletion) is restricted to the front end and the insertions has the option either end.

 

Example: Timesharing system using the prototype of priority queue –programs of high priority are processed first and programs with the same priority form a standard queue.

 

 

 

 

Priority Queue

 

A priority queue is a collection of elements such that each element has been assigned a priority and such that the order in which elements are deleted and processed comes from the following rules:

 

1.       An element of higher priority is processed before any element of lower priority. 

 

2.     Two elements with the same priority are processed according to the order in which they were added to the queue. 

 

 

Two types of queue are

 

1.     Ascending Priority Queue 

2.     Descending Priority Queue 

 

 

1.     Ascending Priority Queue 

 

 

Collection of items into which item can be inserted arbitrarily & from which only the Smallest item can be removed.

 

 

 

2.  Descending Priority Queue

 

Collection of items into which item can be inserted arbitrarily & from which only the Largest item can be removed.

 


APPLICATIONS OF QUEUE

Batch processing in an operating system To implement Priority Queues.

 

Priority Queues can be used to sort the elements using Heap Sort. Simulation and Mathematics user Queueing theory.

 

Computer networks where the server takes the jobs of the client as per thequeue strategy.


Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail


Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.