Short Notes: Queue

 Page 1


QUEUE
> A queue is also a linear data structure like stack. But unlike stack, here insertion is done at 
one end and deletion at the other end.
> Because of this property, it is also called First-In-First-Out (FIFO) list.
> The insertion process is called ENQUEUE and deletion process is called DEQUEUE.
> The end where element is inserted is called the TAIL of the queue, whereas the other end 
is called HEAD. So initially head=tail.
> Queue can also be represented using an array or a linked list.
> If we DEQUEUE an empty queue, it is called queue underflow. Similarly queue overflow 
is when we ENQUEUE a full queue.
> In array representation, when head=tail+1, then queue is full.
Circular queue
> A circular queue is one in which after reaching the last position, next element is added in 
the first position (provided it is free).
> In general queue, on reaching the end of the queue, no more elements can be added even 
though elements in the beginning are empty (as a result of many dequeue process). 
Circular queue overcomes this limitation of the queue.
> This also can be represented using an array or a linked list.
Page 2


QUEUE
> A queue is also a linear data structure like stack. But unlike stack, here insertion is done at 
one end and deletion at the other end.
> Because of this property, it is also called First-In-First-Out (FIFO) list.
> The insertion process is called ENQUEUE and deletion process is called DEQUEUE.
> The end where element is inserted is called the TAIL of the queue, whereas the other end 
is called HEAD. So initially head=tail.
> Queue can also be represented using an array or a linked list.
> If we DEQUEUE an empty queue, it is called queue underflow. Similarly queue overflow 
is when we ENQUEUE a full queue.
> In array representation, when head=tail+1, then queue is full.
Circular queue
> A circular queue is one in which after reaching the last position, next element is added in 
the first position (provided it is free).
> In general queue, on reaching the end of the queue, no more elements can be added even 
though elements in the beginning are empty (as a result of many dequeue process). 
Circular queue overcomes this limitation of the queue.
> This also can be represented using an array or a linked list.
> In array representation, the list is empty when front=rear.
> Also in array representation, the list is full when front=0 and rear=n-1 where n is the size 
of the array; or when rear=front-1.
De-queue
> De-queue is a double ended queue. It supports insertion and deletion at both end of the list 
but not anywhere in between.
> It is basically a generalization of stack and queue.