Queues
From
| Line 1: | Line 1: | ||
A queue is another basic data structure that is normally homogeneous data. It is similar to a<br>stack except it operates using a FIFO (First In, First Out) ordering. A queue is another way<br>of expressing a line. The standard operations on a queue are enqueue(), dequeue(),<br>peek(), and isEmpty(). | A queue is another basic data structure that is normally homogeneous data. It is similar to a<br>stack except it operates using a FIFO (First In, First Out) ordering. A queue is another way<br>of expressing a line. The standard operations on a queue are enqueue(), dequeue(),<br>peek(), and isEmpty(). | ||
| - | + | <br> | |
Similar to a stack, a queue can be implemented either by an array or a linked list. When<br>implemented using an array, it is normally implemented as a circular list (circular array).<br>Items are added at the rear and removed from the front—in the same manner as a list. And,<br>just like a list, we need an isFull() operation when using an array. | Similar to a stack, a queue can be implemented either by an array or a linked list. When<br>implemented using an array, it is normally implemented as a circular list (circular array).<br>Items are added at the rear and removed from the front—in the same manner as a list. And,<br>just like a list, we need an isFull() operation when using an array. | ||
| Line 7: | Line 7: | ||
<br>When using a linked list, items are added to the rear and removed from the front, so we need<br>both front and rear pointers. Also note that similar to a stack, the operations on a queue are<br>constant. | <br>When using a linked list, items are added to the rear and removed from the front, so we need<br>both front and rear pointers. Also note that similar to a stack, the operations on a queue are<br>constant. | ||
| - | + | ==Deque== | |
| + | A deque is a double-ended queue. This means that we can add or remove items from either<br>end. The operations we need are addToFront(), addToBack(), removeFront(),<br>removeBack(), peekFront(), peekBack(), isFull(), isEmpty(). | ||
| - | + | ==Priority Queue== | |
| + | A priority queue is a standard queue, but the elements have a priority. When an item is<br>entered into the queue, it moves up in the queue until it encounters an item of equal or greater<br>priority. This is its position in the queue. | ||
<br>When implementing a priority queue, it is often implemented as a linked list. If I am adding<br>items to the back of the list, and removing items from the head of the list, a priority queue is<br>best implemented as a doubly linked list. In this case, we would do the following. | <br>When implementing a priority queue, it is often implemented as a linked list. If I am adding<br>items to the back of the list, and removing items from the head of the list, a priority queue is<br>best implemented as a doubly linked list. In this case, we would do the following. | ||
Revision as of 20:10, 26 March 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.
