Transcript Stacks - University of Scranton

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
Chapter 5: Stacks
2
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
Chapter 5: Stacks
3
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
Chapter 5: Stacks
4
Specification of the Stack Abstract Data
Type (continued)
Chapter 5: Stacks
5
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”
Chapter 5: Stacks
6
Stack Applications (continued)
Chapter 5: Stacks
7
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!
Chapter 5: Stacks
8
Stack Applications (continued)
Chapter 5: Stacks
9
Stack Applications (continued)
Chapter 5: Stacks
10
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
Chapter 5: Stacks
11
Implementing a Stack as an Extension to
Vector (continued)
Chapter 5: Stacks
12
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
Chapter 5: Stacks
13
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
Chapter 5: Stacks
14
Implementing a Stack Using an Array
(continued)
Chapter 5: Stacks
15
Implementing a Stack as a Linked Data
Structure
• We can implement a stack using a linked list of nodes
Chapter 5: Stacks
16
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
Chapter 5: Stacks
17
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
Chapter 5: Stacks
18
Additional Stack Applications (continued)
Chapter 5: Stacks
19
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
Chapter 5: Stacks
20
Evaluating Postfix Expressions
Chapter 5: Stacks
21
Evaluating Postfix Expressions (continued)
Chapter 5: Stacks
22
Evaluating Postfix Expressions (continued)
Chapter 5: Stacks
23
Evaluating Postfix Expressions (continued)
Chapter 5: Stacks
24
Converting from Infix to Postfix
Chapter 5: Stacks
25
Additional Stack Applications (continued)
Chapter 5: Stacks
26
Evaluating Postfix Expressions (continued)
Chapter 5: Stacks
27
Evaluating Postfix Expressions (continued)
Chapter 5: Stacks
28
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 5: Stacks
29
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
Chapter 5: Stacks
30