Queues
All credit to Dr. G.S. Lehal
DEFINITION OF QUEUE
A Queue is an ordered collection of items from
which items may be deleted at one end (called the
front of the queue) and into which items may be
inserted at the other end (the rear of the queue).
The first element inserted into the queue is the first
element to be removed. For this reason a queue is
sometimes called a FIFO (first-in first- out) list as
opposed to the stack, which is a LIFO (last-in first-
out).
Queues
Basic Queue Operations
There are two basic operations that can be
performed on a queue:
Enqueue: This operation inserts or adds data in
the queue. The data will be added to the rear of
the queue.
Dequeue: This operation removes the data,
which has been in the queue for the longest
time. The data is present in the front of the
queue.
Enqueue
Adding an element
Front of queue
New element is
added to the rear
of the queue
Dequeue
Removing an element
New front element of queue
Element is
removed from the
front of the
queue
Basic Queue Operations
Implementation of the Queues
There are many possible ways to implement the
queues:
An array with front at index 0
An array with floating front and rear
A circular array with floating front and rear
(wrap around array)
A singly linked list with front
A singly linked list with front and rear
A doubly linked list
Array Implementation of the
Queues
We must keep track of both the front and the rear of the queue.
One method is to keep the front of the array in the first location
on the array. Then, we can simply increase the counter of the
array to show the rear.
Nevertheless, to delete an entry from this queue is very
expensive, since after the first entry was served, all the
existing entry need to be move back one position to fill in
the vacancy.
With a long queue this process can lead to poor performance.
Array with front at index 0
Before: ‘a’ ‘c’ ‘d’ ‘g’ ‘v’ ‘e’
front
0 1 2 3 4 5
rear
‘c’ ‘d’ ‘g’ ‘v’ ‘e’ ‘a’ at index 0 is deleted
0 1 2 3 4 5
After: ‘c’ ‘d’ ‘g’ ‘v’ ‘e’
0 1 2 3 4 5
Linear Implementation of Queues
Indicate the front and rear of the queue. We can keep
track the entry of the queue without moving any entries.
Append an entry: increase the rear by one.
To remove the entry: increase the front by one.
Problem:
Position of front will increase and never decrease
This leads to the end of the storage capacity
Linear Imple mentation of
Queues
Add ‘k’ to the queue: ‘a’ ‘c’ ‘d’ ‘g’ ‘k’
- rear + 1 (increase) 0 1 2 3 4 5
front
rear
Delete ‘a’ in queue: ‘a’ ‘c’ ‘d’ ‘g’ ‘k’
- front + 1 (increase) 0 1 2 3 4 5
front rear
Add ‘z’ to the queue: ‘c’ ‘d’ ‘g’ ‘k’ ‘z’
-rear + 1 (increase)
0 1 2 3 4 5
rear
front
Reach end of storage!!
Need for Circular Queues
• Queues implemented as linear arrays have the
drawback that once the queue is FULL, even
though we delete few elements from the "front"
and relieve some occupied space, we are not able
to add anymore elements, as the "rear" has
already reached the Queue's rear most position.
Need for Circular Queues
To solve this problem, queues implement
wrapping around. Such queues are called
Circular Queues.
Both the front and the rear pointers wrap
around to the beginning of the array.
Circular queues are better than normal queues as
they effectively utilise the memory space.
Circular Queues
Circular Queues
Queue with 6 elements
Circular Queues
dequeue()
Circular Queues
enqueue(6)
Circular Queues
enqueue(52)
Circular Queues
dequeue()
Circular Queues
enqueue(63)
Circular Queues
enqueue(29)
Circular Queues
dequeue()
Circular Queues
dequeue()
Circular Queues
dequeue()
Circular Queues
dequeue()
Circular Queues
dequeue()
Circular Queues
dequeue()
Circular Queues
dequeue()
Circular Queues
Empty Queue
dequeue()
Circular Queues
Full Queue
Array Implementation of the
Circular Queues
typedef char QueueItemType;
class Queue{
public:
Queue(int size);
~Queue(); bool
isEmpty(); bool
isFull();
bool enqueue(QueueItemType newItem); bool
dequeue(QueueItemType *QueueTop);
private:
QueueItemType *items;
int front, rear, count;
int MaxQueue;
};
Array Implementation of the
Circular Queues
Queue::Queue(int size) {
items = new QueueItemType[size];
MaxQueue = size;
front = 0;
rear = -1;
count = 0;
}
Queue:: ~Queue(){
delete [] items;
items = NULL;
}
Array Implementation of the
Circular Queues
bool Queue::isEmpty()
{ return count <= 0;
}
bool Queue::isFull() {
return count >=
MaxQueue-1;
}
Array Implementation of the
Circular Queues
bool Queue::enqueue(QueueItemType newItem){ if
(isFull())
return false;
else{
rear = (rear + 1) % MaxQueue;
items[rear] = newItem; count+
+;
return true;
}
}
Array Implementation of the
Circular Queues
bool Queue::dequeue (QueueItemType
*QueueTop){
if (isEmpty())
return false;
else {
count--;
*QueueTop
=
items[fron
t];
front = (front + 1) % MaxQueue;
return true;
main(){
QueueItemType c;
Queue Queue(4);
[Link]('a');
[Link]('b');
[Link]('c');
[Link](&c);
printf("%c\n",c);
[Link](&c);
printf("%c\n",c);
[Link]('d');
[Link](&c);
[Link](‘e');
printf("%c\n",c);
[Link](&c);
printf("%c\n",c);
[Link](&c);
printf("%c\n",c);
}
queue(4)
Count = 0
Items[3]
Items[2]
Items[1]
Items[0] Front = 0
Rear = -1
enqueue (’a’)
Count = 1
Items[3]
Items[2]
Items[1]
Items[0] a Rear = 0
Front = 0
enqueue (’b’)
Count = 2
Items[3]
Items[2]
Items[1] b Rear = 1
Items[0] a Front = 0
enqueue (’c’)
Count = 3
Items[3]
Items[2] c Rear = 2
Items[1] b
Items[0] a Front = 0
dequeue (&c)
Count = 2
Items[3]
Items[2] c Rear = 2
Items[1] b Front = 1
Items[0] a
dequeue (&c)
Count = 1
Items[3]
c Rear = 2
Items[2]
Front = 2
Items[1] b
Items[0] a
enqueue (’d’)
Count = 2
Items[3] d Rear = 3
Items[2] c Front = 2
Items[1] b
Items[0] a
dequeue (&c)
Count = 1
d Rear = 3
Items[3]
Front = 3
Items[2] c
Items[1] b
a
Items[0]
enqueue (’e’)
Count = 2
Items[3] d Front = 3
Items[2] c
Items[1] b
Items[0] e Rear = 0
dequeue (&c)
Count = 1
Items[3] d
Items[2] c
b
Rear = 0
Items[1]
Items[0] e
Front = 0
dequeue (&c)
Count = 0
Items[3] d
Items[2] c
Items[1] b Front = 1
Items[0] e Rear = 0
Applications of Queues
Queues are used in operating systems, for
controlling access to shared system resources
such as:
Printer
Disk access on a network
CPU
Printer Queue
Disk Queue
Process Queues
Queues in Simulation
Simulation of Airplane Traffic
Other Applications of Queues
Reading from the keyboard
Implementing buffer
Level order traversal of trees or breadth first
search in a graph
Implementing Radix Sort
Buffers
Breadth First Traversal of Graph
Radix Sort
Radix Sort Algorithm
1. Place all the integers in the main queue.
2. Remove each value in the main queue and place it in a
digit queue corresponding to the digit being
considered, starting with the least significant digit.
3. Once all the values are placed in the appropriate digit
queue, collect the values from queue 0 to queue 9,
and place them back in the main queue.
4. Repeat steps 2 and 3 with the tens digit, the hundreds
digit, and so on. After the last digit is processed, the
main queue contains the values in ascending order.
45834 06283 56323 92634 78332 55111
0
1
2
3
4
5
6
7
8
9
45834 06283 56323 92634 78332 55111
0
1
2
3
4 45834
5
6
7
8
9
06283 56323 92634 78332 55111
0
1
2
3 06283
4 45834
5
6
7
8
9
56323 92634 78332 55111
0
1
2
3 06283 56323
4 45834
5
6
7
8
9
92634 78332 55111
0
1
2
3 06283 56323
4 45834 92634
5
6
7
8
9
78332 55111
0
1
2 78332
3 06283 56323
4 45834 92634
5
6
7
8
9
55111
0
1 5511
2 1
78332
3 06283 56323
4 45834 92634
5
6
7
8
9
0
1 55111
2 78332
3 06283 56323
4 45834 92634
5
6
7
8
9
55111
0
1 55111
2 78332
3 06283 56323
4 45834 92634
5
6
7
8
9
55111 78332
0
1
2 78332
3 06283 56323
4 45834 92634
5
6
7
8
9
55111 78332 06283 56323
0
1
2
3 06283 56323
4 45834 92634
5
6
7
8
9
55111 78332 06283 56323 45834 92634
0
1
2
3
4 45834 92634
5
6
7
8
9
55111 78332 06283 56323 45834 92634
0
1 55111
2 56323
3 78332 45834 92634
4
5
6
7
8
06283
9
55111 56323 78332 45834 92634 06283
0
1 55111
2 56323
3 78332 45834 92634
4
5
6
7
8
06283
9
55111 56323 78332 45834 92634 06283
0
1 55111
2 06283
3 56323 78332
4
5
6 92634
7
8
9 45834
55111 06283 56323 78332 92634 45834
0
1 55111
2 06283
3 56323 78332
4
5
6 92634
7
8
45834
9
55111 06283 56323 78332 92634 45834
0
1
2 92634
3
4
5 55111 45834
6 06283 56323
7
8
78332
9
92634 55111 45834 06283 56323 78332
0
1
2 92634
3
4
5 55111 45834
6 06283 56323
7
8
78332
9
92634 55111 45834 06283 56323 78332
0 06283
1
2
3
4 45834
5 56323
5511
6 1
7
78332
8
9
92634
06283 45834 55111 56323 78332 92634
0 06283
1
2
3
4 45834
5 56323
5511
6 1
7
78332
8
9
92634
06283 45834 55111 56323 78332 92634
0
1
2
3
4
5
6
7
8
9
Questions on Stacks and
Queues
How do you implement a stack using two
queues? Using one queue?
How do you implement a queue using two
stacks?
Given a string containing N S's and N X's where
S indicates a push operation and X indicates a
pop operation, and with the stack initially
empty, Formulate a rule to check whether a
given string S of operations is admissible or not.