Transcript document
Stacks
Chapter 5
Chapter Objectives
To learn about the stack data type and how to use its
four methods: push, pop, peek, and empty
To understand how Java implements a stack
To learn how to implement a stack using an underlying
array or a linked list
To see how to use a stack to perform various
applications, including finding palindromes, testing for
balanced (properly nested) parentheses, and evaluating
arithmetic expressions
Stack Abstract Data Type
A stack can be compared to a Pez dispenser
Only the top item can be accessed
Can only extract one item at a time
A stack is a data structure with the property that only
the top element of the stack is accessible
The stack’s storage policy is Last-In, First-Out
Specification of the Stack
Abstract Data Type
Only the top element of a stack is visible, therefore the
number of operations performed by a stack are few
Need the ability to
Inspect the top element
Retrieve the top element
Push a new element on the stack
Test for an empty stack
Specification of the Stack
Abstract Data Type (continued)
Stack Applications
Two client programs using stacks
Palindrome finder
Parentheses matcher
Palindrome: string that reads the same in either
direction
Example: “Able was I ere I saw Elba”
Stack Applications (continued)
Stack Applications (continued)
When analyzing arithmetic expressions, it is important
to determine whether an expression is balanced with
respect to parentheses
(a+b*(c/(d-e)))+(d/e)
Problem is further complicated if braces or brackets are
used in conjunction with parenthesis
Solution is to use stacks!
Stack Applications (continued)
Stack Applications (continued)
Implementing a Stack as an
Extension of Vector
The Java API includes a Stack class as part of the
package java.util
The vector class implements a growable array of objects
Elements of a vector can be accessed using an integer
index and the size can grow or shrink as needed to
accommodate the adding and removing of elements
Implementing a Stack as an
Extension to Vector (continued)
Implementing a Stack with a List
Component
Can use either the ArrayList, Vector, or the LinkedList
classes as all implement the List interface
Name of class illustrated in text is ListStack<E>
ListStack is an adapter class as it adapts the
methods available in another class to the interface
its clients expect by giving different names to
essentially the same operations
Implementing a Stack Using an
Array
Need to allocate storage for an array with an initial
default capacity when creating a new stack object
Need to keep track of the top of the stack
No size method
Implementing a Stack Using an
Array (continued)
Implementing a Stack as a Linked
Data Structure
We can implement a stack using a linked list of nodes
Comparison of Stack
Implementations
Extending a Vector (as is done by Java) is a poor choice
for stack implementation as all Vector methods are
accessible
Easiest implementation would be to use an ArrayList
component for storing data
All insertions and deletions are constant time regardless
of the type of implementation discussed
All insertions and deletions occur at one end
Additional Stack Applications
Consider two case studies that relate to evaluating
arithmetic expressions
Postfix and infix notation
Expressions normally written in infix form
Binary operators inserted between their operands
A computer normally scans an expression string in the
order that it is input; easier to evaluate an expression in
postfix form
Additional Stack Applications
(continued)
Additional Stack Applications
(continued)
Advantage of postfix form is that there is no need to
group subexpressions in parentheses
No need to consider operator precedence
Evaluating Postfix Expressions
Evaluating Postfix Expressions
(continued)
Evaluating Postfix Expressions
(continued)
Evaluating Postfix Expressions
(continued)
Converting from Infix to Postfix
Additional Stack Applications
(continued)
Evaluating Postfix Expressions
(continued)
Evaluating Postfix Expressions
(continued)
Chapter Review
A stack is a last-in, first-out (LIFO) data structure
A stack is a simple but powerful data structure; its four
operations include empty, peek, pop, and push
Stacks are useful to process information in the reverse
of the order that it is encountered
Java.util.Stack is implemented as an extension of the
Vector class
Chapter Review (continued)
Three ways to implement a stack:
Using an object of a class that implements the List
interface as a container
Using an array as a container
Using a linked list as a container
Stacks can be applied in programs for evaluating
arithmetic expressions