Queues
l Introduction to Queues
l A queue is a waiting line
l It’s in daily life:
l A line of persons waiting to check out at a supermarket
l A line of persons waiting to purchase a ticket for a film
l A line of planes waiting to take off at an airport
l A line of vehicles at a toll booth
l Introduction to Queues
l Difference between Stack and Queues:
l Stack exhibits last-in-first-out (LIFO)
l Queue exhibits first-in-first-out (FIFO)
l The Queue Operations
A queue is like a line of
l
people waiting for a bank
teller. The queue has a
front and a rear.
$ $
Front
Rea
r
l The Queue Operations
New people must enter the queue at the
l
rear. The C++ queue class calls this a
push, although it is usually called an
enqueue operation.
$ $
Front
Rea
r
l The Queue Operations
When an item is taken from the queue, it
l
always comes from the front. The C++
queue calls this a pop, although it is
usually called a dequeue operation.
$ $
Front
Rea
r
• Queue Operations
• There are four basic queue operations.
• Data can be inserted at the rear and processed from the front.
[Link] ; inserts an element at the rear of the queue.
[Link] ; deletes an element at the front of the queue.
[Link] Front; examines the element at the front of the queue.
[Link] Rear; examines the element at the rear of the queue.
• Queue
Operations
• Queue
Operations
• Queue
Operations
• Queue
Operations
• If there are no data in the queue, then the queue is in an
• underflow state.
l Array Implementation
lA queue can be implemented with an array, as
shown here. For example, this queue contains the
integers 4 (at the front), 8 and 6 (at the rear).
[0] [1] [2] [3] [4] [5] ...
4 8 6
An array of integers
to implement a We don't care what's
queue of integers in
this part of the array.
l Array Implementation
The easiest implementation also keeps
l 3 siz
track of the number of items in the e
queue and the index of the first element first
0
(at the front of the queue), the last
element (at the rear).
2 last
[0] [1] [2] [3] [4] [5] ...
4 8 6
l A Dequeue Operation
When an element leaves the queue,
l 2 siz
size is decremented, and first changes, e
too. first
1
2 last
[0] [1] [2] [3] [4] [5] ...
4 8 6
l An Enqueue Operation
lWhen an element enters the queue, size 3 siz
is incremented, and last changes, too. e
1 first
3 last
[0] [1] [2] [3] [4] [5] ...
8 6 2
l At the End of the Array
There is special behavior at the end of
l 3 siz
the array. For example, suppose we e
want to add a new element to this first
3
queue, where the last index is [5]:
5 last
[0] [1] [2] [3] [4] [5]
2 6 1
l Array Implementation
Easy to implement
l
3 siz
But it has a limited capacity with a fixed array
l e
Or you must use a dynamic array for an unbounded
l
capacity 0 first
Special behavior is needed when the rear reaches
l
the end of the array.
2 last
[0] [1] [2] [3] [4] [5] ...
4 8 6
l Queue Full and Empty
Queue Full:
Rear=n (Maxsize of an
array)
Queue Empty:
Rear < Front
l Circular Queue
l Problems
l We quickly "walk off the end" of the array
l Possible solutions
l Shift array elements
l Use a circular queue
l Circular Queue
l Use of Linear Array to implement a queue.
l Waste of memory: The deleted elements can not be re-used.
l Solution: to use circular queue.
l Circular Queue Full and Empty
Unfortunately, it is difficult under this representation to
determine when the queue is empty.
The condition rear < front is no longer a valid test for the
empty queue.
One way to solve this problem is to establish the convention
that the value of front is the array index immediately
preceding the first element of the queue rather than the index
of the first element itself.
Thus, one element of the array is to be scarified and allow a
queue to grow only as large as one less than the size of the
array
l Circular Queue Full and Empty
Queue Full:
(rear +1) % n == front
Queue Empty:
front==rear
l Priority Queues
A Special form of queue from which items
are removed according to their designated
priority and not the order in which they
entered.
Two kinds of priority queues:
• Min priority queue.
• Max priority queue.
l Max Priority Queue
• Collection of elements.
• Each element has a priority or key.
• Supports following operations:
▪ empty
▪ size
▪ insert an element into the priority queue (push)
▪ get element with max priority (top)
▪ remove element with max priority (pop)
Logic
• Sorting
• use element key as priority
• insert elements to be sorted into a priority queue
• remove/pop elements in priority order
▪ if a min priority queue is used, elements are extracted in ascending
order of priority (or key)
▪ if a max priority queue is used, elements are extracted in
descending order of priority (or key)
Queue Application:
Josephus Problem
A set of players are present in a circle.
Counting from a given player, every ‘nth’ player is considered
out and eliminated from the game
Counting starts again from the next person after the removed
player, and the next ‘nth’ player is removed.
The game continues until only one player remains, who is the
winner
❖ Given the total number of person n and a number k which
indicates that k-1 persons are skipped and the kth person is
eliminated from a circle.
❖ The task is to choose the place in the initial circle so that you are
the last one remaining and so survive.
For example,
● if n = 5 and k = 2, then the safe position is 3. Firstly, the person at
position 2 is killed, then the person at position 4 is killed, then the
person at position 1 is killed. Finally, the person at position 5 is
killed. So the person at position 3 survives.
● If n = 7 and k = 3, then the safe position is 4. The persons at
positions 3, 6, 2, 7, 5, and 1 are killed in order, and the person at
position 4 survives.
Approach to solve Josephus problem iteratively:
N = 5, k = 2
Follow the below steps to Implement the idea:
● Initialize variables num, cnt, and cut with 1, 0, and 0
respectively and an array arr[] of size N with the initial value set
as 1.
● Run a while loop till cnt < N:
○ Run a while loop till num is less than equal to k.
■ Increment cut by one and take modulo by N
■ If arr[cut] = 1 increment num by one.
○ Set num = 1, arr[cut] = 0 and increment cnt and cut by one
and cut = cut % n;
○ Run a while loop till arr[cut] = 0 and increment cut by one.
● Return cnt + 1 as the required answer.
End of Chapter