Faculty of Information Technology

Chapter 5: Queues
(Data Structures and Algorithms)
 Outline

1 Queue abstract data type

2 Implement Queue

3 Application of Queue

4 Exercises

ISLab- Intelligent Systems Laboratory 2

 Queue abstract data type
• A queue is a list from which items are inserted at the
other end (rear, or back) which items are deleted from
one end (front)
It is like line of people waiting to purchase tickets.
• Queue is referred to as a first-in-first-out (FIFO) data
structure. The first item inserted into a queue is the first
item to leave.

ISLab- Intelligent Systems Laboratory 3

 The Abstract Data Type Queue
• Queues have many applications in computer
systems:
– Any application where a group of items is waiting to
use a shared resource will use a queue. e.g.
• jobs in a single processor computer
• print spooling
• information packets in computer networks.

ISLab- Intelligent Systems Laboratory 4

 ADT Queue Operations
• createQueue()
– Create an empty queue
• destroyQueue()
– Destroy a queue
• isEmpty()
– Determine whether a queue is empty
• isFull()
– Check whether queue is full or not
• enqueue()
– Inserts a new item at the end of the queue (at the rear of the queue)
• dequeue()
– Get and remove (return value) the element at the front of the queue
(was added earliest)
• getFront()
– Retrieve the item that was added earliest (without removing)
• ……

11/06/2021 5
ISLab- Intelligent Systems Laboratory 5
 ADT Queue Operations

ISLab- Intelligent Systems Laboratory 6

 Some Queue Operations
Operation Queue after operation
x.createQueue() an empty queue
front

x.enqueue(5) 5
x.enqueue(3) 5 3
x.enqueue(2) 5 3 2
x.dequeue() 3 2
x.enqueue(7) 3 2 7
x.dequeue(a) 2 7 (a is 3)
x.getFront(b) 2 7 (b is 2)

ISLab- Intelligent Systems Laboratory 7

 Outline

1 Queue abstract data type

2 Implement Queue

3 Application of Queue

4 Exercises

ISLab- Intelligent Systems Laboratory 8

 Implementations of the ADT Queue
• Array-based implementations of queue
– A naive array-based implementation of queue
– A circular array-based implementation of queue
• Pointer-based implementations of queue
– A linear linked list with two external references
• A reference to the front
• A reference to the back
– A circular linked list with one external reference
• A reference to the back

ISLab- Intelligent Systems Laboratory 9

 Implementation of Array-based Queue

• Rightward drift can cause the queue to appear full even

though the queue contains few entries.
• We may shift the elements to left in order to compensate
for rightward drift, but shifting is expensive
• Solution: A circular array eliminates rightward drift.
ISLab- Intelligent Systems Laboratory 10
 Implementation of Array-based Queue
• A Circular array-based Implementation

When either front or back

advances past MAX_QUEUE-1
it wraps around to 0.

ISLab- Intelligent Systems Laboratory 11

 Implementation of Array-based Queue
• The effect of some operations of the queue
Initialize: front=0; back=MAX_QUEUE-1;

Insertion : back = (back+1) % MAX_QUEUE;

items[back] = newItem; NOT ENOUGH

Deletion : front = (front+1) % MAX_QUEUE;

ISLab- Intelligent Systems Laboratory 12

 Implementation of Array-based Queue
• PROBLEM – Queue is Empty or Full

front and back cannot be used

to distinguish between queue-full
and queue-empty conditions.

? Empty
(back+1)%MAX_QUEUE == front

? Full
(back+1)%MAX_QUEUE == front

So, we need extra mechanism to

distinguish between queue-full
and queue-empty conditions.

ISLab- Intelligent Systems Laboratory 13

 Implementation of Array-based Queue
Solutions for Queue-Empty/Queue-Full Problem
1. Using a counter to keep the number items in the queue.
• Initialize count to 0 during creation; Increment count by 1 during insertion;
Decrement count by 1 during deletion.
• count=0  empty; count=MAX_QUEUE  full
2. Using isFull flag to distinguish between the full and empty
conditions.
• When the queue becomes full, set isFullFlag to true; When the queue is not
full set isFull flag to false;
3. Using an extra array location (and leaving at least one empty
location in the queue=> more efficient)
• Declare MAX_QUEUE+1 locations for the array items, but only use
MAX_QUEUE of them. We do not use one of the array locations.
• Full: front equals to (back+1)%(MAX_QUEUE+1)
• Empty: front equals to back
ISLab- Intelligent Systems Laboratory 14
 Implementations of Pointer-based Queue
• a linear linked list with two external pointers

• a circular linear linked list with one external pointer

ISLab- Intelligent Systems Laboratory 15

 A linked list Implementation -- enqueue
• Inserting an item into a nonempty queue

Inserting an item into an empty queue

a) before insertion b) after insertion

