Data Structures & Algorithms Lecture Notes

11 February 2010 • Queues

---

Outline

• Motivation
• Queue properties.
• The queue ADT.
• ADT implementations
• Extension and details.

Restricted Lists

• Restricting list access to the ends exploits a strength.
  • Trading-off general access for more efficient implementation and operation.
• Restricting access to one end results in a stack.
• What happens when either end is accessible?

  

Possibilities

• The possibilities for dual-end access restrictions are outlined in two questions:

  Which end? What access?

• Two of the answers seem most reasonable:
  1. Add only at one end, remove only at the other.
  2. Add and remove at either end.
• Consider choice 1 for the moment.

Properties

• The desirable ADT properties are:
  • Unrestricted value capacity.
  • Add at one end, remove at the other end.
  • Only end values can be referenced.
  • Sequential access isn’t needed.
• The resulting data structure is called a queue.

  

The ADT

• Create and delete maintenance operations.
• Add and remove manipulation operations.
  • “Add” is traditionally called enqueue.
    • Enqueue applies to the queue tail.
  • “Remove” is traditionally called dequeue.
    • Dequeue applies to the queue head.
• Value references are unnecessary.

Adding and Removing Values

• Enqueue and dequeue locations are implicit.
  • No references needed.

  class Queue<T> {
    T deque() { ... }
    void enque(T v) { ... }
    }

• The before or after question is irrelevant.
• Enqueuing in an empty queue is simple.

Queue Error States

• Trying to dequeue a value from an empty queue results in a queue underflow.
  • Queue underflows are always a possibility.
• Trying to enqueue a value into a full queue results in a queue overflow.
  • Queue overflows may not occur if there’s no such thing as a full queue.

Query Operations

• The usual operations: size, empty, ...
  • Query operations may access non-end values.
• Access the head value.
  • No value references required.
• No traversal or navigation operations.
• However, some common queue clients require value reference and navigation operations.

Queue Ordering

• Queue access restrictions impose an order on queued values.
  • Values added earlier come before values added later.

  This order is known as first in first out (or FIFO) order.

Stack v Queue Ordering

Stack (LIFO) order		Queue (fifo) order

Queue ADT Implementations

• Queue ADTs can be implemented with arrays or dynamic storage.
• Dynamic-storage implementations can be direct or based on other dynamic data structures.
  • Using a linked list to implement a queue, at higher overhead.
• There are other implementation techniques.
  • Adapting an existing data structure as a queue, for example.

List Representation

• A list-based queue ADT includes variables for the head and tail references.

  

• Singly-linked lists have minimal overhead.

Array Representation

• An array-based queue implementation eliminates list overhead.
  • At a cost of fixed value capacity.
• Two variables keep the head and tail indices.

  

Shifting Values

• As values are added and removed from an array-implemented queue, the value block shifts in the array.

  

• What happens when the value block hits an array end?

Value Shifting

• If a value block hits an array end, move it to the other end.

  

• But now enqueuing values is lumpy in the amount of work required.
• How can always fast value enqueuing be recovered?

Circular Buffering

• Connecting the array ends together eliminates the shift

  This is a circular array (or buffer).

• A circular buffer may overflow if full, or just overwrite old values.
  • Or create a larger array.

Circular-Array Indexing

• Circular-array indexing uses modulo arithmetic.
  • head = (head + 1) % n
  • tail = (tail + 1) % n
• Distinguishing between empty and full queues requires some thought.
  • Keeping track of value count is easiest.

  bool isEmpty() { return size == 0; }
  

Dynamic-Array Queues

• Queues can be implemented with dynamic arrays, adjusting the array size as needed.
  • Eliminating queue overflows.
  • Value-block shifting still goes on for non-full arrays.
  • Circular buffers eliminate the value-block shifting.

Queue Comparison

	List	Queue	Queue	Queue
		(CBuffer)	(List)	(DArray)
create	fast	fast	fast	fast
delete	fast	fast	fast	fast
add	slow	fast	fast	fast*
remove	slow	fast	fast	fast*
traversal	fast	na	na	na
navigation	fast	na	na	na
dynamic	no	no	yes	yes

* Most of the time.

Dequeues

• Another answer to the questions “Which end?” and “What access?” is

  Values added or removed at either end.

  

• Such a data structure is called a dequeue (double-ended queue).
  • Pronounced “deck”.

Non-End Access

• Some queue variations require access to values inside the queue.
  • The priority queue, for example.
  • A priority queue messes with fifo order too.
• Some queue uses require access to internal values.
  • Canceling entries in the run or event queue.

Priority Queues

• Each value in a priority queue has an comparable value called its priority.
  • Usually priorities are assigned to values by the queue client.
• A priority queue maintains values in order by priority.
  • The fifo property is mostly ignored.

  

Priority-Queue Operations

• Priority-queue operations mostly follow queue operations.
  • create() may have a priority comparator argument.
  • enqueue() and dequeue() may have a priority argument.
    • If not, then assign a default priority.
• Dequeuing removes the highest priority value.

New Operations

• Priority-manipulation operations.
  • Increase or decrease a queued value's priority.
• Non-head values may be removed from the queue.
  • Past-due values in a deadline-scheduled priority queue.
• These operations require non-navigable value references.

Priority-Queue Implementation

• A priority queue can be implemented with an array or a linked-list.
  • Linked lists are expensive to search but cheap to change.
  • Arrays are cheap to search but expensive to change.
• An alternative priority-queue implementation is cheaper than both arrays and linked-lists to search and change.
  • But later for that.

Summary

• Queues allow restricted access to both ends of a linked list.
  • Trading off efficiency for generality.
• Different types of access at different ends leads to different queue ADTs.
• The highly useful priority queue generalizes queues by redefining queue order.

---

This page last modified on 11 February 2010.