QUEUE
Module -02
Part-01
Queue as ADT(abstract data type.)
• These operations are as follows.
• Queue create(Q_size)→create an empty queue whose max size is Q_size
• Queue enqueue(queue,item) →if(isfull(queue)) return Qfull
else insert item at rear end
• dequeue() →if(isempty(queue)) return true
else remove item from front end
• Boolean Isempty(queue) → if (queue= =create(Q_size))
return true else false
• Boolean Isfull(queue,Q_size)→if (no.of elements==Q_size)
return true else false
• Display()→ display queue items
Steps of Queue Insert
Or
q[++rear]=item
Steps of Queue Deletion
When front>rear it results empty queue.
Hence we need to make initial condition as
front=0and rear=-1 when front>rear
Printf(“Deleted item is %d”,q[front++]);
Disadvantages of linear queue
• On deletion of an element from existing queue, front pointer is
shifted to next position.
• This results into virtual deletion of an element.
• By doing so memory space which was occupied by deleted
element is wasted and hence inefficient memory utilization is
occur.
Overcome disadvantage of linear queue:
• To overcome disadvantage of linear queue, circular queue is use.
• We can solve this problem by joining the front and rear end of a queue to
make the queue as a circular queue .
• Circular queue is a linear data structure. It follows FIFO principle.
• In circular queue the last node is connected back to the first node to make
a circle.
Overcome disadvantage of linear queue:
• It is also called as “Ring buffer”.
• Items can inserted and deleted from a queue in O(1) time.
Types Of Queue
1. Circular Queue
2. Dequeue (Double Ended Queue)
3. Priority Queue
Circular Queue
Circular Queue
Enqueue(Insert) operation on Circular Queue:
• Step 1: Check for queue full
• If rear=max–1 and front=0 or if
front=rear+1 then
circular queue is full and insertion
operation is not possible.
otherwise go to step 2
• Step 2: Check position of rear pointer
If rear=max–1
then set rear=0 otherwise increment rear
by 1.
rear=(rear+1)%MAX
• Step 3: Insert element at the position pointer by
rear pointer.
q[rear]=Data
• Step 4: Check the position of front pointer
If front=–1 then set front as 0.
Insert &Overflow in C.Q.
Dequeue (Delete) operation on
Circular Queue:
• Step 1: Check for queue empty if (front = -1)
then circular queue is empty and deletion
operation
is not possible. otherwise go to step 2
• Step 2: Check for position of front and rear
pointers.
if front = rear then
Data = q[front];
set front=rear=-1
• Step 3: Check position of front
if front = Max-1
Data = q[front];
then set front=0;
otherwise
Data = q[front];
front = (front+1)%MAX
Delete &Underflow in C.Q.
• Advantages: optimal utilization of memory
• Disadvantages: i) May become infinite loop
ii)keeping track of r and f is difficult
Circular queue using Dynamic array
• The various operation done on CQ
• Create ()
Let us assume Qsize is 1
Int Qsize=1
Int *q, f=0, r=-1, count=0;
• insertQ():
Before inserting ,check for sufficient space in the queue .But once the
queue is full , we can increase the size of queue using relloc()
Delete () and display() are as
same as linear queue