ISLab- Intelligent Systems Laboratory 16

 A Linked list Implementation -- dequeue
Deleting an item from a queue of more than one item

Deleting an item from a queue with one item

tempPtr = frontPtr;
frontPtr = NULL;
backPtr = NULL;
tempPtr delete tempPtr;

before deletion after deletion

ISLab- Intelligent Systems Laboratory 17

 A circular linked list with one external pointer
Queue Operations
constructor ?
isEmpty ?
enqueue ?
dequeue ?
getFront ?

ISLab- Intelligent Systems Laboratory 18

 Comparing Implementations
• Fixed size versus dynamic size
– A statically allocated array:
• Prevents the enqueue operation from adding an item to the queue if
the array is full
– A resizable array or a reference-based implementation
• Does not impose this restriction on the enqueue operation
• Pointer-based implementations
– A linked list implementation
• More efficient; no size limit
– The ADT list implementation
• Simpler to write; inefficient

ISLab- Intelligent Systems Laboratory 19

 A Summary of Position-Oriented ADTs
• Position-oriented ADTs: List, Stack, Queue
• Stacks and Queues: Only the end positions can be accessed
• Lists: All positions can be accessed
• Stacks and queues are very similar. Operations of stacks and
queues can be paired off as
• createStack and createQueue
• Stack isEmpty and queue isEmpty
• push and enqueue
• pop and dequeue
• Stack getTop and queue getFront
• ADT list operations generalize stack and queue operations
– insert, remove, first
ISLab- Intelligent Systems Laboratory 20
 Outline

1 Queue abstract data type

2 Implement Queue

3 Application of Queue

4 Exercises

ISLab- Intelligent Systems Laboratory 21

• Queue is used whenever we need to manage any group
of objects in an order in which the first one coming in,
also gets out first while the others wait for their turn,
e.g.:
– Serving requests on a single shared resources, like a printer,
CPU task scheduling etc.
– Call Center phone systems uses Queues to hold people calling
them in an order, until a service representative is free.
– Handling of interrupts in real-time systems. The interrupts are
handled in the same order as they arrive i.e First come first
served.

ISLab- Intelligent Systems Laboratory 22

An Application -- Reading a String of Characters
• A queue can retain characters in the order in which they
are typed

aQueue.createQueue()
while (not end of line) {
Read a new character ch
aQueue.enqueue(ch)
}

• Once the characters are in a queue, the system can

process them as necessary

ISLab- Intelligent Systems Laboratory 23

 Recognizing Palindromes
• A palindrome
– A palindrome is a word, number, phrase, or other sequence of characters
which reads the same backward as forward, such as madam, racecar.
– That mean a string of characters that reads the same from left to right as its
does from right to left.
• Solution ideas?
 To recognize a palindrome, a queue can be used in
conjunction with a stack
– A stack reverses the order of occurrences
– A queue preserves the order of occurrences
 A nonrecursive recognition algorithm for palindromes
– As you traverse the character string from left to right, insert each character
into both a queue and a stack
– Compare the characters at the front of the queue and the top of the stack
ISLab- Intelligent Systems Laboratory 24
 Recognizing Palindromes

The results of inserting a string

into both a queue and a stack

ISLab- Intelligent Systems Laboratory 25

 Recognizing Palindromes -- Algorithm
• Recursive algorithm:
bool isPal(char str[], int left, int right) {
if (left >= right) //Could I have used == instead?
return true;
if (str[left] == str[right])
return isPal(str, left+1, right-1);
return false;

//to be called from main as isPal(“rotator”, 0, 6);

ISLab- Intelligent Systems Laboratory 26

 Recognizing Palindromes
• Iterative algorithm:
isPal(in str:string) : boolean // Determines whether str is a palindrome or not
aQueue.createQueue(); aStack.createStack();
len = length of str;
for (i=1 through len) {
nextChar = ith character of str;
aQueue.enqueue(nextChar);
aStack.push(nextChar);
}
charactersAreEqual = true;
while (aQueue is not empty and charactersAreEqual) {
aQueue.getFront(queueFront);
aStack.getTop(stackTop);
if (queueFront equals to stackTop) { aQueue.dequeue(); aStack.pop()}; }
else charactersAreEqual = false; }
return charactersAreEqual;

ISLab- Intelligent Systems Laboratory 27

 Example: BFS
• Breadth-First Search
– To be explored while discussing Graphs
– Key search algorithm to explore graphs, e.g., network of
people like Facebook

ISLab- Intelligent Systems Laboratory 28

 Summary
• The definition of the queue operations gives the ADT
queue first-in, first-out (FIFO) behavior
• A pointer-based implementation of a queue uses either
– A circular linked list
– A linear linked list with a front reference and a back reference
• A circular array eliminates the problem of rightward
drift in an array-based implementation
– Distinguishing between the queue-full and queue-empty
conditions in a circular array
• Count the number of items in the queue
• Use a isFull flag
• Leave one array location empty
ISLab- Intelligent Systems Laboratory 29
 Homework
