ITI 1121. Introduction to Computing II – subtitle
ITI 1121. Introduction to Computing II
Queue: applications
by
Marcel Turcotte
Version March 7, 2020
Preamble
Preamble
Overview
Overview
Queue: applications
We are interested in all aspects of queues in programming. We examine several examples
of their use, including resource sharing and simulation algorithms. We explore the concept
of breadth-first-search.
General objective:
This week, you will be able to implement a breadth-first-search algorithm.
1 31
Preamble
Learning objectives
Learning objectives
Justify the role of a queue in solving a computer problem.
Design a computer program requiring the use of a queue.
Implement a breadth-first-search.
Readings:
https://en.wikipedia.org/wiki/Breadth-first_search
2 31
https://en.wikipedia.org/wiki/Breadth-first_search
Preamble
Plan
Plan
1 Preamble
2 Introduction
3 Labyrinth
4 Implementation
5 Conclusions
6 Prologue
3 31
Asynchronous processing
Applications such as producer/consumer, client/server or sender/receiver require the
use of queues if the data processing is asynchronous.
Asynchronous processing means that the client and server are not synchronized, the
server is not ready or able to receive the data at the time and speed of sending.
This treatment requires a queue:
The client inserts data into the queue (enqueue);
The server removes data from the queue at the appropriate time (dequeue).
Such a queue is sometimes called a buffer.
4 31
Asynchronous processing
In particular, the inter-process communications in an operating system work like this.
1. Printer spooler.;
2. Buffered i/o;
3. access to disks;
4. the transmission of messages (packets) over a network.
5 31
Timeshare
CPU
rearfront
new process
dequeue() enqueue()
All modern operating systems are time-shared. One of the common techniques for
time-sharing is called round-robin. The first process in the queue (dequeue) is assigned a
time slot after which its execution is suspended and the process is put at the end of the
queue (enqueue), and we move on to the next process.
6 31
Communications between processes
enqueue()
client
server
dequeue()
whi le ( t rue ) {
whi le ( ! q . i s F u l l ( ) ) {
q . enqueue ( . . . ) ;
}
}
whi le ( t rue ) {
whi le ( ! q . empty ( ) ) {
p r o c e s s ( q . dequeue ( ) )
}
}
⇒ inter-process communication (IPC), buffered i/o, etc.
7 31
Applications
Simulations;
Customer
+getArrivalTime() : int
+getNumberOfItems() : int
+getNumberOfServedItems() : int
+serve() : void
-arrivalTime : int
-initialNumberOfItems : int
-numberOfItems : int
-MAX_NUM_ITEMS : int
Cashier
+addCustomer(c : Customer) : void
+getQueueSize() : int
+serveCustomers(currentTime : int) : void
+getTotalCustomerWaitTime() : int
+getTotalCustomersServed() : int
+getTotalItemsServed() : int
-queue : Queue
-currentCustomer : Customer
-totalCustomerWaitTime : int
-customersServed : int
-totalItemsServed : int
<
Queue
+enqueue(obj : Object) : void
+dequeue() : Object
+isEmpty() : boolean
+size() : int
ArrayQueue
<
Breadth-first-search.
8 31
Introduction
What displays the method Search.run()?
pub l i c c l a s s Search {
pub l i c s t a t i c vo id run ( ) {
Queue
q = new LinkedQueue
q . enqueue ( ” ” ) ;
whi le ( t rue ) {
S t r i n g s ;
s = q . dequeue ( ) ;
q . enqueue ( s + “0” ) ;
q . enqueue ( s + “1” ) ;
System . out . p r i n t l n ( q ) ;
}
}
}
9 31
What’s that for?
Queue
q = new LinkedQueue
q . enqueue ( ” ” ) ;
whi le ( t rue ) {
S t r i n g s ;
s = q . dequeue ( ) ;
q . enqueue ( s + “0” ) ;
q . enqueue ( s + “1” ) ;
System . out . p r i n t l n ( q ) ;
}
This algorithm generates all strings consisting of the symbols 0 and 1 in ascending
order of length: 0, 1, 00, 01, 10, 11, 000, 001, . . .
10 31
[“”]
[“0”]
[“0″,”1”]
[“1”]
[“1″,”00”]
[“1″,”00″,”01”]
[“00″,”01”]
[“00″,”01″,”10”]
[“00″,”01″,’10″,”11”]
[“01″,”10″,”11”]
[“01″,”10″,”11″,”000”]
[“01″,”10″,”11″,”000″,”001”]
[“10″,”11″,”000″,”001”]
[“10″,”11″,”000″,”001″,”010”]
[“10″,”11″,”000″,”001″,”010″,”011”]
[“11″,”000″,”001″,”010″,”011”]
[“11″,”000″,”001″,”010″,”011″,”100”]
[“11″,”000″,”001″,”010″,”011″,”100″,”101”]
What does it do?
Queue
q = new LinkedQueue
q . enqueue ( ” ” ) ;
whi le ( t rue ) {
S t r i n g s ;
s = q . dequeue ( ) ;
q . enqueue ( s + “L” ) ;
q . enqueue ( s + “R” ) ;
q . enqueue ( s + “U” ) ;
q . enqueue ( s + “D” ) ;
System . out . p r i n t l n ( q ) ;
}
This algorithm generates all strings formed by the symbols L, R, U and D in
increasing order of length: L, R, U, D, LL, LR, LU, LD, . . .
12 31
[]
[“”]
[]
[“L”]
[“L”,”R”]
[“L”,”R”,”U”]
[“L”,”R”,”U”,”D”]
[“R”,”U”,”D”]
[“R”,”U”,”D”,”LL”]
[“R”,”U”,”D”,”LL”,”LR”]
[“R”,”U”,”D”,”LL”,”LR”,”LU”]
[“R”,”U”,”D”,”LL”,”LR”,”LU”,”LD”]
[“U”,”D”,”LL”,”LR”,”LU”,”LD”]
[“U”,”D”,”LL”,”LR”,”LU”,”LD”,”RL”]
[“U”,”D”,”LL”,”LR”,”LU”,”LD”,”RL”,”RR”]
[“U”,”D”,”LL”,”LR”,”LU”,”LD”,”RL”,”RR”,”RU”]
[“U”,”D”,”LL”,”LR”,”LU”,”LD”,”RL”,”RR”,”RU”,”RD”]
[“D”,”LL”,”LR”,”LU”,”LD”,”RL”,”RR”,”RU”,”RD”]
[“D”,”LL”,”LR”,”LU”,”LD”,”RL”,”RR”,”RU”,”RD”,”UL”]
Labyrinth
Semantics
What are these Ls, Rs, Us and Ds?
Each symbol corresponds to a direction:
L = left;
R = right;
U = up;
D = down.
Each string corresponds to a path in two-dimensional space.
14 31
D DR
DRR DRRU
DRRUR DRRURR
Let’s add some obstacles.
Now let’s assume that some of the cells are unaccessible.
DRRURRDD DRRDRR
16 31
x
s
s + L
s + R
s + U
s + D
dequeue
enqueue
Finding the shortest path in a maze
19 31
Implementation
Helper methods
We’ll need a method that checks if a partial solution is valid, checkPath(String
path).
As well as a method that tells us if a valid solution achieves its goal,
reachesGoal(String path).
20 31
Data structures
A matrix of characters, i.e. a 2-dimensional array.
char [ ] [ ] maze ;
An inaccessible position (a wall) is denoted by ’#’, an empty cell by ’ ’, and a visited
position by ’+’.
#+#####
#+# # #
#++ # #
### #
##### #
21 31
checkpath(String path)
p r i v a t e boolean checkPath ( S t r i n g path ) {
boolean [ ] [ ] v i s i t e d ;
v i s i t e d = new boolean [MAX_ROW] [MAX_COL] ;
i n t row , c o l ;
row = 0 ;
c o l = 0 ;
i n t pos =0;
boolean v a l i d = t rue ;
22 31
checkpath(String path)
. . .
whi le ( v a l i d && pos < path . l e n g t h ( ) ) {
char d i r e c t i o n = path . charAt ( pos++);
switch ( d i r e c t i o n ) {
case LEFT :
co l −−;
break ;
case RIGHT :
c o l ++;
break ;
case UP:
row−−;
break ;
case DOWN:
row++;
break ;
de f au l t :
v a l i d = f a l s e ;
}
. . .
23 31
checkpath(String path)
After each move, we check that the current position is valid, i.e. inside the labyrinth,
is not a wall, and has not been visited.
i f ( ( row >= 0) && ( row < MAX_ROW) &&
( c o l >= 0) && ( c o l < MAX_COL) ) {
i f ( v i s i t e d [ row ] [ c o l ] | | g r i d [ row ] [ c o l ]==WALL) {
v a l i d = f a l s e ;
} e l s e {
v i s i t e d [ row ] [ c o l ] = t rue ;
}
} e l s e {
v a l i d = f a l s e ;
}
} // end o f w h i l e l oop
re tu rn v a l i d ;
}
24 31
«Are we done yet!»
p r i v a t e boolean r e a c h e s G o a l ( S t r i n g path ) {
i n t row = 0 ;
i n t c o l = 0 ;
f o r ( i n t pos =0; pos < path . l e n g t h ( ) ; pos++) {
char d i r e c t i o n = path . charAt ( pos ) ;
switch ( d i r e c t i o n ) {
case LEFT : co l −−; break ;
case RIGHT : c o l ++; break ;
case UP: row−−; break ;
case DOWN: row++; break ;
}
}
re tu rn g r i d [ row ] [ c o l ] == OUT;
}
25 31
Conclusions
Breadth-first-search
The algorithm using a queue is called breadth-first search.
The search tree is built level by level. All the sequences of the same level (thus all
the sequences of the same length) are processed before proceeding with the next level.
26 31
Depth-first-search
The algorithm using a stack is called the depth-first search.
The search tree is built branch by branch. A sequence is selected and repeatedly
extended until no extension is valid. The algorithm then backtracks, hence the
nickname backtracking.
27 31
Prologue
Summary
A breadth-first-search uses a queue to find the shortest path in a search space.
28 31
Next module
Queue : array-based implementation
29 31
References I
E. B. Koffman and Wolfgang P. A. T.
Data Structures: Abstraction and Design Using Java.
John Wiley & Sons, 3e edition, 2016.
30 31
Marcel Turcotte
Marcel.
School of Electrical Engineering and Computer Science (EECS)
University of Ottawa
31 / 31
Marcel.
Preamble
Overview
Learning objectives
Plan
Introduction
Labyrinth
Implementation
Conclusions
Prologue