**CS C++ Lesson 42: Queues**

**OBJECTIVES:**
The student will use the apqueue class to solve problems.

Queues are another restricted access data structure, much like stacks.
A queue is like a one-way line where data enters the end of the line and
exits from the front of the line. The
*apqueue* class will support operations
similar to but different from stacks.

The key topics for this lesson are:

A. Queues

B. Operations on Queues

C. Implementing Queues as a Linked List

**VOCABULARY:**
QUEUE
ENQUEUE

DEQUEUE

**DISCUSSION:**
A. __Queues__

1. A queue is a linear data structure which simulates waiting in line. A queue has two ends, a front and a (rear) end.

2. Data must always enter the queue at the end and leave from the front of the line. This type of action can be summarized as FIFO (first-in, first-out).

3. All the data stored in a queue must be of the same type.

4. A queue is the appropriate data structure when simulating waiting in line. A printer which is part of a multi-user network must process print commands on a first-come, first-served basis. A queue would be used to store the jobs in a line.

B. __Operations
on Queues__

1. The
following operations are supported by the *apqueue*
class:

*apqueue*(); // default constructor

*apqueue* (**const** *apqueue* & *q*);
// copy constructor

*~apqueue* (); // destructor

Assignment

**const** *apqueue* & **operator**= (**const**
*apqueue* &*rhs*);

Accessors

**const** *itemType* & *front*() **const**;
// return front, no dequeue

**bool** *isEmpty*() **const**;
// return true if empty, else false

**int**
*length*() **const**; // return number of
elements in queue

Modifiers

**void** *enqueue* (**const** *itemType*
&*item*); //
insert item at rear

**void** *dequeue* ();
// remove first element

**void** *dequeue* (*itemType* & *item*);
// combine front and dequeue

**void** *makeEmpty* ();
// make queue empty

2. Using
the templated *apqueue* class is very
similar to using the *apstack* class.
Here is a sample program which uses some of the key operations provided
by the *apqueue* class.

Program 42-1

#include <iostream.h>

#include <apqueue.cpp>

*main*()

{

*apqueue* <**int**> *queue*;

**int** *k*;

**for** (*k*=1; *k*<=5;
*k*++)

*queue.enqueue*(*k*);

**while** (!*queue.isEmpty*())

{

*queue.dequeue*(*k*);

cout << *k* << "
";

}

**return** 0;

}

Run output:

1 2 3 4 5

3. See
Handout H.A.42.1, |

C. __Implementing
Queues as a Linked List__

1. A
queue can be implemented as a vector or a linked list.
The author of the *apqueue* class
chose to use an *apvector*.
If we use a linked list to implement a queue we must deal with the
following issues.

3. Data will be removed from the "front" of the queue. This operation is called dequeue.

4. A
queue can be implemented as a singly-linked list if the two external pointers
are appropriately placed.

5. When
a new piece of data is added to the tail of the queue (enqueue), the external
pointer *myEnd* must be moved to point
to the new node added to the list.

6. When
an old piece of data is extracted from the queue (dequeue), the external pointer
*myFront* must be advanced to the
appropriate node after the data has been removed. The **delete**
operation should be applied to the unwanted node of information.

**SUMMARY/REVIEW:**
Queues serve a very useful function whenever a program needs to simulate
waiting in line. One of the lab exercises will require queues to solve an
intriguing problem regarding binary trees.

**ASSIGNMENT:**
Lab Exercise L.A.42.1, *Printbylevel*