1501118

Data Structures
and Algorithms

Chapter 7:
Queues

2nd semester AY2024

School of Information
Technology

Copyright 2025 School of IT

 Outline
• Introduction
• Abstract Data Types
– Enqueue
– Dequeue
• Array-Based Queue
• SLL Queue
• Double-Ended Queue
• Java Built-in Queue
• Summary
2
 Why Queues?
• Real world problems:
– Have you ever waited in line at the theatre box
office?
– Have you ever waited for filling up a motorbike
at a gas station?

• Need to manage
the queue/waiting
line by an organizer.
3
Image source: [Link]
 What is Queue?
• Collection of objects that are inserted and
removed according to First-in, First-out
(FIFO)

• The longest item being in the queue will be

removed first.

Out/Remove A B C D In/Add
 What is Queue?
• Operating systems:
– queue of printing jobs to send to the printer
– queue of programs / processes to be run
– queue of network data packets to send

• Programming:
– modeling a line of customers or clients through
a call-center application
– storing a task of computations to be executed in
order

5
 What is Queues?

Out/Remove In/Add
front rear

6
Image source: M. T. Goodrich et al., Data Structures and Algorithms in Java
 Operations of Queues
• If a queue is empty.

– add
• insert an element to front of queue

– remove
• do nothing element ‘A’

Remove A Add
7
 Adding Element to Queues
• If there are some elements in a queue.

– add
• insert an element after a rear of queue

element ‘D’

Remove A B C D Add
8
 Removing Element from Queues
• If there are some in queue.

– remove
• remove the front of queue
• return the element

element ‘A’

Remove A B C D Add
9
Methods of Queue Class

Queue

+enqueue(element:int): void
+dequeue(): int
+peek():int
+getSize(): int
+isEmpty(): Boolean
10
 Operations
• enqueue(int element)→ adds element to the
back of queue.
• dequeue( )→ removes and returns the first
element OR null if the queue is empty.
• peek( )→ returns the first without removing
it OR null if the queue is empty.
• getSize( )→ returns the no. of elements in
the queue.
• isEmpty( )→ return true if queue is empty 11
 enqueue(element:int)
• Check the queue is full, or not?

– If yes, display “queue is full”.

– If no, add new element to the back of queue.

FULL ???

Remove A B C D E Add
12
front rear
 dequeue( )
• Check the queue is empty, or not?
– If yes, return “null.” (ex: -999 in programming)
– If no,
• get the first element’s value
• update the first element’s position
• clear the queue’s first slot to “null” (optional)
• decrease no. of elements
• return the first element’s value Empty ???

Remove null null null null null

Add
13
front rear
 peek( )
• Check the queue is empty, or not?
– If yes, return “null.” (ex: -999 in programming)
– If no,
• get the first element’s value
• return the first element’s value
• there is no remove within the method

element ‘A’

Remove A B C D null
Add
14
front rear
 Array (-Based) Queues

• Array’s capacity is N elements

• Queue’s first element is stored in data[0]
• Size of queue is t+1
• data[t] is a last of the queue

15
Image source: M. T. Goodrich et al., Data Structures and Algorithms in Java
Array Queues: Class
ArrayQueue

- CAPACITY: int
- data: int[ ]
- first: int //index of first element
- size: int
+ ArrayQueue()
+ ArrayQueue(capacity: int)
+ enqueue(element:int): void
+ dequeue(): int
+ peek():int
+ getSize(): int
+ isEmpty(): Boolean 16
 ArrayQueue()
• Constructor method

• ArrayQueue()
– constructs queue with default CAPACITY

• ArrayQueue(capacity: int)
– constructs queue with given capacity

17
 Array Queue: Class
