A queue is a linear list of elements in which deletion can take place only at one end, called the FRONT, and insertions can take place only at the other end, called the REAR. These two terms are only used with the queues. Queues are also called First-in First-out (FIFO) lists. There is a lot of application of queue in daily life let see them below.
An example of a queue in daily life is the people waiting in a line at a bank. Man first comes first out form line.
Another example of a queue is a line of those people who wait for a bus at a bus stop. Each new person who comes takes his place at the end of the line when the bus is coming, the person at front of line board first.
An important example of a queue in computer science occurs in a time sharing system, in which the programs with the same priority form a queue while waiting to be executed.
Recommended Book: Data Structures and algorithms
Different types of queue:
There are three major variations in a simple queue. They are
- Circular queue
- Double-ended queue (de-queue)
- Priority queue
The following Figures show the way the arrays in figures a, b, c, and d will be stored in memory using an array QUEUE with N elements.
These figures also indicate the way elements will be deleted from and the way elements will be added to the queue.
Note that whenever an element is deleted from the queue, the value of FRONT is increased by 1; this is accomplished by
FRONT: = FRONT + 1
Similarly whenever an element is added to the queues the value of REAR is increased by 1; this is accomplished by
REAR : = REAR + 1
The linear arrangement of the queue always considers the elements in a forward direction. In the above two algorithms, we had seen that the pointers front and rear are always incremented as and when we delete or insert elements respectively.
Suppose in a queue of 10 elements front points to 4th element and rear points to 8th element as follows.
Later, when we try to insert some elements, then according to the logic when REAR is N then it encounters an overflow situation. But there are some elements that are left blank at the beginning part of the array.
To utilize those leftover spaces more efficiently, a circular fashion is implemented in queue representation. The circular fashion of queue reassigns the rear pointer with 1 if it reaches N and beginning elements are free and the process is continued for deletion also. Such queues are called Circular Queue.
A priority queue is a collection of elements such that each element has been assigned a priority value such that the order in which elements are deleted and processed comes from the following rules
- An element of higher priority is processed before any element of lower priority.
- Two elements with the same priority are processed according to the order in which they were added to the queue.
There are various ways of maintaining a priority queue in memory. One is using a one-way list. The sequential representation is never preferred for a priority queue. We use linked Queue for priority Queue.
A Double Ended Queue is in short called as Deque (pronounced as Deck or dequeue). A deque is a linear queue in which insertion and deletion can take place at either end but not in the middle.
There are two types of Deque.
- Input restricted Deque: A Deque which allows insertion at only at one end of the list but allows deletion at both the ends of the list is called Input restricted Deque.
- Output restricted Deque: A Deque which allows deletion at only at one end of the list but allows insertion at both the ends of the list is called Output restricted Deque.
Conditions of the queue:
Two conditions can exist for a queue that is overflow and underflow.
Overflow: Overflow occurs when the queue is full in spite of that we try to insert an item into a queue.
Underflow: It occurs when a queue is empty, we try to delete an element from a queue.
Algorithm for inserting an element into a simple QUEUE:
QUEUE INSERTION (QUEUE, FRONT, REAR, ITEM, MAXSIZE)
(This algorithm inserts an element ITEM in the array QUEUE where MAXSIZE is the capacity of the queue and FRONT and REAR are the pointers.)
- [Check for overflow] IF REAR >= MAXSIZE – 1 then Printf (“overflow “) and EXIT.
- [ CHECK IF THE FIRST ELEMENT IS BEING INSERTED ] If FRONT = -1 and REAR =-1 Set: FRONT = 0 and REAR =0
- Else Set: REAR = REAR + 1
- [Insert the element] Set: QUEUE [REAR] = ITEM
- [Finish] End.
Algorithm to delete an element from a simple QUEUE:
DELETION IN QUEUE (QUEUE, MAXSIZE, FRONT, REAR, ITEM)
(This algorithm deletes an element from the QUEUE and assigns it to the variable ITEM. MAXSIZE is the capacity of the QUEUE. FRONT and REAR are used as pointers).
- [Check for underflow] If FRONT < 0 then Printf (“Underflow “) and EXIT.
- [TAKE the element out] Set ITEM: = QUEUE [FRONT]
- [Increase the FRONT or set the FRONT AND REAR] If FRONT = REAR then Set: FRONT = REAR = – 1
- Else Set: FRONT = FRONT + 1
- [Finish] End.
Application of queue:
- Implementation of a queue is also an important application of data structure. Nowadays computer handles multiuser, multiprogramming environment and time-sharing environment. In this environment a system(computer) handles several jobs at a time, to handle these jobs the concept of a queue is used.
- To implement printer spooler so that jobs can be printed in the order of their arrival.
- Round robin scheduling technique is implemented using queue
- All types of customer service(like railway reservation) centers are designed using the concept of queues.