Data Structures and Algorithms Lecture Notes

14 February 2011 • Queues

Outline

Motivation
Queue properties.
The queue data structures.
Queue 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 queue 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 Queue Data Structure

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

parts of

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) ordering

queue (FIFO) ordering

Stack (LIFO) order

Queue (fifo) order

Queue Implementations

Queues 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 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?

One-Way Queue Example

A one-way queue isn't too useful. How can it be fixed to provide a more useful queue?
- What's wrong with a one-way queue?

Index Resetting

A one-way queue eventually runs out of indices to use.

When the queue is empty, recover lost indices by resetting the head and tail.

Making it a two-way queue.

the value in resetting indexes

Resetting-Index Queue Example

That's better, but are there any other improvements to make?
- What problems are left?

Value Shifting

If the queue never empties, head and tail are never reset.
Don't wait until the queue's empty to reset the head and tail.
- If a value block hits an array end, move it to the other end.

Value-Shifting Example

Are we done yet? Is there anything else to consider?

Put Them All Together

Resetting Shifting Example

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; }
```

Circular Queue Example

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 a comparable value called its priority.
- Usually priorities are assigned to values by the queue client.
A priority queue orders values 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 implementations.
The highly useful priority queue generalizes queues by redefining queue order.

References

Stacks and Queues, Chapter 16 in Data Structures & Problem Solving Using Java, fourth edition, by Mark Weiss, Addison Wesley, 2010.
Stacks, Queues, and Deques, Chapter 5 in Data Structures & Algorithms in Java, fifth edition, by Michael Goodrich and Roberto Tamassia, Wiley, 2010.

This page last modified on 2011 February 9.