Transcript Data Abstraction and Problem Solving with JAVA

Data Abstraction and Problem Solving with JAVA Walls and Mirrors
Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Stacks
Data Abstraction and Problem Solving with JAVA:
Walls and Mirrors
Carrano / Prichard
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
ADT Stack Operations
•
•
•
•
Create an empty stack.
Determine whether a stack is empty.
Add a new item to the stack.
Remove from the stack the item that
was added most recently.
• Remove all the items from the stack.
• Retrieve from the stack the item that
was added most recently.
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 6.1
Stack of cafeteria dishes
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
ADT Stack Operations
• LIFO (Last-In, First-Out) - Stack
• FIFO (First-In, First-Out) - Queue
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Pseudocode for the ADT Stack Operations
createStack()
// Creates an empty stack
isEmpty()
// Determines whether a stack is empty
push(newItem) throws StackException
// Adds newItem to the top of the stacks. Throws StackException if failed.
pop() throws StackException
// Retrieves and then removes the top of the stack. Throws StackException if
not successful.
popAll()
// Removes all items from the stack
peek() throws StackException
//Retrieves the top of the stack. Retrieval does not change the stack. Throws
Stack Exception if failed.
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Using the ADT stack in a solution
displayBackward(stack)
// Displays the input line in reversed order by writing the contents of
stack
// Writing the contents of stack.
stack = readAndCorrect()
while (!stack.isEmpty()) {
newChar = stack.pop()
Write newChar
} // end while
Advance to new line
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Using the ADT stack in a solution
readAndCorrect()
// Reads the input line and returns the corrected version as a stack.
// For each character read, either enters it into the stack or, if it is
// ‘<-’, corrects the contents of stack
stack.createStack()
Read newChar
while (newChar is not the end-of-line symbol) {
if (newChar is not ‘<-’) {
stack.push(newChar)
}
else if (!stack.isEmpty()) {
oldChar = stack.pop()
} // end if
Read newChar
} // end while
return stack
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Simple Applications of the ADT Stack
• Checking for Balanced Braces
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 6.2
Traces of the algorithm that checks for balanced braces
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Implementations of the ADT Stack
• Array-based Implementation
• Reference-based Implementation
• Comparing Implementations
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 6.3
Implementation of the ADT stack that use a) an array; b) a linked list;
c) an ADT list
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 6.4
An array-based implementation
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 6.5
A reference-based
implementation
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 6.6
An implementation that uses the ADT list
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 6.7
The action of a postfix calculator when evaluating the expression 2 * (3 + 4)
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 6.8
A trace of the algorithm that converts the infix expression a - (b + c * d)/e to
postfix form
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 6.9
Flight map for HPAir
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 6.10
The stack of cities as you travel a) from P; b) to R; c) to X; d) back to R; e) back
to P; f) to W
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 6.11
The stack of cities a) allowing revisits and b) after backtracking when revisits
are not allowed
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 6.12
A trace of the search algorithm, given the flight map in Figure 6-9
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 6.13
A piece of a flight map
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 6.14
Visiting city P, then R, then X: a) box trace versus b) stack
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 6.15
Backtracking from city X, then R, then P: a) box trace versus b) stack
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 6.16
Flight map for Self-Test Exercise 9 and Exercise 11
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 6.17
Railroad switching system for Exercise 2
Data Abstraction and Problem Solving with JAVA Walls and Mirrors; Frank M. Carrano and Janet J. Prichard © 2001 Addison Wesley
Figure 6.18
Adjacency list for the flight map in Figure 6-9