Queue

A queue is an ordered list in which insertions are done at one end (rear) and deletions are done at other end (front). The first element to be inserted is the first one to be deleted.

Hence, it is called First in First out (FIFO) or Last in Last out (LILO) list. Similar to Stacks, special names are given to the two changes that can be made to a queue. When an element is inserted in a queue, the concept is called EnQueue, and when an element is removed from the queue, the concept is called DeQueue.

This behavior is very useful in cases where there is a need to maintain the order of arrival.

Queue ADT

Main Queue Operations 

• EnQueue( int data): Inserts an element at the end of the queue 
• int DeQueue(): Removes and returns the element at the front of the queue

Auxiliary Queue Operations

• int Front(): Returns the element at the front without removing it 
• int QueueSize(): Returns the number of elements stored in the queue 
• int IsEmptyQueueQ: Indicates whether no elements are stored in the queue or not

Direct Applications 

• Operating systems schedule jobs
• priority) in the order of arrival (e.g., a print queue). 
• Simulation of real-world queues such as lines at a ticket counter or any other first-come first-served scenario requires a queue. 
• Multiprogramming. 
• Asynchronous data transfer (file IO, pipes, sockets). 
• Waiting times of customers at call center. 
• Determining number of cashiers to have at a supermarket.

Simple Circular Array Implementation

Note: Initially, both front and rear points to -1 which indicates that the queue is empty.

(for n EnQueue operations) 

Space Complexity : O( n) 

Time Complexity  :  O( 1)

Limitations: The maximum size of the queue must be defined as prior and cannot be changed. Trying to EnQueue a new element into a full queue causes an implementation-specific exception.

Linked List Implementation

Non Template ADT - Program

Template ADT - Program

Problems

• Problem1 : Give an algorithm for reversing a queue Q. To access the queue, we are only allowed to use the methods of queue ADT. - See Program - Time Complexity: O( n).
• Problem2 : How can you implement a queue using two stacks? - See Program - Time Complexity: O(1).
• Problem3 : A queue is set up in a circular array A[ O.. n - 1] with front and rear defined as usual. Assume that n – 1 locations in the array are available for storing the elements (with the other element being used to detect full/ empty condition). Give a formula for the number of elements in the queue in terms of rear, front, and n. See Explanation
• Problem4 : Double ended queues