Chapter 7 Queues .edu



Chapter 7 Queues

7.1 Queue Abstract Data Type

7.2 Queue Applications

7.3 Implementing QueueADT

7.4 Simulating Waiting Lines Using Queues

7.5 Priority Queues

7.6 Common Programming Errors

Chapter Review

The queue is a data structure that has one important difference from a stack. A stack is called a LIFO list (Last-In-First-Out) in that the last element pushed onto a stack will be the first element popped off. A queue, on the other hand, is a FIFO list (First-In-First-Out) in that the first element inserted in the queue will be the first element removed. The easiest way to visualize a queue is to think of a line of customers waiting to purchase theater tickets or see a bank teller (see Figure 7.1). Usually the next person to be served is the one who has been waiting the longest and late-comers are added to the end of the line. (The British people "queue up" instead of waiting in lines.)

Figure 7.1 Customers Waiting in a Line or Queue

_____________________________________________________________

______________________________________________________________

In computer science, queues are used in operating systems for a timeshared computer to keep track of tasks waiting for the processor. If all tasks have the same priority, the one that receives the processor is the one that has been waiting the longest. Queues are also used by operating systems to keep track of the list of jobs waiting to be printed.

We will describe the queue as an abstract data type and show how to use a queue to represent a list of airline passengers waiting to see a ticket agent. We will also implement an abstract data type for a queue. We will illustrate how to use a process called simulation to determine the amount of time customers spend waiting in queues. Lastly, we will introduce a variation on the queue known as a priority queue.

7.1 Queue Abstract Data Type

A queue differs from a stack in that new elements are inserted at one end (the rear of the queue) and elements already in the queue are removed from the other end (the front of the queue). In this way the element that has been waiting longest is removed first. In contrast, stack elements are inserted and removed from the same end (the top of the stack).

A queue of three passengers waiting to see an airline ticket agent is shown in Figure 6.2. The name of the passenger who has been waiting the longest is 'McMann' (pointed to by Front); the name of the most recent arrival is 'Carson' (pointed to by Rear). Passenger 'McMann' will be the first one removed from the queue when an agent becomes available, and pointer Front will be moved to passenger 'Watson'. Any new passengers will follow passenger 'Carson' in the queue, and pointer Rear will be adjusted accordingly.

Figure 7.2 A Passenger Queue

_____________________________________

ÚÄÄÄÄÄÄÄÄÄÄ¿

Front ---> ³McMann ³

³Economy ³

³2 ³

ÃÄÄÄÄÄÄÄÄÄÄ´

³Watson ³

³Business ³

³1 ³

ÃÄÄÄÄÄÄÄÄÄÄ´

Rear ---> ³Carson ³

³FirstClass³

³2 ³

ÀÄÄÄÄÄÄÄÄÄÄÙ

_____________________________________

Table 7.1 gives the specification for the abstract data type Queue. You may wish to compare it with the earlier specification for an abstract stack.

Table 7.1 Specification of Abstract Data Type Queue

--------------------------------------------------------------

Elements

A queue consists of a collection of elements that are all the same data type.

Structure

The elements of a queue are ordered according to time of arrival. The only element which may be removed or examined at any given time is the element that entered the queue first and has been in the queue the longest. Elements are removed from the front of the queue and inserted at the rear of the queue.

Operators

In the descriptions below we will assume the following parameters:

El (pronounced el) has the same data type as the queue

elements

Success is type Boolean and indicates whether the

operation succeeds.

Queue.Queue(): Creates an empty queue.

Queue.Insert(El, &Success): If the queue is not full, the value in El is inserted at the rear of the queue and Success is set to True. Otherwise, the queue is not changed and Success is set to False.

Queue.Remove(&X, &Success): If the queue is not empty, the element at the front of the queue is removed and copied to El, and Success is set to True. If the queue is empty, El is not changed and Success is set to False.

Queue.Retrieve(&El, &Success): If the queue is not empty, the element at the front of the queue is copied into El, and Success is set to True. If the queue is empty, El is not defined and Success is set to False. In either case, the queue is not changed.

Queue.IsEmpty(): Returns True if the queue is empty; otherwise, returns False.

Queue.IsFull(): Returns True if the queue is full; otherwise, returns False.

Queue.SizeOfQueue(): Returns the number of elements in the queue.

---------------------------------------------------------------

