Programming Languages Chapter 18 Programming From Problem Analysis Program Design Eighth Edition Stacks And Queues

C++ Programming: From Problem Analysis to Program Design, Eighth Edition 18-1

license distributed with a certain product or service or otherwise on a password-protected website for classroom use.

Chapter 18

Stacks and Queues

A Guide to this Instructor’s Manual:

We have designed this Instructor’s Manual to supplement and enhance your teaching

experience through classroom activities and a cohesive chapter summary.

At a Glance

Instructor’s Manual Table of Contents

• Overview

• Objectives

• Teaching Tips

• Quick Quizzes

• Class Discussion Topics

• Additional Projects

• Additional Resources

• Key Terms

C++ Programming: From Problem Analysis to Program Design, Eighth Edition 18-2

Lecture Notes

Overview

Chapter 18 introduces students to two very useful data structures, stacks and queues.

Students will examine the various operations of stacks and queues. Then, they will learn

how to implement these structures as an array and as a linked list. Finally, students will

explore some of the numerous applications in which stacks and queues are used.

Objectives

In this chapter, the student will:

• Learn about stacks

• Examine various stack operations

• Learn how to implement a stack as an array

• Learn how to implement a stack as a linked list

• Learn about infix, prefix, and postfix expressions, and how to use a stack to evaluate

postfix expressions

• Learn how to use a stack to remove recursion

• Learn about queues

• Examine various queue operations

• Learn how to implement a queue as an array

• Learn how to implement a queue as a linked list

• Discover how to use queues to solve simulation problems

Teaching Tips

Stacks

Teaching

Tip

Review the stack rewinding of functions during exception propagation (Chapter

14) as an introduction to the stack data structure. Note that keeping track of

function calls is an important application of stacks.

1. Define the stack data structure. Mention that it is frequently used to convert recursive

algorithms into nonrecursive algorithms.

2. Explain the purpose of the element of a stack called the top.

C++ Programming: From Problem Analysis to Program Design, Eighth Edition 18-3

Teaching

Tip

Illustrate everyday stacks with the examples in Figure 18-1, and then ask

students to think of more examples in which the top element of a stack is always

the one the user would want to retrieve first.

4. Describe the push, pop, and top operations of a stack using Figures 18-2 and 18-3.

5. Explain why the isEmptyStack, isFullStack, and initializeStack

operations are necessary for a stack implementation.

Stack Operations

Teaching

Tip

Explain why the stack ADT is implemented as an abstract class.

Quick Quiz 1

1. What is a LIFO data structure?

2. The addition and deletion of elements in a stack only occur at one end, called the

____________________ of the stack.

3. True or False: A stack element can be accessed either at the top or the bottom of the

stack.

4. The ____________________ operation of a stack removes and stores the top element of

C++ Programming: From Problem Analysis to Program Design, Eighth Edition 18-4

Implementation of Stacks as Arrays

Teaching

Tip

Emphasize that the primary property of a stack is that an element can only be

accessed from the top. In other words, the client cannot access elements in any

other location of the stack.

2. Discuss the function of the variable stackTop. Use Figure 18-6 to illustrate.

Teaching

Tip

Verify that students understand the possible values of stackTop and how they

correspond to the array index.

Initialize Stack

1. Explain how this function initializes a stack using Figure 18-7 and the function

Empty Stack

1. Briefly examine the definition of the isEmptyStack function.

Full Stack

Push

1. Describe the two-step process to push an element onto a stack. Use Figures 18-8 and

2. Examine the definition of the push function.

Return the Top Element

1. Note the definition of the top function.

C++ Programming: From Problem Analysis to Program Design, Eighth Edition 18-5

Pop

1. Describe the process of popping an element off a stack using Figures 18-10 and 18-11.

2. Examine the definition of the pop function.

3. Discuss how to check for underflow in a stack.

Teaching

Tip

Remind students that the STL vector class uses stack terminology to insert and

remove elements at the end. Note, however, that it provides these operations for

both the top and bottom, and it also allows access to other elements.

Copy Stack

Constructor and Destructor

1. Describe how an array-based stack allocates and deallocates memory in the constructor

1. Note the definition of the copy constructor in an array-based stack.

Overloading the Assignment Operator (=)

1. Note the definition of the overloaded assignment operator in an array-based stack.

Teaching

Tip

Students may be pleasantly surprised by the simplicity of the stack

implementation. Explain that this is due to the fact that only the top element is

manipulated in most cases.

Stack Header File

1. Examine the header file for the array-based stack ADT.

