© 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










































































































































































































































































































学霸联盟