We will implement a Queue class in Section 7.3. We will illustrate how to use a queue next. Just as we did for stacks, we will assume that the identifier QElement represents the type of each queue element. Each client program must import the type definitions for QElement and Queue from the header file queue.h before trying to use them.

Exercises for Section 7.1

Self-check

1. Draw the queue in Figure 2.2 after the insertion of firstclass

passenger Harris (3 seats reserved) and the removal of one

passenger from the queue. Which passenger is removed? How

many passengers are left?

7.2 Queue Applications

Our application will be to write a program that processes a queue of airline passengers.

Case Study: Maintaining a Queue of Passengers

Problem

Write a menu-driven program that maintains a queue of passengers waiting to see a ticket agent. The program user should be able to insert a new passenger at the rear of the queue, display the passenger at the front of the queue, or remove the passenger at the front of the queue. The program will display the number of passengers left in the queue just before it terminates.

Design Overview

We can use the Queue abstract data type and operators Insert, Retrieve, and Remove to process the queue. We can simplify the program by using another abstract data type, Passenger, that contains type declarations for an airline passenger and provides its input/output operators (ReadPass and WritePass). We will implement this abstract data type as a class later.

Data Requirements

Problem Inputs

The operation to be performed (char Choice)

The next passenger's data (Passenger NextPass)

Problem Outputs

The passenger at the front of the queue (Passenger FirstPass)

Program Variables

The queue of passengers (Queue PassQueue)

A flag for storing the result of a queue operation (int Success)

Algorithm

1. Initialize the queue.

2. repeat

3. Display the menu.

4. Read the operation selected.

5. Perform the operation selected.

until user is done or a queue operation fails.

6. Display the number of passengers left in the queue.

Coding

Main Program

The main program (see Figure 7.3) imports the type definitions for QElement and for Queue from the header file queue.h. Method Queue::Queue() initializes the passenger queue to an empty queue. In the main program body, the statement

cout > Choice;

Choice = toupper(Choice);

//Process current request

ModifyQueue(PassQueue, Choice, Success);

cout E

Number of seats > 3

Enter I(nsert), R(emove), D(isplay), or Q(uit) > R

Passenger removed from queue was:

Name: Brown

Economy Class

2 Seats

Enter I(nsert), R(emove), D(isplay), or Q(uit) > D

Passenger at head of queue is:

Name: Watson

Business Class

1 Seat

Enter I(nsert), R(emove), D(isplay), or Q(uit) > Q

Leaving passenger queue.

Number of passengers in queue is 2

________________________________________________________________

Coding the Abstract Data Type Passenger

Figure 7.6 shows the header file passenger.h that contains the declaration for the Passenger class. The Passenger will be used as the base class when we implement QElement a subclass in the next section.

Figure 7.6 Header file passenger.h

________________________________________________________________

#include

#include

//Header file for passenger class

const StrLen = 10;

enum ClassType{FirstClass, Business, Economy,

Standby, Undesignated};

class Passenger

{

protected:

char Name[StrLen];

ClassType Class;

int NumSeats;

public:

Passenger();

void ReadPass();

void WritePass();

};

________________________________________________________________

Figure 7.7 shows the implementation file passenger.cpp that contains the implementations of methods ReadPass and WritePass which read and write a single passenger's record. The completion of WritePass is left as an exercise.

Figure 7.7 Implementation file passenger.cpp

________________________________________________________________

#include "passenger.h"

ClassType ClassConvert(char ClassCh)

//Converts character to passenger category

{

//stub function

return Economy;

}

Passenger::Passenger()

//Default constructor

{

strcpy(Name, "");

}

void Passenger::ReadPass()

//Reads values into passenger's data members

//Pre : None

//Post: Data read into all data members for one passenger.

{

char ClassCh; //input - character for class type

cout > Name;

cout > ClassCh;

Class = ClassConvert(ClassCh);

cout > NumSeats;

}

void Passenger::WritePass()

//Displays the data members for one passenger

{

//stub function

cout ServeTime;

cout > TotalTime;

cout ShowAll;

cout = 0

//Post: AveFFWait and AveRPWait are defined and displayed.

{

float AveRPWait;

float AveFFWait;

if (NumRPServed > 0)

AveRPWait = (float) RPWait / NumRPServed;

else

AveRPWait = 0.0;

cout ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download