Queues
Queue
Stores a set of elements in a particular
order
Stack principle: FIRST IN FIRST OUT
= FIFO
It means: the first element inserted is the
first one to be removed
Example
The first one in line is the first one to be
What is a queue?
Queues are linear data structures in which we add elements
to one end and remove them from the other end.
The first item to be en-queued is the first to be de-queued.
Queue is therefore called a First In First Out (FIFO)
structure.
Queue operations:
Enqueue /Insert
Dequeue / Delete
Empty
First In First Out
D rear
C rear C D rear
rear B B C
rear B front
fron A front A front B
A front A t
Applications of Queues
Direct applications
Waiting lists, bureaucracy
Access to shared resources (e.g., printer)
Multiprogramming
Indirect applications
Auxiliary data structure for algorithms
Component of other data structures
Application: Round Robin
Schedulers
We can implement a round robin scheduler using a queue Q by
repeatedly performing the following steps:
1. e = [Link](); [Link]()
2. Service element e
3. [Link](e)
Queue
Dequeue Enqueue
Shared
Service
6
ADT 3.2 Abstract Data Type
Queue
template <class KeyType>
class Queue
{
// objects: A finite ordered list with zero or more elements
public:
Queue(int MaxQueueSize = DefaultSize);
// Create an empty queue whose maximum size is MaxQueueSize
bool IsFull();
// if number of elements in the queue is equal to the maximum size of
// the queue, return TRUE(1); otherwise, return FALSE(0)
bool IsEmpty();
// if number of elements in the queue is equal to 0, return TRUE(1)
// else return FALSE(0)
ADT 3.2 Abstract Data Type
Queue (cont.)
void enQueue(const KeyType& item);
// if IsFull(), then QueueFull(); else insert item at rear of the queue
KeyType deQueue ();
// if IsEmpty(), then QueueEmpty() and return 0;
// else remove the item at the front of the queue and return a pointer to it
};
ADT 3.2 Abstract Data
Type Queue (cont.)
Implementation of Queue ADT
use an one-dim array
two variables
front : one less than the position of the first
element
rear : the position of the last element
data member declaration in class
template <class KeyType>
class Queue
private:
int front, rear;
keyType *queue;
int MaxSize;
public:
......
Implementation of
Queue
constructor definition
template <class KeyType>
Queue<KeyType>::Queue (int MaxQueueSize) : MaxSize (MaxQueueSize)
{
queue = new KeyType[MaxSize];
front = rear = -1;
}
member function IsFull()
template <class KeyType>
inline bool Queue<KeyType>::IsFull()
{
if (rear == MaxSize-1) return TRUE;
else return FALSE;
}
Implementation of Queue
(cont.)
member function IsEmpty()
template <class KeyType>
inline bool Queue<KeyType>::IsEmpty()
{
if (front == rear) return TRUE;
else return FALSE;
}
member function Add()
template <class KeyType>
void Queue<KeyType>::enQueue(const KeyType &x)
{
if (isFull) {cout << “Queue overflow”; exit(1);}
else queue[++rear] = x;
}
Implementation of Queue
(cont.)
member function Delete()
template <class KeyType>
KeyType Queue<KeyType>::deQueue ()
{
if (IsEmpty())
{
cout << “Queue underflow”;
exit(1);
}
KeyType x = queue[++front];
return x;
}
Queue in C++ STL
13
Queue Manipulation Issue
It’s intuitive to use array for
implementing a queue. However,
queue manipulations (add and/or
delete) will require elements in the
array to move. In the worse case,
the complexity is of O(MaxSize).
Shifting Elements in Queue
front rear
front rear
front rear
Solution 1
When ever remove is called move all the elements in the
start of queue.
KeyType x= queue[0]
for (int i=0; i <rear; i++)
queue [i] = queue [i+1];
rear--;
Solution 2
These problems can be avoided by
using a circular array – an array in
which the location of the front and
back index are allowed to change
and the contents to wrap around
when the last position in the buffer
is filled.
Circular Queue
Imagine that the two ends are joined together to form a
circle implemented by a circular
Queue
array
The Queue maintains two indices, front and rear, that initially are
both SIZE -1
1 2
0
3
rear
front 9
4
8
7 5
6
Insertion in queue
2 3
1
rear 4
back
0
x
5
front 9
8 6
7
Queue implemented using circular array
Assume that X denotes the indices in the buffer that hold
an object.
2 3
x x
1
x 4
back
x
rear
0
x
front
front
5
9
8 6
7
buffer
Deletion of element from queue
Assume that X denotes the indices in the buffer that hold
an object.
2 3
x x
1
x 4
back
x rear
0
front
5
9
8 6
7
buffer
Implementation of Circular
Queue
constructor definition
template <class KeyType>
Queue<KeyType>::Queue (int MaxQueueSize) : MaxSize (MaxQueueSize)
{
queue = new KeyType[MaxSize];
front = rear =MaxSize -1;
}
Queue
Operations
front 2 3
rear
X X
1
X 4
X
0 X
X
X 5
9
X X X
8 6
7
When array is full again front is equal to rear
so we can not differentiate whether array is
full or empty
Queue
Operations
front 2 3
X X
1
4
X
rear 0 X
X
X 5
9
X X X
8 6
7
So we sacrifice one element.
Implementation of Circular
Queue (cont.)
member function Add()
template <class KeyType>
void Queue<KeyType>::Add(const KeyType& x)
// add x to the circular queue
{
int k = (rear+1) % MaxSize;
if (front = = k)
{
cout << “Queue overflow”;
exit(1);
}
else
{
queue[k] = x;
rear = k;
}
}
Implementation of Circular
Queue (cont.)
member function Delete()
template <class KeyType>
KeyType Queue<KeyType>::Delete()
// remove front element from queue
{
if (front == rear)
{
cout << “Queue overflow”;
exit(1);
}
front = (front+1)%MaxSize;
KeyType x = queue[front];
return x;
}
Priority Queues
Priority queue is a data structure in which
intrinsic ordering of elements determines
the result of basic operations.
Two kinds of priority queues:
•Ascending priority queue/Min priority
Queue
•Descending priority queue/MAX priority
Queue
Min Priority Queue
• Collection of elements into which
elements are inserted arbitrarily and
smallest element is removed.
• Each element has a priority or key.
• Supports following operations:
isEmpty
insert an element into the priority queue
get element with min priority
remove element with min priority
Max Priority Queue
• Collection of elements into which
elements are inserted arbitrarily and
largest element is removed.
• Each element has a priority or key.
• Supports following operations:
isEmpty
insert an element into the priority queue
get element with max priority
remove element with max priority
Applications
Sorting
• use element key as priority
• put elements to be sorted into a
priority queue
• extract elements in priority order
if a min priority queue is used, elements
are extracted in ascending order of
priority
if a max priority queue is used, elements
are extracted in descending order of
Sorting Example
Sort five elements whose keys are 6, 8,
2, 4, 1 using a max priority queue.
Put the five elements into a max priority
queue.
Do five removemax() operations placing
removed elements into the sorted array
from right to left.
After Putting Into Max Priority
Queue
8 4 6
1
Max
2 Priority
Queue
Sorted Array
After First Remove Max
Operation
4 6
1
Max
2 Priority
Queue
Sorted Array
After Second Remove Max
Operation
4
1
Max
2 Priority
Queue
6 8
Sorted Array
After Third Remove Max
Operation
1
Max
2 Priority
Queue
4 6 8
Sorted Array
After Fourth Remove Max
Operation
1
Max
Priority
Queue
2 4 6 8
Sorted Array
After Fifth Remove Max
Operation
Max
Priority
Queue
1 2 4 6 8
Sorted Array
Queue
Operations
Suppose n elements of a priority queue are maintained in
positions 0 to n-1 of an array of size maxpq then pqinsert(pq,x)
is strightforward.
template <class KeyType>
void insert(KeyType x)
{
if (rear >= MaxSize - 1)
{
cout << “Queue Overflow”;
exit(1);
}
queue[rear] = x;
rear++;
} // elements are nor ordered.
For deletion there are two issues.
[Link] locate the smallest element.
[Link] to delete a middle element of the array.
Deletion Operation
Solutions
1.A special empty() indicator can be placed
into a deleted position. Insertion is done
as given before.
[Link] operation labels a position as
empty but insertion is done at the first
empty position.
[Link] deletion compact the array by
shifting all elements past the deleted
element by one position and
decrementing [Link] by 1.
[Link] the array sorted.
DEQUEUE
A dequeue is an ordered set of elements
from which elements may be deleted at
either end and into which items may be
inserted at either end.
Basic operations:
•Remvleft
•Remvroght
•Insrtleft
•Insrtright