D a t a s t r u c t u r e s a n d a L g o r I t h m s Annotated Reference with Examples

§2.1). A singly linked list provides O(1)
insertion and deletion run time complexities. The reason we have an O(1) run
time complexity for deletion is because we only ever remove items from the front
of queues (with the Dequeue operation). Since we always have a pointer to the
item at the head of a singly linked list, removal is simply a case of returning
the value of the old head node, and then modifying the head pointer to be the
next node of the old head node. The run time complexity for searching a queue
remains the same as that of a singly linked list: O(n).
6.2
Priority Queue
Unlike a standard queue where items are ordered in terms of who arrived first,
a priority queue determines the order of its items by using a form of custom
comparer to see which item has the highest priority. Other than the items in a
priority queue being ordered by priority it remains the same as a normal queue:
you can only access the item at the front of the queue.
A sensible implementation of a priority queue is to use a heap data structure
(defined in §4). Using a heap we can look at the first item in the queue by simply
returning the item at index 0 within the heap array. A heap provides us with the
ability to construct a priority queue where the items with the highest priority
are either those with the smallest value, or those with the largest.
6.3
Double Ended Queue
Unlike the queues we have talked about previously in this chapter a double
ended queue allows you to access the items at both the front, and back of the
queue. A double ended queue is commonly known as a deque which is the name
we will here on in refer to it as.
A deque applies no prioritization strategy to its items like a priority queue
does, items are added in order to either the front of back of the deque. The
former properties of the deque are denoted by the programmer utilising the data
structures exposed interface.

---

CHAPTER 6. QUEUES
50
Figure 6.1: Queue mutations

---

CHAPTER 6. QUEUES
51
Deque’s provide front and back specific versions of common queue operations,
e.g. you may want to enqueue an item to the front of the queue rather than
the back in which case you would use a method with a name along the lines
of EnqueueFront. The following list identifies operations that are commonly
supported by deque’s:
•
EnqueueFront
•
EnqueueBack
•
DequeueFront
•
DequeueBack
•
PeekFront
•
PeekBack
Figure 6.2 shows a deque after the invocation of the following methods (in-
order):
1.
EnqueueBack(12)
2.
EnqueueFront(1)
3.
EnqueueBack(23)
4.
EnqueueFront(908)
5.
DequeueFront()
6.
DequeueBack()
The operations have a one-to-one translation in terms of behaviour with
those of a normal queue, or priority queue. In some cases the set of algorithms
that add an item to the back of the deque may be named as they are with
normal queues, e.g. EnqueueBack may simply be called Enqueue an so on. Some
frameworks also specify explicit behaviour’s that data structures must adhere to.
This is certainly the case in .NET where most collections implement an interface
which requires the data structure to expose a standard Add method. In such
a scenario you can safely assume that the Add method will simply enqueue an
item to the back of the deque.
With respect to algorithmic run time complexities a deque is the same as
a normal queue. That is enqueueing an item to the back of a the queue is