QUEUE
[Link]
Professor
Sri Ramakrishna College of Arts & Science
Stack and Queue / Slide 2
Queue ADT
Like a stack, a queue is also a list. However,
with a queue, insertion is done at one end,
while deletion is performed at the other end.
Accessing the elements of queues follows a
First In, First Out (FIFO) order.
Like customers standing in a check-out line in a
store, the first customer in is the first customer
served.
Stack and Queue / Slide 3
The Queue ADT
Another form of restricted list
Insertion is done at one end, whereas deletion is performed at the
other end
Basic operations:
enqueue: insert an element at the rear of the list
dequeue: delete the element at the front of the list
First-in First-out (FIFO) list
Stack and Queue / Slide 4
Enqueue and Dequeue
Primary queue operations: Enqueue and Dequeue
Like check-out lines in a store, a queue has a front
and a rear.
Enqueue
Insert an element at the rear of the queue
Dequeue
Remove an element from the front of the queue
Remove Insert
(Dequeue) front rear (Enqueue)
Stack and Queue / Slide 5
Queue Implementation of Array
There are several different algorithms to
implement Enqueue and Dequeue
Naïve way
When enqueuing, the front index is always fixed
and the rear index moves forward in the array.
rear rear rear
3 3 6 3 6 9
front front front
Enqueue(3) Enqueue(6) Enqueue(9)
Stack and Queue / Slide 6
Create Queue
Queue(int size = 10)
Allocate a queue array of size. By default, size = 10.
front is set to 0, pointing to the first element of the
array
rear is set to -1. The queue is empty initially.
Queue::Queue(int size /* = 10 */) {
values = new double[size];
maxSize = size;
front = 0;
rear = -1;
counter = 0;
}
Stack and Queue / Slide 7
IsEmpty & IsFull
Since we keep track of the number of elements
that are actually in the queue: counter, it is
easy to check if the queue is empty or full.
bool Queue::IsEmpty() {
if (counter) return false;
else return true;
}
bool Queue::IsFull() {
if (counter < maxSize) return false;
else return true;
}
Stack and Queue / Slide 8
Insert
Procedure INSERTQ (Q, n, Item,
REAR)
IF ( REAR = n)
REAR = REAR + 1;
Q[REAR] = ITEM;
End INSERTQ
Stack and Queue / Slide 9
Delete
Procedure DELETEQ (Q, FRONT,
Item, REAR)
IF (FRONT = REAR)
FRONT = FRONT + 1;
Q[FRONT] = ITEM;
End DELETEQ
Stack and Queue / Slide 10
Thank You……….