程序代写代做代考 Java C COMP 250

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!