Advanced Programming I Lecture Notes

23 February 2006 • 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:

  1. Which end?

  2. 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.

Properties

• The desirable data-structure properties are:

  • Unrestricted element capacity.

  • Add at one end, remove at the other end.

  • Only end elements can be referenced.

• The resulting data structure is called a queue.

Element Ordering

• Queue access restrictions impose an order on queued elements..

  • Elements added earlier come before elements more recently.

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

  • Added in 1, 2, 3 order.

  • Removed in 1, 2, 3 order.

The ADT

• Create and delete maintenance operations.

• Add and remove manipulation operations.

  • "Add" is traditionally called enqueue.

    • Enqueue applies to the queue head.

  • "Remove" is traditionally called dequeue.

    • Enqueue applies to the queue tail.

• Element references are unnecessary.

Adding and Removing Elements

• Enqueue and dequeue locations are implicit.

• The before or after question for enqueuing is irrelevant.

• Enqueuing in an empty queue is simple.

Query Operations

• The usual operations: size, empty, ...

  • Query operations may access non-end elements.

• Access the head element.

  • No element references required.

• No traversal or navigation operations.

Queue ADT Implementations

• Queue ADTs can be array-based or based on dynamic storage.

• There are others.

List Representation

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

  

Array Representation

• An array-based queue implementation eliminates list overhead.

  • At a cost of fixed element capacity.

• Two variables keep track of head and tail indices.

  

Element Shifting

• Enqueuing an element may run into an array end.

  • Requiring that elements be shifted.

• Connecting the array ends eliminates the shift

  This is a circular array.

Circular-Array Indexing

• Circular-array indexing uses modulo arithmetic.

  • head = (head + 1) % n

  • Similarly for tail.

• Distinguishing between empty and full queues requires some thought.

  • Keeping track of element count is easiest.

Queue Comparison

	List	Queue	Queue	Queue
		(Array)	(List)	(DArray)
create	O(1)	O(1)	O(1)	O(1)
delete	O(1)	O(1)	O(1)	O(1)
add	O(n)	O(1)	O(1)	O(1)*
remove	O(n)	O(1)	O(1)	O(1)*
traversal	O(1)	na	na	na
navigation	O(1)	na	na	na
dynamic	No	No	Yes	Yes

* Amortized.

Dequeues

• Another answer to the questions "Which end?" and "What access?" is
  Add or remove 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 elements inside the queue.

  • The priority queue, for example.

  • A priority queue messes with fifo order too.

• Some queue uses require access to internal elements.

  • Cancelling entries in the run or event queue.