public class ArrayQueue {
//----------------- data --------------
private final int CAPACITY = 10;
private int[] data; //array to store queue data
private int front = 0; //pointer for first queue element
private int size = 0; //size of queue (no. of elements)

//----------------- method --------------

public ArrayQueue() {
data = new int[CAPACITY];
}

public ArrayQueue(int capacity) {

data = new int[capacity];
}
...

...

18
 Queue: getSize() & isEmpty()
...

...
//get current size (no. of elements)
public int getSize() {
return size;
}

//is queue empty?

public boolean isEmpty() {
if(size == 0) {
return true;
}
else {
return false;
}
//return (size == 0);
}
...

...

19
... Queue: printQueue()
...
//print all queue members
public void printQueue() {

?
}
...

...

20
... Queue: enqueue()
...
public void enqueue(int element) {

?
}
...

...

21
... Queue: peek()
...
public int peek() {

?
}
...

...

22
... Queue: dequeue()
...
public int dequeue() {

?
}
...

...

23
Queue: Expected Output
Queue is empty!

### Add Data to Empty queue ###

enqueue() : 1 2 3 4 5
Queue: 1 2 3 4 5

------ Remove 3 elements from Queue ------

dequeue() : 1
Queue: 2 3 4 5

dequeue() : 2
Queue: 3 4 5

dequeue() : 3
Queue: 4 5

+++ Add more Data to Queue +++

enqueue() : 10
Queue: 4 5 10

enqueue() : 20
Queue: 4 5 10 20

+++ Dequeue all data : +++

Remove 4 5 10 20
Queue is empty!

24
Array Queues: main( ) Codes
...

...

25
Array Queues: main( ) Codes
...

...

26
 Array Queues: Example
• Run this set of the source codes with an
empty queue:
1. enqueue(5); 4. enqueue(2);
2. enqueue(3); 5. enqueue(8);
3. dequeue(); 6. dequeue();

dequeue null null null null null

enqueue
27
 Array Queues: Example
• Run this set of the source codes with an
empty queue:
1. enqueue(5); 4. enqueue(2);
2. enqueue(3); 5. enqueue(8);
3. dequeue(); 6. dequeue();

dequeue 5
null null null null null
enqueue
28
 Array Queues: Example
• Run this set of the source codes with an
empty queue:
1. enqueue(5); 4. enqueue(2);
2. enqueue(3); 5. enqueue(8);
3. dequeue(); 6. dequeue();

dequeue 5 null
3 null null null
enqueue
29
 Array Queues: Example
• Run this set of the source codes with an
empty queue:
1. enqueue(5); 4. enqueue(2);
2. enqueue(3); 5. enqueue(8);
3. dequeue(); 6. dequeue();

dequeue 5 3 null null null

enqueue
30
 Array Queues: Example
• Run this set of the source codes with an
empty queue:
1. enqueue(5); 4. enqueue(2);
2. enqueue(3); 5. enqueue(8);
3. dequeue(); 6. dequeue();

dequeue null
3 null
2 null null
enqueue
31
 Array Queues: Example
• Run this set of the source codes with an
empty queue:
1. enqueue(5); 4. enqueue(2);
2. enqueue(3); 5. enqueue(8);
3. dequeue(); 6. dequeue();

dequeue null
3 2 null
8 null
enqueue
32
 Array Queues: Example
• Run this set of the source codes with an
empty queue:
1. enqueue(5); 4. enqueue(2);
2. enqueue(3); 5. enqueue(8);
3. dequeue(); 6. dequeue();

dequeue null
3 2 8 null
enqueue
33
 Array Queues: Example
• Run this set of the source codes with an
empty queue:
1. enqueue(5); 4. enqueue(2);
2. enqueue(3); 5. enqueue(8);
3. dequeue(); 6. enqueue();

END

dequeue null null

2 8 null
enqueue
34
 Array Queues: Limitation
element ‘A’

dequeue A B C D enqueue
By moving the
front t front index of
the array, it
element ‘B’
leads the queue
to have a
dequeue B C D enqueue smaller
capacity than N
front t
element ‘C’ elements.

dequeue C D enqueue
35
front t
 Circular Array (-Based) Queues

• Circular array—Wrap around the end

– Back of the queue can reverse to start at begin
of the array

• Array’s capacity is always N elements

36
Image source: M. T. Goodrich et al., Data Structures and Algorithms in Java
 Circular Array (-Based) Queues

• A next front after dequeue() is:

front=(front+1)%N
where N = capacity = [Link]

• A next index (rear) to enqueue() is:

rear=(front+size)%N

37
Image source: M. T. Goodrich et al., Data Structures and Algorithms in Java
 Array Queue– Circularly

dequeue A B C D null
enqueue
front rear
rear=3
3
2
D
C
front=0 1 B
0 A
n-1

38
Circular Array Queue– Example
• Given a circular array
rear=3
3 • front index
2 D //front=0
front=0 1 BC • rear index
//rear=3
0 A
• size
15 //size=4

39
 Circular Array Queue– Example
• dequeue(‘A’)
rear=3
front=1 3 • New front index:
2 D
1 BC f=(f+1)%N
f=(0+1)%16
element ‘A’
f=1%16
0 A f=1
15 • size
size--; //size=3

40
Circular Array Queue– Example
• enqueue(‘E’)
element ‘E’

rear=4
front=1 3 4 • New rear index:
2 D E
1 BC avail=(f+size)%N
avail=(1+3)%16
avail=4%16
0 avail=4
15 • size
size++; //size=4

41
 Exercise (Lecture Assignment)
• Given the set of the source codes with an empty queue:
1. enqueue(9); 6. dequeue();
2. enqueue(1); 7. dequeue();
3. dequeue(); 8. enqueue(4);
4. enqueue(7); 9. enqueue(11);
5. enqueue(6); 10. enqueue(23);

• What should be the values stored in the circular queue AFTER

finish execution? What are the indexes of front and rear?

dequeue null null null null null

enqueue
42
front rear
 Singly Link List Queue
• Appropriate memory usage
– Fit to the elements in the queue
• No capacity limit
• First element stored at Front/First node
• New element will be inserted at the back of
the queue
new element

head tail

1 2 3 null 43
 Double-Ended Queue
• Collection of objects that are inserted and
removed at both the front and the back of
the queue.

• Called deque (D.Q.) and usually pronounced

“deck”
enqueue enqueue
null null null null null

dequeue dequeue
44
front rear
 Java Built-in Queue
• There is NO direct queue class in Java
• However, Java creates queue as “interface”
and must be implemented with other
classes such as “ArrayDeque” or
“LinkedList”
• See more information at
[Link]
/java/util/[Link]

45
 Java Queue Interface

Source: [Link] 46
 Example
import [Link];
public class MainJavaQueue {
public static void main(String[] args) {
//Create a queue based on ArrayDeque class with default 16 capacity
ArrayDeque<Integer> queue = new ArrayDeque<>();
//add data to queue
[Link](1);
[Link](2);
[Link](3);
[Link]("Current queue: " + queue);

//peek
[Link]("First element = " + [Link]());

//remove all data and show

[Link]("Dequeue all"); Current queue: [1, 2, 3]
while(![Link]()) { First element = 1
[Link]([Link]()+" "); Dequeue all
} 1 2 3
}
} 47
 Summary
• What is Queues?
• How to implement the array-based queues?
• Explain operations on array queue.
• Explain operations on circular array queue.

48