2. Walk through the sample program in Example 18-1 to illustrate how an array-based

stack is used by a client program.

C++ Programming: From Problem Analysis to Program Design, Eighth Edition 18-6

Linked Implementation of Stacks

2. Explain how the use of the stackTop member variable differs in the linked

implementation of a stack.

Teaching

Tip

Ask your students if they can think of any advantages to using a stack as an array

rather than as a linked list.

3. Examine the definition of the linked stack ADT.

Default Constructor

1. Note the definition of the default constructor of the linked stack ADT.

Empty Stack and Full Stack

1. Briefly examine the definitions of the isEmptyStack and isFullStack functions.

Teaching

Tip

Note that in a linked stack implementation, the isFullStack function only

applies if computer memory runs out. Mention that this is a typical

implementation. Ask your students if they can think of another approach to

designing the class hierarchy that would not require the implementation of this

function in the linked stack class.

Initialize Stack

1. Examine the initializeStack function in the linked stack ADT and compare it to

Push

1. Illustrate the execution of the push function in a linked stack using Figures 18-13 and

18-14. Examine the definition of the push function.

C++ Programming: From Problem Analysis to Program Design, Eighth Edition 18-7

Teaching

Tip

Ask students to comment on the differences between this function and the insert

functions of the linked list classes. Note that this function does not provide an

assert statement for failure to allocate memory.

Return the Top Element

1. Note the straightforward definition of the top function in a linked stack.

Pop

1. Illustrate the execution of the pop function in a linked stack using Figures 18-15 and

18-16. Examine the definition of the pop function.

Copy Stack

Constructors and Destructors

Overloading the Assignment Operator (=)

1. Note the definition of the overloaded assignment operator of a linked stack ADT.

2. Remind students that this is a generic stack and that the definition and implementation

of the ADT will be placed in a header file.

Stack as Derived from the class unorderedLinkedList

1. Review the similarities between the operations of a linked implementation of a stack

and the analogous operations of a linked list.

C++ Programming: From Problem Analysis to Program Design, Eighth Edition 18-8

Teaching

Tip

Discuss whether this implementation violates the restrictions of a stack by

allowing access to the linked list operations of its base class,

unorderedLinkedList. Note that the stack ADT interface does not list the

underlying base class operations, but the base class is inherited as a public

class.

Application of Stacks: Postfix Expressions Calculator

1. Describe infix, prefix, and postfix notation.

Teaching

Tip

Ask students to convert a few postfix expressions into infix by hand before

discussing the stack application.

2. Discuss the importance of postfix notation in computer science applications.

3. Explain how postfix expressions can be evaluated using a stack with Figure 18-17.

Main Algorithm

Function evaluateExpression

1. Explain how this function evaluates an entire postfix expression.

2. Examine the pseudocode and the implementation of this function.

Teaching

Tip

This function has several parameters. Verify that students understand the purpose

of each one.

Function evaluateOpr

1. Describe how this function evaluates expressions using a stack.

2. Examine the pseudocode and the implementation of this function.

C++ Programming: From Problem Analysis to Program Design, Eighth Edition 18-9

Teaching

Tip

Step through the conditional statements in this function carefully to make sure

students understand the various evaluation paths.

Function discardExp

Function printResult

1. Explain how the result of a postfix expression is output.

2. Illustrate how to use these functions in the program listing in this section.

Teaching

Tip

Ask your students how this program might be implemented without a pound sign

preceding each number.

Quick Quiz 2

1. Which stack function is a private member of the class?

2. What is the position of the top element of a stack in an array-based implementation?

3. Removing an element from an empty stack results in ____________________.

4. True or False: In a linked implementation of a stack, the stack is only full if computer

memory runs out.

Removing Recursion: Nonrecursive Algorithm to Print a Linked List

Backward

1. Explain how a stack can be used to print a linked list backwards nonrecursively.

C++ Programming: From Problem Analysis to Program Design, Eighth Edition 18–10

Teaching

Tip

This section discusses the improvement in execution and processing time that

results from using a stack instead of recursion. What about the memory overhead

of recursive calls versus the memory overhead of an additional stack? Ask

students to share their opinions on this balance.

2. Walk through the steps involved in printing the linked list backward using Figures 18-

18 through 18-25.

Queues

2. Discuss the numerous applications of queues.

Queue Operations

1. Discuss the typical operations of a queue, noting that the two key operations are to add

an element to the rear of a queue and remove an element from the front of the queue.

2. Examine the definition of the abstract class queueADT.

