xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

c代写-ECE36800

时间：2021-02-19

© Andrew H. Jones & Cheng-Kok Koh 1

ECE36800 Data structures

Queues

Chapter 4 (pp. 153-161)

Chapter 9 (pp. 383-392)

© Andrew H. Jones & Cheng-Kok Koh 2

Overview

● Queue definition

● Primitive operators

● Linked list implementation

● Array implementation

● Priority queues

● Reference pages: pp. 153-161, pp. 383-392

© Andrew H. Jones & Cheng-Kok Koh 3

Queues

● A queue is an ordered collection of items where items are inserted

(enqueued) at the end and are removed (dequeued) from the front

● Can also be called FIFO (First In First Out)

● A check-out line at grocery store, for example

– The line (queue) is either empty or not empty

– The cashier serves the customer at the front of the line

– Customers are ordered from the front to the end of line

– Customers can only join at the end of the ine

● Other examples:

– Printer queues

– Buffer queue of switching packets in data communication

© Andrew H. Jones & Cheng-Kok Koh 4

Primitive operators

● Enqueue(Q, i)

– Add item i at the end/rear of queue Q

– Must make sure it does not cause overflow

● Dequeue(S)

– Get the front item of queue Q, remove it from Q and return it, e.g., i = Dequeue(Q)

– Must make sure that queue was not empty

● Front(Q)

– Return the front item of queue Q with no change to Q, e.g., i = Front(Q)

– Must make sure that queue was not empty

● Rear(Q)

– Return the last item of queue Q with no change to Q, e.g., i = Rear(Q)

– Must make sure that queue was not empty

● Empty(Q) (or Is_empty(Q))

– Return true if queue Q is empty; false otherwise

© Andrew H. Jones & Cheng-Kok Koh 5

Linked list implementation

● Seek O(1) time complexity for all primitive operations

● Must maintain both head and tail of linked list for access of front and rear

● Empty list == Empty queue

● Head of list == Queue front

– Meaningful only if list is not empty

● Tail of list == Queue rear

– Meaningful only if list is not empty

● Insert at tail = Enqueue

– To check for overflow, verify that the address returned by malloc is not NULL

● Remove at head = Dequeue

– Meaningful only if list is not empty

● What would be the time complexity for each of the primitive operations for

a queue if the head of the linked list is the queue rear and the tail is the

queue front?

© Andrew H. Jones & Cheng-Kok Koh 6

Linked list example

3 6 1

Front

NULL

3 = Dequeue(Q)

6 1

Front

NULL

6 1 4

Front

NULL

Enqueue(Q, 4)

Rear

Rear

Rear

© Andrew H. Jones & Cheng-Kok Koh 7

Array implementation

● Use a struct to store four fields:

– Address of the array to store items

– Total size of the array

– Index of the queue front

– Index of the queue rear

● First attempt (assume the array is of infinite size)

– Assume that front and rear indices initialized to 0 for an empty queue

● We may initialize front and rear differently and would have to implement the primitive

operations slightly differently

– Empty queue == number of items in queue = rear index – front index is 0

– Queue front == item in array at location indexed by front (if queue not empty)

– Queue rear == item in array at location indexed by rear – 1 (if queue not empty)

– Enqueue == Store item in array at location indexed by rear, increment rear

– Dequeue == Store in a temporary variable the item in the array at location

indexed by front (if queue not empty), increment front, return value stored in the

temporary variable

© Andrew H. Jones & Cheng-Kok Koh 8

???? ? ...

front = 0

rear = 0

???3 ? ...

front = 0 rear = 1

Enqueue(Q, 3)

??13 ? ...

front = 0 rear = 2

Enqueue(Q, 1)

?613 ? ...

front = 0 rear = 3

Enqueue(Q, 6)

?613 ? ...

front = 1 rear = 3

Dequeue(Q)

3 is not over-written in the

array even though it is no

longer a valid entry in queue

4613 ? ...

front = 1 rear = 4

Enqueue(Q, 4)

© Andrew H. Jones & Cheng-Kok Koh 9

Array example: array size of 5

4613 ?

front = 1 rear = 4

4613 ?

front = 2 rear = 4

Dequeue(Q)

1 is not over-written in the

array even though it is no

longer a valid entry in queue

4613 ?

