5.2.3 A C++ Queue Interface
We design our own queue that throws the QueueEmpty exception
This queue does not have a limit on size but many applications would like an upper limit
Note the const keywords in 2 places.
1 | template <typeName E> |
Implementing with arrays.
- A queue can be implemented via array.
- Keeping track of the
front
would require Q[0] to be the front of the queue, and to keep track of the number of elements to find therear
.- Not efficient because: if dequeueing, need to shift the entire array by one place.
- What do?
- Not efficient because: if dequeueing, need to shift the entire array by one place.
- Keeping track of the
Using an Array in a Circular Way
https://www.youtube.com/watch?v=okr-XE8yTO8
To avoid moving objects once they are placed in Q
, define 3 variables f
, r
, n
.
f
is the index of the front of the queue.r
is the index of the space after the last element (rear) of the queue.n
is the number of current elements in the queue.
Initially, we set n = 0 and f = r = 0, indicating an empty queue.
- When we dequeue an element from the front of the queue, we decrement n and increment f to the next cell in Q.
- Likewise, when we enqueue an element, we increment r and increment n.
This allows us to implement the enqueue and dequeue functions in constant time.
Immediate Issue with this method:
- It’s because of the way enqueue() and dequeue() are implemented. Both increment based on what’s being added or what’s being removed. So we’re not really removing any value–rather we just move through the array and pretend like the values in front of the
f
index do not exist within the queue (which they don’t, but they do exist on the array).
Lets say we have the following:
Array size is N = 5
and an array of integers called Q which we will use as a queue
Draw your queue and keep track of f,r,n as we execute the following:
Operation | f | r | n |
---|---|---|---|
enqueue(5) | 0 | 1 | 1 |
enqueue(10) | 0 | 2 | 2 |
dequeue() | 1 | 2 | 1 |
enqueue(15) | 1 | 3 | 2 |
dequeue() | 2 | 3 | 1 |
dequeue() | 3 | 3 | 0 |
enqueue(2) | 3 | 4 | 1 |
dequeue() | 4 | 4 | 0 |
f | ||||
---|---|---|---|---|
5 | 10 | 15 | 2 | |
r | ||||
A[0] | A[1] | A[2] | A[3] | A[4] |
- The queue is now full?! Yes! F and R, if incremented again with dequeue() or enqueue(), will go out-of-bounds.
enqueue(1)
will result in an out-of-bounds.- This is because when we dequeue,
f
moves one forward, meaning that the index prior becomes inaccessible.
- This is because when we dequeue,
Circular Array
To avoid this problem and be able to utilize all of the array Q, we let the f and r indices “wrap around” the end of Q. That is, we now view Q as a “circular array” that goes from Q[0] to Q[N −1] and then immediately back to Q[0] again.
We stated earlier that . . .
dequeue()
means incrementingf
, and (decrementingn
)enqueue()
means incrementingr
, and (incrementingn
)
Instead, we use modulo
dequeue()
meansf = (f + 1) % N
, where N is the total array size.enqueue()
meansr = (r + 1) % N
, where N is the total array size.
f | ||||
---|---|---|---|---|
5 | 10 | 15 | 2 | |
r | ||||
A[0] | A[1] | A[2] | A[3] | A[4] |
- Once again, if we
enqueue(1)
here:r = (r + 1) % N
- `r = ((4) + 1) % (5) = 0
- This shows that once we reach Q[N - 1], we go right back to Q[0].
C++ Implementation isn’t provided–but the powerpoint has the algorithm.
- Array-based queue implementation are extremely fast with O(1) time.
- As with the array-based stack implementation, the only real disadvantage of the array-based queue implementation is that we artificially set the capacity of the queue to be some number N.
- What do? Linked list-based queues. Particularly circularly linked list.
Implement Queue using a circularly linked list (5.2.5)
https://www.youtube.com/watch?v=A5_XdiK4J8A (this is singly)
Can’t use a singly linked list? Why?
- Singly linked list only provides efficient access to one side. Queue requires enqueue (rear access) and dequeue (front access).
Recall CircleList [[5.1 Doubly and Circular Linked#3.4 Circularly linked list]]
Recall CircleList supports the following:
The
cursor
itself is implemented to point to the back of the circulary linked list.
- It works out that the cursor in a queue points to therear
.
Therefore, in order to implement a queue:- the element referenced by back will be the
rear
of the queue - the element referenced by front will be the
front
- the element referenced by back will be the
back(): returns reference to the element the cursor points
front(): returns reference to the element AFTER the cursor
add(): inserts a new node AFTER the cursor
remove(): removes the node AFTER the cursor
Implementing enqueue()
and dequeue()
1 | void LinkedQueue::enqueue(const Elem& e) { |
C++ Implemention of Queue using Circularly Linked List
1 | typedef string Elem; |
- The entire implementation is just a mind exercise comparing a queue and a circular list.
- In the array-based implementation of a queue, what we did was: - we had three variables, two of which are cursors. - front (
f
), when wedequeue()
, we increment front and decrementn
- rear (r
), when weenqueue()
, we increment rear, and incrementn
. - Since in a circular linked list, front (
f
) and rear (r
) are implemented as one variable,cursor
.- The cursor points to the
rear
element. - And front
f
is simply the element immediately after the cursor because of the nature of a circular linked list.
- The cursor points to the
- We made use of the circular linked list’s multi-functionality to create a new type of data structure. In this case,
add()
,remove()
,advance()
, and evenfront()
1 |
|