Transcript figure 1.1 Aspects of software quality

Chapter 6
Stacks
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 © 2004 Pearson Addison-Wesley. All rights reserved.
1-2
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 © 2004 Pearson Addison-Wesley. All rights reserved.
1-3
figure 6.1 A conceptual view of a stack
Copyright © 2004 Pearson Addison-Wesley. All rights reserved.
1-4
figure 6.2 The operations on a stack
• See StackADT.java (page 148)
Copyright © 2004 Pearson Addison-Wesley. All rights reserved.
1-5
figure 6.3
The StackADT interface in UML
Copyright © 2004 Pearson Addison-Wesley. All rights reserved.
1-6
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 © 2004 Pearson Addison-Wesley. All rights reserved.
1-7
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 © 2004 Pearson Addison-Wesley. All rights reserved.
1-8
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 © 2004 Pearson Addison-Wesley. All rights reserved.
1-9
figure 6.4 Using a stack to evaluate
a postfix expression
Copyright © 2004 Pearson Addison-Wesley. All rights reserved.
1-10
Postfix Expressions
• To simplify the example, let's assume the
operands to the expressions are integer
literals
• Our solution uses an ArrayStack, though
any implementation of a stack would suffice
• See Postfix.java (page 152)
• See PostfixEvaluator.java (page 153)
Copyright © 2004 Pearson Addison-Wesley. All rights reserved.
1-11
figure 6.5 A UML class diagram
for the postfix expression program
Copyright © 2004 Pearson Addison-Wesley. All rights reserved.
1-12
The LinkedStack Class
• Now let's examine a linked implementation of
a stack
• We will reuse the LinearNode class that we
used in Chapter 3 to define the linked
implementation of a bag collection
• Internally, a stack is represented as a linked
list of nodes, with a reference to the top of the
stack and an integer count of the number of
nodes in the stack
Copyright © 2004 Pearson Addison-Wesley. All rights reserved.
1-13
figure 6.6
A linked implementation of a stack
Copyright © 2004 Pearson Addison-Wesley. All rights reserved.
1-14
The push Operation
//----------------------------------------------------------------// Adds the specified element to the top of the stack.
//----------------------------------------------------------------public void push (Object element)
{
LinearNode temp = new LinearNode (element);
temp.setNext(top);
top = temp;
count++;
}
Copyright © 2004 Pearson Addison-Wesley. All rights reserved.
1-15
figure 6.7
The stack after pushing element E
Copyright © 2004 Pearson Addison-Wesley. All rights reserved.
1-16
The pop Operation
//----------------------------------------------------------------// Removes the element at the top of the stack and returns a
// reference to it. Throws an EmptyStackException if the stack
// is empty.
//----------------------------------------------------------------public Object pop() throws EmptyStackException
{
if (isEmpty())
throw new EmptyStackException();
Object result = top.getElement();
top = top.getNext();
count--;
return result;
}
Copyright © 2004 Pearson Addison-Wesley. All rights reserved.
1-17
figure 6.8
The stack after a pop operation
Copyright © 2004 Pearson Addison-Wesley. All rights reserved.
1-18
The ArrayStack Class
• Now let's examine an array-based
implementation of a stack
• We'll make the following design decisions:
• maintain an array of Object references
• the bottom of the stack is at index 0
• the elements of the stack are in order and
contiguous
• an integer variable top stores the index of the
next available slot in the array
• This approach allows the stack to grow and
shrink at the higher indexes
Copyright © 2004 Pearson Addison-Wesley. All rights reserved.
1-19
figure 6.9
An array implementation of a stack
Copyright © 2004 Pearson Addison-Wesley. All rights reserved.
1-20
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 (Object element)
{
if (size() == stack.length)
expandCapacity();
stack[top] = element;
top++;
}
Copyright © 2004 Pearson Addison-Wesley. All rights reserved.
1-21
figure 6.10
The stack after pushing element E
Copyright © 2004 Pearson Addison-Wesley. All rights reserved.
1-22
The pop Operation
//----------------------------------------------------------------// Removes the element at the top of the stack and returns a
// reference to it. Throws an EmptyStackException if the stack
// is empty.
//----------------------------------------------------------------public Object pop() throws EmptyStackException
{
if (isEmpty())
throw new EmptyStackException();
top--;
Object result = stack[top];
stack[top] = null;
return result;
}
Copyright © 2004 Pearson Addison-Wesley. All rights reserved.
1-23
figure 6.11
The stack after popping the top element
Copyright © 2004 Pearson Addison-Wesley. All rights reserved.
1-24
The java.util.Stack Class
• The Java Collections framework defines a
Stack class with similar operations
• It is derived from the Vector class and
therefore has some characteristics that are
not appropriate for a pure stack
• The java.util.Stack class has been
around since the original version of Java, and
has been retrofitted to meld with the
Collections framework
Copyright © 2004 Pearson Addison-Wesley. All rights reserved.
1-25
figure 6.12 A UML description
of the java.util.Stack class
Analysis of Stack Operations
• Because stack operations all work on one
end of the collection, they are generally
efficient
• The push and pop operations, for both linked
and array implementations, are O(1)
• Likewise, the other operations for all
implementations are O(1)
• We'll see that other collections (which don't
have that characteristic) aren't as efficient for
all operations
Copyright © 2004 Pearson Addison-Wesley. All rights reserved.
1-27