front = 3 rear = 4

Dequeue(Q)

6 is not over-written in the

array even though it is no

longer a valid entry in queue

4613 2

front = 3 rear = 5

Enqueue(Q, 2)

Enqueue(Q, 7)?

© Andrew H. Jones & Cheng-Kok Koh 10

Enqueue(Q, 7)

● Resize array (recall dynamically growing stack array by a

multiplicative factor)

– Wasting space vacated by dequeue operations

● Copy all valid entries to the left and update indices, then enqueue

– O(n), if there are n items in the queue

– Worst case scenario, 1 empty slot in front, enqueue, dequeue, enqueue,

dequeue, ...

4613 2

front = 3 rear = 5

4624 2

front = 0 rear = 2

4724 2

front = 0 rear = 3

Enqueue(Q, 7)

Copy entries to

left

© Andrew H. Jones & Cheng-Kok Koh 11

Enqueue(Q, 7)

● Use a circular array (or circular buffer), i.e., the index rear = 5 is

equivalent to rear = 5 mod 5 = 0

– We apply modulo 5 because that is the size of the array

– When we increment the index, instead of doing (rear + 1) or (front + 1),

we perform (rear + 1) mod 5 or (front + 1) mod 5

– From slide 9, we would have the following after Enqueue(Q, 2)

– If we ask for the rear element, we perform (rear – 1) mod 5 = (0 – 1)

mod 5 = 4 to get the index of the rear element

● The number of valid items in queue is (rear – front) mod 5

– (rear – front) mod 5 = (1 – 3) mod 5 = –2 mod 5 = 3

4613 2

front = 3rear = 0

rear = 1 front = 3

Enqueue(Q, 7) 4617 2

Enqueue(Q, 2)

© Andrew H. Jones & Cheng-Kok Koh 12

Queue is full

● The number of valid entries in queue = (rear – front) mod 5 = 0

– Solution 1: We include one more field in the struct for queue to indicate

whether a queue is empty or a queue is fully occupied

– Solution 2: We only fill up to (array size – 1) elements; when (rear + 1)

mod 5 is the same as front, the array is deemed “full”

rear = 1 front = 3

Enqueue(Q, 7) 4613 2

rear = 2 front = 3

Enqueue(Q, 0) 4603 2

rear = 3

front = 3

Enqueue(Q, 8) 4803 2

© Andrew H. Jones & Cheng-Kok Koh 13

Queue is full: Solution 2

rear = 2 front = 3

Enqueue(Q, 0) 4603 2

rear = 3

front = 3

Enqueue(Q, 8) 4803 2

rear = 3

front = 3

Reallocate (assume

we double the size) 4803 2 ???? ?

Turn it into valid

queue by copying

4 and 2 to the right

end of the array

and update front

rear = 3 front = 8

4803 2 4??? 2

© Andrew H. Jones & Cheng-Kok Koh 14

Queue is full: Alternate solution 2

rear = 2 front = 3

Enqueue(Q, 0) 4603 2

rear = 3

front = 3

Enqueue(Q, 8) 4803 2

rear = 3

front = 3

Reallocate (assume

we double the size) 4803 2 ???? ?

Turn it into valid

queue by copying

3, 0, and 8 to the

right end of 4 and

2, and update rear

front = 3 rear = 8

4803 2 ?803 ?

© Andrew H. Jones & Cheng-Kok Koh 15

Queue is full

● Typically, pick the left or right partition to copy to the new

location based on the size of the partition to minimize

overhead

● Can also grow the array first before enqueuing the new

element

– Grow the array

– If left partition has fewer elements, copy the left partition to the right

of the right partition, update rear

– Else copy the right partition to the right of array, update front

– Enqueue new element

● Average time complexity of enqueue operation is O(1)

© Andrew H. Jones & Cheng-Kok Koh 16

Double-ended queues (deques)

● A queue is an ordered collection of items where items may be

inserted (enqueued) and removed (dequeued) from either end (left

or right, front or rear, first or last)

● Primitive operators

– Empty(DQ) or Is_empty(DQ)

– Left(DQ), Right(DQ)

– Dequeue_left(DQ), Dequeue_right(DQ)

– Enqueue_left(DQ, i) or Enqueue_right(DQ, I)

