Queues
From
m (Protected "Queues" ([edit=autoconfirmed] (indefinite) [move=autoconfirmed] (indefinite))) |
(→Priority Queue) |
||
| Line 78: | Line 78: | ||
</pre> | </pre> | ||
<br/><br/> | <br/><br/> | ||
| + | ---- | ||
| + | {{CS2/ChapNav}} | ||
| + | ---- | ||
| + | [[Category:CS2|{{SUBPAGENAME}}]] | ||
Revision as of 17:00, 9 April 2009
A queue is another basic data structure that is normally homogeneous data. It is similar to a stack except it operates using a FIFO (First In, First Out) ordering. A queue is another way of expressing a line. The standard operations on a queue are enqueue(), dequeue(), peek(), and isEmpty().
Similar to a stack, a queue can be implemented either by an array or a linked list. When implemented using an array, it is normally implemented as a circular list (circular array). Items are added at the rear and removed from the front—in the same manner as a list. And, just like a list, we need an isFull() operation when using an array.
When using a linked list, items are added to the rear and removed from the front, so we need both front and rear pointers. Also note that similar to a stack, the operations on a queue are constant.
Deque
A deque is a double-ended queue. This means that we can add or remove items from either end. The operations we need are addToFront(), addToBack(), removeFront(), removeBack(), peekFront(), peekBack(), isFull(), isEmpty().
Priority Queue
A priority queue is a standard queue, but the elements have a priority. When an item is entered into the queue, it moves up in the queue until it encounters an item of equal or greater priority. This is its position in the queue.
When implementing a priority queue, it is often implemented as a linked list. If I am adding items to the back of the list, and removing items from the head of the list, a priority queue is best implemented as a doubly linked list. In this case, we would do the following.
Adding an item to a priority queue that is a doubly linked list:
Let Temp be a node pointer that points to a new list node. Assume a list node has a field called priority.
If Rear is null, the list is empty. So, set Front and Rear of the head node to the value of Temp.
If Rear is not null, there is at least one node in the list.
If Temp.priority <= Rear.priority, then add Temp to the end of the list
Set Rear.next to Temp.
Set Temp.previous to Rear
Set Rear to Temp
Else
let P be a node pointer
let P = Rear
EndIf
While P is not null and Temp.priority > P.priority
Let P = P.previous
If P is not null, then P has stopped at a node whose priority is greater or equal to that of
Temp. Temp is to be inserted after the node pointed to by P.
Let Temp.previous = P
Let Temp.next = P.next
Let P.next.previous = Temp
Let P.next = Temp
If P is null, then the node pointed to by Temp goes at the head of the list.
Let Front.previous = Temp
Let Temp.next = Front
Let Front = Temp
When using a singly linked list, it becomes a little more difficult:
If Front is null, the list is empty, so
Let Front = Temp
If Front is not null, the list has at least one node in it
If Temp.priority > Front.priority, then Temp goes in the front of the list
Set Temp.next to Front
Set Front to Temp.
Set Rear to Temp.
Else
let P = Front
While P.next is not null and P.next.priority >= Temp.priority
Let P = P.next
EndWhile
If P.next is null, then Temp goes at the end of the list
Set P.next to Temp
Set Rear to Temp
Else
Temp goes after the node pointed to by P
Set Temp.next to P.
EndElse
EndElse
EndIf
CS2: Data Structures
Theory of Computation - ADT Preliminaries
Linear ADTs - Tree ADTs - Graph ADTs - Unordered Collection ADTs
