Data Structures & Algorithms Lecture Notes

20 November 2008 • 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 tail.

  • “Remove” is traditionally called dequeue.

    • Dequeue applies to the queue head.

• Element references are unnecessary.

Adding and Removing Elements

• Enqueue and dequeue locations are implicit.

  • No references needed.

• The before or after question 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 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 element capacity.

• Two variables keep the head and tail indices.

  

• The elements move through the array.

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

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

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.