程序代写代做代考 algorithm c++ data structure PowerPoint Presentation

PowerPoint Presentation

Stacks
Chapter 6
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Contents
The Abstract Data Type Stack
Simple Uses of a Stack
Using Stacks with Algebraic Expressions
Using a Stack to Search a Flight Map
The Relationship Between Stacks and Recursion

The Abstract Data Type Stack
Developing an ADT during the design of a solution
Consider entering keyboard text

Mistakes require use of backspace
abcddefgg
We seek a programming solution to read these keystrokes

The Abstract Data Type Stack
Pseudocode of first attempt

Requires

Add new item to ADT
Remove most recently added item
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Specifications for the ADT Stack
We have identified the following operations:

See whether stack is empty.
Add a new item to stack.
Remove from the stack item added most recently.
Get item that was added to stack most recently.
Stack uses LIFO principle

Last In First Out
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Specifications for the ADT Stack
FIGURE 6-1 A stack of cafeteria plates
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Abstract Data Type: Stack
A finite number of objects

Not necessarily distinct
Having the same data type
Ordered by when they were added
Operations

isEmpty()
push(newEntry)
pop()
peek()
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Abstract Data Type: Stack
View C++ Stack interface, Listing 6-1

FIGURE 6-2 UML diagram for the class Stack
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
.htm code listing files must be in the same folder as the .ppt files for these links to work

Axioms for the ADT Stack
new Stack()).isEmpty() = true
new Stack()).pop() = false
new Stack()).peek() = error
aStack.push(item)).isEmpty() = false
aStack.push(item)).peek() = item
aStack.push(item)).pop() = true

Simple Uses of a Stack

FIGURE 6-3 Traces of the algorithm that
checks for balanced braces
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Simple Uses of a Stack
Recognizing strings in a language
Consider
L = { s$s’ : s is a possibly empty string of characters other than $ , s’ = reverse( s )}
View algorithm to verify a string for a given language, Listing 6-A

Using Stacks with Algebraic Expressions
Evaluating postfix expressions

FIGURE 6-4 The effect of a postfix calculator on a stack when evaluating the expression 2 * (3 + 4)
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Using Stacks with Algebraic Expressions
Converting infix expressions to equivalent postfix expressions
Possible pseudocode solution

Using Stacks with Algebraic Expressions
FIGURE 6-5 A trace of the algorithm that converts the infix expression a – ( b + c * d ) / e to postfix form
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
View pseudocode algorithm that converts infix to postfix
Listing 6-B

Related Posts