Scribd
Upload
4 views

DSA Module 02 Part 01

The document describes the Queue as an Abstract Data Type (ADT) with operations such as create, enqueue, dequeue, isEmpty, and isFull. It highlights the disadvantages of linear queues, particularly inefficient memory utilization, and introduces circular queues as a solution, which allows for optimal memory use and O(1) time complexity for insertions and deletions. Additionally, it outlines the operations for circular queues and discusses their advantages and disadvantages.

Uploaded by

Yeshwanth
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views

DSA Module 02 Part 01

The document describes the Queue as an Abstract Data Type (ADT) with operations such as create, enqueue, dequeue, isEmpty, and isFull. It highlights the disadvantages of linear queues, particularly inefficient memory utilization, and introduces circular queues as a solution, which allows for optimal memory use and O(1) time complexity for insertions and deletions. Additionally, it outlines the operations for circular queues and discusses their advantages and disadvantages.

Uploaded by

Yeshwanth
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 27

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

You might also like