Teaching

Tip

Ask students if they think LIFO or FIFO structures are used more in everyday

life.

Implementation of Queues as Arrays

1. Discuss the issues involved with using an array-based implementation of a queue.

2. Describe the various solutions to the problems of queue overflow to the rear, and

determining correctly whether a queue is empty or full. Use Figures 18-26 through 18-

34 to illustrate these issues.

Teaching

Tip

Make sure students understand why a circular array is typically used in array-

based queue implementations, and that they understand the formula for testing

whether a queue is empty or full when using a circular array.

3. Examine the class definition of an array-based queue ADT.

C++ Programming: From Problem Analysis to Program Design, Eighth Edition 18–11

4. Discuss the implementations of the array-based queue ADT, including the functions

isEmptyQueue, isFullQueue, initializeQueue, front, back,

Linked Implementation of Queues

1. Explain the advantages of using a linked rather than an array-based implementation of a

queue.

Teaching

Tip

Note that since the array-based implementation of queues has so many special

cases involving the front and rear, a linked list implementation is preferable in

most cases. Explain that the array version is shown here for completeness and to

illustrate queue concepts.

3. Step through the implementation of the class linkedQueueType in this section,

4. Illustrate how this class can be used by a client program using Example 18-5.

Queues Derived from the class unorderedLinkedListType

1. Explain how the linked implementation of a queue is similar to the linked list

Application of Queues: Simulation

Teaching

Tip

Ask your students to read this section before class so that they understand the

implementation issues discussed in class.

2. Explain what a queuing system is and how it is used to model everyday situations.

C++ Programming: From Problem Analysis to Program Design, Eighth Edition 18–12

Designing a Queuing System

1. Introduce the terms server, customer, and transaction time as they relate to a queuing

system.

3. Discuss time-driven simulations and how they can be implemented with a queuing

system.

Customer

1. Describe the purpose of the customerType class and its member functions.

2. Examine the class definition, UML class diagram in Figure 18-36, and the partial

Server

1. Describe the purpose of the serverType and its member functions.

2. Examine the class definition, UML class diagram in Figure 18-37, and the partial

Server List

1. Describe the purpose of the serverListType and its member functions.

Waiting Customers Queue

2. Examine the class definition, and the partial function definitions of the class

Main Program

1. Describe the simulation parameters that the main program needs to obtain in order to

run the simulation.

2. Discuss how to determine how many customers are arriving at a given time and how

C++ Programming: From Problem Analysis to Program Design, Eighth Edition 18–13

Teaching

Tip

Spend some time explaining the Poisson distribution for arrivals if students have

no prior exposure to this.

3. Describe the algorithm for the main loop in the simulation.

Quick Quiz 3

1. A(n) ____________________ is a system in which a queue of objects is waiting to be

served by various servers.

2. A(n) ____________________ array can be used in an array implementation of a queue

to avoid an overflow error at the rear of the queue when the queue is not full.

3. True or False: A queue is a First In First Out data structure.

Class Discussion Topics

1. Why do the linked stack and queue implementations not include iterators, as in the

linked list classes of Chapter 17? Are there cases in which a stack or queue might need

to be traversed privately, even if access cannot be provided publicly? If so, should an

iterator be used for these cases?

2. Introduce your students to the stack and queue containers in the C++ Standard Template

Library. You can find an overview of their functionality here:

Additional Projects

1. Write a private function for the stack that checks for duplicates. Use the derived version

of the stack class, so that you have the functions of the unorderedlinkedList at

2. Write a program that allows a user to see a recipe, one step at a time. A recipe class will

contain a queue to hold the steps of the recipe and a list to hold the ingredients. The

constructor creates the recipe from an input file. The test program will first print the

Additional Resources

2. An Introduction to Data Structures in C++: Queues:

Key Terms

➢ addQueue: an operation that adds a new element to the rear of the queue

➢ Back (rear): the location where elements are added to a queue; also a queue operation

(back)

➢ Customer: in a queuing system, refers to the object receiving the service

➢ deleteQueue: an operation that removes the front element from the queue

➢ destroyStack: an operation that removes all the elements from the stack, leaving

➢ push: adds a new element to the top of the stack

➢ Queue: a data structure in which the elements are added at one end, called the back or

rear, and deleted from the other end, called the front

➢ queueFront: a pointer to keep track of the front of the queue

➢ queueRear: a pointer to keep track of the rear of the queue

license distributed with a certain product or service or otherwise on a password-protected website for classroom use.