Unlock document.
This document is partially blurred.
Unlock all pages and 1 million more documents.
Get Access
C++ Programming: From Problem Analysis to Program Design, Eighth Edition 18-1
© 2018 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a
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
© 2018 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website for classroom use.
