COMP 250
INTRODUCTION TO COMPUTER SCIENCE
Week 7-2 : Queues
Giulia Alberini, Fall 2020 Slides adapted from Michael Langer’s
WHAT ARE WE GOING TO DO IN THIS VIDEO?
Queues
ADT (ABSTRACT DATA TYPE)
List
add(i, e), remove(i), get(i), set(i), …..
Stack
push(e) , pop(), ..
Queue
enqueue(e), dequeue()
QUEUE
dequeue
(remove from front)
enqueue (add at back)
e.g. Server
clients
EXAMPLES
keyboard buffer
CPU processes (applications do not run in parallel) web server
students in the zoom waiting room
…
Stack push(e) pop()
LIFO
(last in, first out)
Stack push(e) pop()
LIFO
(last in, first out)
Queue enqueue( e ) dequeue()
FIFO
(first in, first out)
“first come, first serve”
QUEUE EXAMPLE
enqueue(a) a enqueue(b) ab
dequeue()
b returns a
time
QUEUE EXAMPLE
enqueue(a) a enqueue(b) ab
dequeue()
enqueue(c) bc enqueue(d) bcd enqueue(e) bcde
b returns a
time
QUEUE EXAMPLE
enqueue(a) a enqueue(b) ab
dequeue()
enqueue(c) bc enqueue(d) bcd enqueue(e) bcde
dequeue()
enqueue(f) cdef enqueue(g) cdefg
b returns a
cde returns b
time
HOW TO IMPLEMENT A QUEUE?
singly linked list doubly linked list array list
enqueue(e) dequeue()
HOW TO IMPLEMENT A QUEUE?
enqueue(e) dequeue()
addLast(e) removeFirst()
singly linked list doubly linked list array list
HOW TO IMPLEMENT A QUEUE?
enqueue(e) dequeue()
addLast(e) removeFirst()
(same, or addFirst() & removeLast())
singly linked list doubly linked list array list
HOW TO IMPLEMENT A QUEUE?
singly linked list doubly linked list array list
enqueue(e)
dequeue()
addLast(e) removeFirst()
(same, or addFirst() & removeLast())
addLast(e) removeFirst()
SLOW!
IMPLEMENTING A QUEUE WITH AN ARRAY LIST (BAD)
length = 4
enqueue( a ) a— enqueue( b ) ab– dequeue( ) b—
Requires shift
0 1 2 3
indices
0123
IMPLEMENTING A QUEUE WITH AN ARRAY LIST (BAD)
length = 4
enqueue( a
enqueue( b
dequeue( )
enqueue( c ) bc– enqueue( d ) bcd- enqueue( e ) bcde dequeue( ) cde-
Requires shift
) a— ) ab– b—
012 3
indices
0123
Requires shift
IMPLEMENTING A QUEUE WITH AN ARRAY LIST (BAD)
length = 4
enqueue( a ) enqueue( b ) dequeue( ) enqueue( c ) enqueue( d ) enqueue( e ) dequeue( ) enqueue( f ) enqueue( g )
requires expansion
0 1 2 3
indices
0123
a— ab– b— bc– bcd- bcde cde- cdef
cdefg—
IMPLEMENTING A QUEUE WITH AN EXPANDING ARRAY (ALSO BAD) Use head and tail indices
a— ab– -b– -bc- -bcd
enqueue( a )
enqueue( b )
dequeue( )
enqueue( c )
enqueue( d )
enqueue( e )
dequeue( )
enqueue( f ) –cdef– (2,5) enqueue( g ) –cdefg- (2,6)
012 3
(tail = head + size – 1)
? — (1,4)
–cde— (2,4)
(0,0) (0,1) (1,1) (1,2) (1,3)
IMPLEMENTING A QUEUE WITH AN EXPANDING ARRAY (ALSO BAD) Use head and tail indices
enqueue( a ) enqueue( b ) dequeue( ) enqueue( c ) enqueue( d ) enqueue( e ) dequeue( ) enqueue( f ) enqueue( g )
(0,0) (0,1) (1,1) (1,2) (1,3) (1,4) (2,4) (2,5) (2,6)
Make bigger array and copy to it.
012 3
(tail = head + size – 1)
a— ab– -b– -bc- -bcd
-bcde— –cde— –cdef– –cdefg-
IMPLEMENTING A QUEUE WITH AN EXPANDING ARRAY
to dequeue: retrieve the element at head and increase the index head
to enqueue: add the element at tail + 1
An expanding array is an inefficient usage of space! A better idea is…
CIRCULAR ARRAY
length = 4
0123
length = 8
01234567
21
0
0123
01234567
1
0
3
2347
5
6
IMPLEMENTING A QUEUE WITH A CIRCULAR ARRAY (GOOD) tail = (head + size – 1) mod length
enqueue( a )
enqueue( b )
dequeue() ?
head
0
3
0123
tail
1
ba
ab–
head=0 tail=1
2
IMPLEMENTING A QUEUE WITH A CIRCULAR ARRAY (GOOD) tail = (head + size – 1) mod length
enqueue( a )
enqueue( b )
dequeue()
enqueue( c ) ?
0123
head
tail
1
b
0
3
-b–
head=1 tail=1
2
IMPLEMENTING A QUEUE WITH A CIRCULAR ARRAY (GOOD) tail = (head + size – 1) mod length
enqueue( a )
enqueue( b )
dequeue()
enqueue( c )
enqueue( d ) ?
0123
head
1
b c
2
tail
0
3
-bc-
head=1 tail=2
IMPLEMENTING A QUEUE WITH A CIRCULAR ARRAY (GOOD) tail = (head + size – 1) mod length
enqueue( a ) enqueue( b ) dequeue() enqueue( c ) enqueue( d ) enqueue( e ) ?
0123
head
1
0
3
tail
b cd
-bcd
head=1 tail=3
2
IMPLEMENTING A QUEUE WITH A CIRCULAR ARRAY (GOOD) tail = (head + size – 1) mod length
enqueue( a )
enqueue( b )
dequeue() 0123 enqueue( c )
enqueue( d )
enqueue( e )
dequeue() ?
head=1 tail=0
head
tail
0
3
1
ebcd
2
be cd
IMPLEMENTING A QUEUE WITH A CIRCULAR ARRAY (GOOD) tail = (head + size – 1) mod length
enqueue( a )
enqueue( b )
dequeue() 0123 enqueue( c )
enqueue( d )
enqueue( e )
dequeue()
head=2 tail=0
tail
0
3
e-cd
2
head
1
e cd
IMPLEMENTING A QUEUE WITH A CIRCULAR ARRAY (GOOD) tail = (head + size – 1) mod length
enqueue( a ) enqueue( b ) dequeue() enqueue( c ) enqueue( d ) enqueue( e ) dequeue() enqueue( f ) enqueue( g ) ?
0123
tail
efcd
head=2
tail=1
2
head
1
0
3
fe cd
INCREASE THE LENGTH OF THE ARRAY AND COPY
Be careful, on how you copy! The following would not work:
tail head
0123
head = 2 tail = 1 size =4
enqueue(g) ?
efc d
e f c d – – —
tail head
INCREASE THE LENGTH OF THE ARRAY AND COPY
Instead you can copy so that the head remains in the same position.
tail head
0123
head = 2 tail = 1 size =4
head = 2 enqueue(g) tail = 5 size =4
efc d
— c d e f —
head tail
INCREASE THE LENGTH OF THE ARRAY AND COPY
OR you can copy so that the head moves to position 0.
tail head
0123
head = 2 tail = 1 size =4
head = 0 enqueue(g) tail = 3 size =4
efc d
c d e f – – —
head tail
ENQUEUE( e )
enqueue( element ){
if (size == queue.length) {
// increase length of array
create a bigger array tmp[ ] // e.g. 2*length for i = 0 to queue.length – 1
tmp[i] = queue[(head + i) mod queue.length]
head = 0
queue = tmp }
queue[(head + size) mod length] = element
size++ }
Note that we don’t have a tail variable here. Instead, recall that tail = (head + size -1) mod length, and note that the new element is added in position (tail + 1) mod length.
DEQUEUE()
dequeue() {
if size <= 0
raise error
element = queue[head]
size = size – 1
head = (head + 1) mod length
return element
}
WHAT IF SIZE IS 0?
What is the relation between head and tail when size is equal to 0?
tail = (head + size – 1) mod length
array (head, tail, size) Initial state ---- (0, 3, 0)
WHAT IF SIZE IS 0?
What is the relation between head and tail when size is equal to 0?
tail = (head + size – 1) % length
Initial state
enqueue( a )
enqueue( b )
dequeue()
dequeue()
array (head, tail, size) ---- (0, 3, 0) a--- (0, 0, 1) ab-- (0, 1, 2) -b-- (1, 1, 1) ---- (2, 1, 0)
tail head
ADT (ABSTRACT DATA TYPE)
Defines a data type by the values and operations from the user’s perspective only. It ignores the details of the implementation.
Examples:
list
stack queue ...
In the next videos:
Back to Java: interfaces!