● Doubly-linked list or array implementation would allow O(1) time

complexity for all operators

● Can be used to implement stacks or queues

© Andrew H. Jones & Cheng-Kok Koh 17

Priority queues (PQs)

● A priority queue is an ordered collection of items where items

are removed (dequeued) in the order of their levels of priority

– Ascending priority queue: A sequence of dequeue operations

remove items in ascending order of levels of priority (lowest or

minimum first)

– Descending priority queue: A sequence of dequeue operations

remove items in descending order of levels of priority (highest or

maximum first)

● Can be used to implement stacks or queues, with the level of

priority of an item being the time the item is pushed or

enqueued, respectively

© Andrew H. Jones & Cheng-Kok Koh 18

Linked list implementation

● Implementation with an unordered linked list

– O(1) to enqueue

● Insert at the beginning of the list

– O(n) to dequeue, where n is the number of items in the list

● Must always visit all items to find the item with the minimum or maximum

priority for removal

● Implementation with an ordered linked list

– O(n) to enqueue

● On the average, visit n/2 items for inserting the new item at the correct sorted

position (see insertion sort)

– O(1) to dequeue

● The item with the minimum or maximum priority is at the beginning of the list

© Andrew H. Jones & Cheng-Kok Koh 19

Array implementation

● Unordered array

– O(1) to enqueue

● Insert at the beginning of the list

– O(n) to dequeue, where n is the number of items in the list

● Must always visit all items to find the item with the minimum or maximum priority for

removal

● Ordered array (ascending array for descending priority queue and

descending array for ascending priority queue)

– O(n) to enqueue

● This is simply insertion of a new item into a sorted array

● On the average, visit n/2 items for inserting the new item at the correct sorted position

– O(1) to dequeue

● The item with the minimum or maximum priority is at the (right) end of the array

© Andrew H. Jones & Cheng-Kok Koh 20

A better array implementation

● An array can be interpreted as a tree, with indices

of items determining their positions within the tree

– Called a heap

– A max-heap implements a descending priority queue

and a min-heap implements an ascending priority

queue

– O(log n) for enqueue and dequeue, where n is the

number of items in the heap

– Will elaborate on heaps when we cover heap sort

学霸联盟

ECE36800 Data structures

Queues

Chapter 4 (pp. 153-161)

Chapter 9 (pp. 383-392)

© Andrew H. Jones & Cheng-Kok Koh 2

Overview

● Queue definition

● Primitive operators

● Linked list implementation

● Array implementation

● Priority queues

● Reference pages: pp. 153-161, pp. 383-392

© Andrew H. Jones & Cheng-Kok Koh 3

Queues

● A queue is an ordered collection of items where items are inserted

(enqueued) at the end and are removed (dequeued) from the front

● Can also be called FIFO (First In First Out)

● A check-out line at grocery store, for example

– The line (queue) is either empty or not empty

– The cashier serves the customer at the front of the line

– Customers are ordered from the front to the end of line

– Customers can only join at the end of the ine

● Other examples:

– Printer queues

– Buffer queue of switching packets in data communication

© Andrew H. Jones & Cheng-Kok Koh 4

Primitive operators

● Enqueue(Q, i)

– Add item i at the end/rear of queue Q

– Must make sure it does not cause overflow

● Dequeue(S)

– Get the front item of queue Q, remove it from Q and return it, e.g., i = Dequeue(Q)

– Must make sure that queue was not empty

● Front(Q)

– Return the front item of queue Q with no change to Q, e.g., i = Front(Q)

– Must make sure that queue was not empty

● Rear(Q)

– Return the last item of queue Q with no change to Q, e.g., i = Rear(Q)

– Must make sure that queue was not empty

● Empty(Q) (or Is_empty(Q))

– Return true if queue Q is empty; false otherwise

© Andrew H. Jones & Cheng-Kok Koh 5

Linked list implementation

● Seek O(1) time complexity for all primitive operations

● Must maintain both head and tail of linked list for access of front and rear

● Empty list == Empty queue

● Head of list == Queue front

– Meaningful only if list is not empty

● Tail of list == Queue rear

– Meaningful only if list is not empty

● Insert at tail = Enqueue

– To check for overflow, verify that the address returned by malloc is not NULL

● Remove at head = Dequeue

