## Queues

 home  Bib  Algorithms  Bioinfo  FP  Logic  MML  Prog.Lang and the  mmlist

Algorithms
glossary
 NB. Do not confuse the priority queue with the ordinary queue (here). The priority queue is, for example, used in Heap sort.

The queue is an abstract data type that obeys a First In First Out (FIFO) rule. It is used where elements are processed in the order in which they arrive. As such it finds many uses in computer operating systems - for example the process queue, the print queue.

```
type queue = empty_queue | addq Element_Type × queue

Operations:
front :queue -> Element_Type
addq  :Element_Type × queue -> queue
popq  :queue -> queue
empty :queue -> boolean

Rules:
front(addq(e, q)) = front(q),    if q not empty
front(empty_queue) = error

popq(empty_queue) = error

empty(empty_queue) = true

The Queue Abstract Data Type.

```
These operations are free of side-effects.

If queues do not share elements, procedures may be written to manipulate them as side-effects, much as for stacks. Frequently front and popq are combined in one procedure which returns the front elements and removes it from the queue.

### Example: Breadth-First Traversal of a Tree

A queue is used in the algorithm to traverse a tree in breadth-first order. This is given in the chapter on binary trees.

### Queue by Array

A queue can be implemented by an array of elements. Two integers point to the first and last elements respectively. Pointer arithmetic is done modulo the maximum size. For this reason it is more convenient if the array index runs from zero to the maximum size minus one.
 L.Allison

```
0   1   2   3   4   5   6=m-1
-   -   a   b   c   -   -
^       ^
|       |
|       last
first

Queue.

```
```
0   1   2   3   4   5   6=m-1
f   g   -   -   -   d   e
^               ^
|               |
last            first

Queue, some time later.

```
Alternatively, one integer can point to the first element and another can keep a count of the number of elements currently in the queue.

This implementation places a limit on the number of elements and is often called a bounded queue.

### Queue by Circular List

There are various ways of implementing a queue by a list. Since front and addq require fast access to opposite ends of the list, a pointer can be kept to each end of the list. A neat variation is to use a circular list where the queue variable points to the last element:

```
q----------->------------|
|
|
v
1----->2----->3----->.....----->n-->--|
^                                     |
|                                     |
|                                     |
|                                     |
|--------<-----------------------------

```
Both the last element, where new things are added, and the first element, where things are removed, can be accessed quickly from q. The empty queue is represented by the nil pointer.
```
[C/Queue/Queue.h]
[C/Queue/Ops.c]

```

### Exercises

1. In an Object oriented Language: Implement a class which exports the standard queue operations and which privately implements the queue by an array.
2. Give an implementation of a queue using a linear list and pointers to the first and last elements.

© L. Allison, Department of Computer Science, U.W.A. 1984-86
window on the wide world:
 The Darwin Awards V: Next Evolution

 Linux  Ubuntu free op. sys. OpenOffice free office suite, ver 3.4+ The GIMP ~ free photoshop Firefox web browser FlashBlock like it says!

 © L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated), Faculty of Information Technology (Clayton), Monash University, Australia 3800 (6/'05 was School of Computer Science and Software Engineering, Fac. Info. Tech., Monash University, was Department of Computer Science, Fac. Comp. & Info. Tech., '89 was Department of Computer Science, Fac. Sci., '68-'71 was Department of Information Science, Fac. Sci.) Created with "vi (Linux + Solaris)",  charset=iso-8859-1,  fetched Thursday, 29-Oct-2020 05:11:27 AEDT.