Data Structures & Algorithms Lecture Notes

1 October 2009 • 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.

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.

  • Sequential access isn’t needed.

• 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 (or buffer).

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.

  • Canceling entries in the run or event queue.

Priority Queues

• Each element in a priority queue has an comparable value called its priority.

  • Usually priorities are assigned to elements by the queue client.

• A priority queue maintains elements 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.

New Operations

• Priority-manipulation operations.

  • Increase or decrease a queued element's priority.

• Non-head elements may be removed from the queue.

  • Past-due elements in a deadline-scheduled priority queue.

• These operations require non-navigable element 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.

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.