Bài giảng Cấu trúc dữ liệu_Phần Stack

Chapter 6
Stacks
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-2
Chapter Objectives
Examine stack processing
Define a stack abstract data type
Demonstrate how a stack can be used to solve problems
Examine various stack implementations
Compare stack implementations
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-3
Stacks
A stack is a linear collection whose elements are added and removed from one end
A stack is LIFO – last in, first out
The last element to be put on the stack is the first element to be removed
A stack is usually depicted vertically, with additions and deletions occurring at the top of the stack
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-4
FIGURE 6.1
A conceptual view of a stack
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-5
FIGURE 6.2
The operations on a stack
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-6
FIGURE 6.3
The StackADT interface in UML
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-7
Listing 6.1
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-8
Using Stacks
Stacks are particularly helpful when solving certain types of problems
Consider the undo operation in an application
keeps track of the most recent operations in reverse order
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-9
Postfix Expressions
Let`s examine a program that uses a stack to evaluate postfix expressions
In a postfix expression, the operator comes after its two operands
We generally use infix notation, with parentheses to force precedence:
(3 + 4) * 2
In postfix notation, this would be written
3 4 + 2 *
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-10
Postfix Expressions
To evaluate a postfix expression:
scan from left to right, determining if the next token is an operator or operand
if it is an operand, push it on the stack
if it is an operator, pop the stack twice to get the two operands, perform the operation, and push the result onto the stack
At the end, there will be one value on the stack, which is the value of the expression
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-11
FIGURE 6.4 Using a stack to evaluate a postfix expression
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-12
Postfix Expressions
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-13
Listing 6.2
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-14
Listing 6.2 (cont.)
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-15
Listing 6.3
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-16
Listing 6.3 (cont.)
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-17
Listing 6.3 (cont.)
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-18
Listing 6.3 (cont.)
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-19
Listing 6.3 (cont.)
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-20
FIGURE 6.5 A UML class diagram for the postfix expression program
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-21
Using Stacks - Traversing a Maze
A classic use of a stack is to keep track of alternatives in maze traversal or other trial and error algorithms
Using a stack in this way simulates recursion
Recursion is when a method calls itself either directly or indirectly
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-22
Using Stacks - Traversing a Maze
Run-time environments keep track of method calls by placing an activation record for each called method on the run-time stack
When a method completes execution, it is popped from the stack and control returns to the method that called it
Which is now the activation record on the top of the stack
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-23
Using Stacks - Traversing a Maze
In this manner, we can traverse a maze by trial and error by using a stack to keep track of moves that have not yet been tried
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-24
Listing 6.4
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-25
Listing 6.4 (cont.)
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-26
Listing 6.4 (cont.)
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-27
Listing 6.4 (cont.)
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-28
Listing 6.4 (cont.)
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-29
Listing 6.5
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-30
Listing 6.5 (cont.)
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-31
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-32
FIGURE 6.6 A linked implementation of a stack
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-33
LinkedStack - the push Operation
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-34
FIGURE 6.7 The stack after pushing element E
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-35
LinkedStack - the pop Operation
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-36
FIGURE 6.8
The stack after a pop operation
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-37
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-38
FIGURE 6.9 An array implementation of a stack
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-39
ArrayStack - the push Operation
//-----------------------------------------------------------------
// Adds the specified element to the top of the stack, expanding
// the capacity of the stack array if necessary.
//-----------------------------------------------------------------
public void push (T element)
{
if (size() == stack.length)
expandCapacity();

stack[top] = element;
top++;
}
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-40
FIGURE 6.10
The stack after pushing element E
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-41
ArrayStack - the pop Operation
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-42
FIGURE 6.11 The stack after popping the top element
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-43
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-44
FIGURE 6.12 A UML description
of the java.util.Stack class
Copyright © 2005 Pearson Addison-Wesley. All rights reserved.
6-45
Analysis of Stack Operations