Queues Flashcards
Deque
A double-ended queued. elements can be added to or removed from either the front (head) or back (tail)
How to pronounce deque
“Deck”
List two possible subtypes of deque
An input-restricted deque is one where deletion can be made from both ends, but insertion can be made at one end only.
An output-restricted deque is one where insertion can be made at both ends, but deletion can be made from one end only.
Shift
Common name for removing first element from a deque
Unshift
Common operation name in most languages for inserting an element into the front of a deque
Two most common ways to efficiently implement a deque
Using an array deque or a doubly linked list
Circular buffering makes a good implementation strategy for what?
A queue with a fixed maximum length
The useful property of a circular buffer
is that it does not need to have its elements shuffled around when one is consumed in a FIFO manner. (If a non-circular buffer were used then it would be necessary to shift all elements left when one is consumed. (Because the buffer is contiguous memory and you need to keep space open at end of the buffer))
Describe how a circular buffer works
Fixed length buffer (represented by say a starting pointer and ending boundary pointer) then with two more logic pointers (or indices) representing the start and end of the logical portion (as opposed to physical portion) of the queue. On every insert move the end logical pointer one forward and put element there ( if at end of buffer, loop around to the starting boundary pointer pointer). On remove operations, just return the value at the starting logical pointer (thus performing FIFO logic) and then increment the starting logical pointer one slot)
When may you not want to use a circular buffer for a queue? And what implementation may you want for a queue instead?
For arbitrarily expanding queues, because reallocating new memory for a larger buffer and copying over the data will take O(n) time.
Instead use a linked list implementation
Double buffer analogy
One buffer = one bucket you fill in sink, turn sink off, walk outside to kiddie pool, fill up kiddie pool with bucket , walk back and fill up bucket again
Two buffer = two buckets. Filling on in sink while emptying one in pool
Three buffer = 3 buckets. One sink one in transport one filling pool
List the 3 common implementation of array deques
Storing deque contents in a circular buffer, and only resizing when the buffer becomes full. This decreases the frequency of resizings.
Allocating deque contents from the center of the underlying array, and resizing the underlying array when either end is reached. This approach may require more frequent resizings and waste more space, particularly when elements are only inserted at one end.
Storing contents in multiple smaller arrays, allocating additional arrays at the beginning or end as needed. Indexing is implemented by keeping a dynamic array containing pointers to each of the smaller arrays.
When would it be a really good idea to implement a deque using a circular buffer as opposed to a dynamic array strategy?
When insertions don’t outpace removals that often, such that queue length rarely exceeds the buffer size. When it does you’ll just have to create a new larger buffer which after copying values will still result in amortized constant time, though occasional one op linear time
ArrayDeque
A Java Implementation of a deque, using an array and two pointers