• Coding program to implement all operations of array
based Queue and Linked based Queue.

ISLab- Intelligent Systems Laboratory 30

 Thanks for your attention!

Please finish your homework in time!

 Application: Josephus Problem
• N men, circular arrangement. Kill every second. Where to sit to
survive?

• History: N men surrounded by enemies. Preferred suicide rather than captured as slaves.
Every men killed the next living men until 1 man is left. That guy (Josephus) then
surrendered (did not tell this initially ‘cos others’d turn on him)
ISLab- Intelligent Systems Laboratory 32
 Application: Josephus Problem
• N men, circular arrangement. Kill every second. Where
to sit to survive?
• List winners/survivors for each N to see a pattern
N W(N)
1 1
2 1
3 3
4 1
5 3
6 5
7 7
8 1
9 3
10 5
11 7
12 9
13 11
14 13
15 15
16 1
17 3

ISLab- Intelligent Systems Laboratory 33

 Application: Josephus Problem
• N men, circular arrangement. Kill every second. Where
to sit to survive?
• List winners/survivors for each N to see a pattern
N W(N)
1 1
2 1
3 3
4 1 Pattern # 1
5 3 Winner always odd!
6 5 Makes sense as the first loop kills all the evens
7 7
8 1
9 3
10 5
11 7
12 9
13 11
14 13
15 15
16 1
17 3

ISLab- Intelligent Systems Laboratory 34

 Application: Josephus Problem
• N men. Circular arrangement. Kill every second. Where
to sit to survive?
• List winners/survivors for each N to see a pattern
N W(N)
1 1
2 1
3 3
4 1 Pattern # 2
5 3 Jump by 2; reset at 2a for some a!
6 5 Makes sense: Assume 2a men in circle. 1 pass
7 7 removes half of them; at 1; repeat on 2a-1 men; so
8 1 winner is the starting point (1)
9 3
10 5
11 7
12 9
13 11
14 13
15 15
16 1
17 3

ISLab- Intelligent Systems Laboratory 35

 Application: Josephus Problem
• N men. Circular arrangement. Kill every second. Where
to sit to survive?
• List winners/survivors for each N to see a pattern
N W(N)
1 1
2 1
3 3
4 1 Pattern # 2 (cont’d)
5 3 Jump by 2; reset at 2a for some a!
6 5 Makes sense: Assume 2a + b men in circle, where a
7 7 is the biggest possible power; hence b < 2a (binary
8 1 notation idea); after b men we are left with 2a men,
9 3 whose winner is the starting point (11 for below)
10 5
11 7
12 9
13 11
14 13
15 15
8 left
16
17
1
3 4 left 2 left 1 left

ISLab- Intelligent Systems Laboratory 36

 Application: Josephus Problem
• N men. Circular arrangement. Kill every second. Where
to sit to survive?
• List winners/survivors for each N to see a pattern
N W(N)
1 1
2 1
3 3
4 1 Pattern # 2 (cont’d)
5 3 Jump by 2; reset at 2a for some a!
6 5 So what is 11 for N=13?
7 7 N = 23 + 5 (a=3, b=5); and 11 = 2*5 + 1
8 1 In general, after b steps, we arrive at the
9 3 position 2*b + 1 (every 2nd is killed). Hence,
10 5
11 7 W(N) = 2*b + 1
12 9 where N = 2a + b and b < 2a
13 11
14 13
15 15
8 left
16
17
1
3 4 left 2 left 1 left

ISLab- Intelligent Systems Laboratory 37

 Application: Josephus Problem
• Based on W(N) = 2*b + 1 where N = 2a + b and b < 2a
we can write a simple program that returns the
winner/survivor index

int W(int N) {
int a = 0;
while (N > 1) {
N /= 2;
a++;
}
return 2*(N – pow(2, a)) + 1;
}
ISLab- Intelligent Systems Laboratory 38
 Application: Josephus Problem

• Based on W(N) = 2*b + 1 where N = 2a + b and b < 2a we can write a

simple program that returns the winner/survivor index
• If you do not like math and cannot extract W(N) above, you can write
the code using a Queue
• Math gets way complicated for the generic problem where you kill
every kth man where k > 1
int Josephus(Q, k) { //Queue Q is built in advance with e.g., 1, 2, 3, 4, 5,
6.
while (Q.size() > 1) {
for (i = 1; i <= k-1; i++) //skip the k-1 men without killing
Q.enqueue( Q.dequeue() );
killed = Q.dequeue();
}
return Q.dequeue(); } //only one left in the Q, the winner 
ISLab- Intelligent Systems Laboratory 39