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.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- instant campaign builder dungeon mastering
- player s guide
- marvel superheroes rpg character generator
- unearthed arcana quick characters
- chapter 3 pseudo random numbers generators
- chapter 7 queues edu
- department of the army letterhead
- rhmap statistical package for
- simlink a program for estimating the power of a
- winclada george washington university