– Meaningful only if list is not empty

● What would be the time complexity for each of the primitive operations for

a queue if the head of the linked list is the queue rear and the tail is the

queue front?

© Andrew H. Jones & Cheng-Kok Koh 6

Linked list example

3 6 1

Front

NULL

3 = Dequeue(Q)

6 1

Front

NULL

6 1 4

Front

NULL

Enqueue(Q, 4)

Rear

Rear

Rear

© Andrew H. Jones & Cheng-Kok Koh 7

Array implementation

● Use a struct to store four fields:

– Address of the array to store items

– Total size of the array

– Index of the queue front

– Index of the queue rear

● First attempt (assume the array is of infinite size)

– Assume that front and rear indices initialized to 0 for an empty queue

● We may initialize front and rear differently and would have to implement the primitive

operations slightly differently

– Empty queue == number of items in queue = rear index – front index is 0

– Queue front == item in array at location indexed by front (if queue not empty)

– Queue rear == item in array at location indexed by rear – 1 (if queue not empty)

– Enqueue == Store item in array at location indexed by rear, increment rear

– Dequeue == Store in a temporary variable the item in the array at location

indexed by front (if queue not empty), increment front, return value stored in the

temporary variable

© Andrew H. Jones & Cheng-Kok Koh 8

???? ? ...

front = 0

rear = 0

???3 ? ...

front = 0 rear = 1

Enqueue(Q, 3)

??13 ? ...

front = 0 rear = 2

Enqueue(Q, 1)

?613 ? ...

front = 0 rear = 3

Enqueue(Q, 6)

?613 ? ...

front = 1 rear = 3

Dequeue(Q)

3 is not over-written in the

array even though it is no

longer a valid entry in queue

4613 ? ...

front = 1 rear = 4

Enqueue(Q, 4)

© Andrew H. Jones & Cheng-Kok Koh 9

Array example: array size of 5

4613 ?

front = 1 rear = 4

4613 ?

front = 2 rear = 4

Dequeue(Q)

1 is not over-written in the

array even though it is no

longer a valid entry in queue

4613 ?

front = 3 rear = 4

Dequeue(Q)

6 is not over-written in the

array even though it is no

longer a valid entry in queue

4613 2

front = 3 rear = 5

Enqueue(Q, 2)

Enqueue(Q, 7)?

© Andrew H. Jones & Cheng-Kok Koh 10

Enqueue(Q, 7)

● Resize array (recall dynamically growing stack array by a

multiplicative factor)

– Wasting space vacated by dequeue operations

● Copy all valid entries to the left and update indices, then enqueue

– O(n), if there are n items in the queue

– Worst case scenario, 1 empty slot in front, enqueue, dequeue, enqueue,

dequeue, ...

4613 2

front = 3 rear = 5

4624 2

front = 0 rear = 2

4724 2

front = 0 rear = 3

Enqueue(Q, 7)

Copy entries to

left

© Andrew H. Jones & Cheng-Kok Koh 11

Enqueue(Q, 7)

● Use a circular array (or circular buffer), i.e., the index rear = 5 is

equivalent to rear = 5 mod 5 = 0

– We apply modulo 5 because that is the size of the array

– When we increment the index, instead of doing (rear + 1) or (front + 1),

we perform (rear + 1) mod 5 or (front + 1) mod 5

– From slide 9, we would have the following after Enqueue(Q, 2)

– If we ask for the rear element, we perform (rear – 1) mod 5 = (0 – 1)

mod 5 = 4 to get the index of the rear element

● The number of valid items in queue is (rear – front) mod 5

– (rear – front) mod 5 = (1 – 3) mod 5 = –2 mod 5 = 3

4613 2

front = 3rear = 0

rear = 1 front = 3

Enqueue(Q, 7) 4617 2

Enqueue(Q, 2)

© Andrew H. Jones & Cheng-Kok Koh 12

Queue is full

● The number of valid entries in queue = (rear – front) mod 5 = 0

– Solution 1: We include one more field in the struct for queue to indicate

whether a queue is empty or a queue is fully occupied

– Solution 2: We only fill up to (array size – 1) elements; when (rear + 1)

mod 5 is the same as front, the array is deemed “full”

rear = 1 front = 3

Enqueue(Q, 7) 4613 2

rear = 2 front = 3

Enqueue(Q, 0) 4603 2

rear = 3

front = 3

Enqueue(Q, 8) 4803 2

© Andrew H. Jones & Cheng-Kok Koh 13

Queue is full: Solution 2

rear = 2 front = 3

Enqueue(Q, 0) 4603 2

rear = 3

front = 3

Enqueue(Q, 8) 4803 2

rear = 3

front = 3

Reallocate (assume

we double the size) 4803 2 ???? ?

Turn it into valid

queue by copying

4 and 2 to the right

end of the array

and update front

rear = 3 front = 8

4803 2 4??? 2

© Andrew H. Jones & Cheng-Kok Koh 14

Queue is full: Alternate solution 2

rear = 2 front = 3

Enqueue(Q, 0) 4603 2

rear = 3

front = 3

Enqueue(Q, 8) 4803 2

rear = 3

front = 3

Reallocate (assume

we double the size) 4803 2 ???? ?

Turn it into valid

queue by copying

3, 0, and 8 to the

right end of 4 and

2, and update rear

front = 3 rear = 8

4803 2 ?803 ?

© Andrew H. Jones & Cheng-Kok Koh 15

Queue is full

● Typically, pick the left or right partition to copy to the new

location based on the size of the partition to minimize

overhead

● Can also grow the array first before enqueuing the new

element

– Grow the array

– If left partition has fewer elements, copy the left partition to the right

of the right partition, update rear

– Else copy the right partition to the right of array, update front

– Enqueue new element

● Average time complexity of enqueue operation is O(1)

© Andrew H. Jones & Cheng-Kok Koh 16

Double-ended queues (deques)

● A queue is an ordered collection of items where items may be

inserted (enqueued) and removed (dequeued) from either end (left

or right, front or rear, first or last)

● Primitive operators

– Empty(DQ) or Is_empty(DQ)

– Left(DQ), Right(DQ)

– Dequeue_left(DQ), Dequeue_right(DQ)

– Enqueue_left(DQ, i) or Enqueue_right(DQ, I)

● Doubly-linked list or array implementation would allow O(1) time

complexity for all operators

● Can be used to implement stacks or queues

© Andrew H. Jones & Cheng-Kok Koh 17

Priority queues (PQs)

● A priority queue is an ordered collection of items where items

are removed (dequeued) in the order of their levels of priority

– Ascending priority queue: A sequence of dequeue operations

remove items in ascending order of levels of priority (lowest or

minimum first)

– Descending priority queue: A sequence of dequeue operations

remove items in descending order of levels of priority (highest or

maximum first)

● Can be used to implement stacks or queues, with the level of

priority of an item being the time the item is pushed or

enqueued, respectively

© Andrew H. Jones & Cheng-Kok Koh 18

Linked list implementation

● Implementation with an unordered linked list

– O(1) to enqueue

● Insert at the beginning of the list

– O(n) to dequeue, where n is the number of items in the list

● Must always visit all items to find the item with the minimum or maximum

priority for removal

● Implementation with an ordered linked list

– O(n) to enqueue

● On the average, visit n/2 items for inserting the new item at the correct sorted

position (see insertion sort)

– O(1) to dequeue

● The item with the minimum or maximum priority is at the beginning of the list

© Andrew H. Jones & Cheng-Kok Koh 19

Array implementation

● Unordered array

– O(1) to enqueue

● Insert at the beginning of the list

– O(n) to dequeue, where n is the number of items in the list

● Must always visit all items to find the item with the minimum or maximum priority for

removal

● Ordered array (ascending array for descending priority queue and

descending array for ascending priority queue)

– O(n) to enqueue

● This is simply insertion of a new item into a sorted array

● On the average, visit n/2 items for inserting the new item at the correct sorted position

– O(1) to dequeue

● The item with the minimum or maximum priority is at the (right) end of the array

© Andrew H. Jones & Cheng-Kok Koh 20

A better array implementation

● An array can be interpreted as a tree, with indices

of items determining their positions within the tree

– Called a heap

– A max-heap implements a descending priority queue

and a min-heap implements an ascending priority

queue

– O(log n) for enqueue and dequeue, where n is the

number of items in the heap

– Will elaborate on heaps when we cover heap sort

学霸联盟