Transcript Stacks

Stacks
Chapter 5
Overview
The stack ADT
 Exceptional situations
 Stack implementations

• stacks in Java
What is a Stack?

Linear pile of objects of one type
•
•
•
•

one on top of another; not a “heap”
in a particular order
access only at one end (the “top”)
“LIFO”: Last In = First Out
Real life stacks
• stack of books/paper
• stack of plates/bowls/beer cups
Stack Operations

Stacks require at least these operations:
• insert at top (push)
• delete from top (pop, pull)

.push(item)
.pop()
Typically have some others
•
•
•
•
check if empty
inspect top element (peek, top)
empty it out
get number of elements
.isEmpty()
.peek()
.clear()
.size()
A Stack

Generally arranged up & down
• top at the top

Top
Old items are popped off the stack
• myStack.pop()

New items are pushed onto the stack
• myStack.push(14)
Stack
35
24
81
12
5
7
17
12
8
A Stack

Generally arranged up & down
• top at the top

Top
Old items are popped off the stack
• myStack.pop()

New items are pushed onto the stack
• myStack.push(14)
Stack
24
81
12
5
7
17
12
8
A Stack

Generally arranged up & down
• top at the top

Top
Old items are popped off the stack
• myStack.pop()

New items are pushed onto the stack
• myStack.push(14)
Stack
14
24
81
12
5
7
17
12
8
Exercise

Draw the stacks that result from the
following operations. Start with empty each
time. Also, make a list of the items popped.
• push A, push B, push C, pop, push D, pop, pop
• push 1, push 2, pop, pop, push 3, push 4, pop
• push 1, push 2, push 3, push 4, pop, pop, pop, pop
Return Values

Push naturally void
• put this thing on the stack; nothing to return

Peek naturally value-returning
• return value that is on top of stack
Empty naturally boolean (empty or not?)
 Clear naturally void
 Size naturally value-returning

• number of items in the stack
Return Values

Pop can be either void or value-returning
• either: take something off stack and discard it
» C++’s STL stack is like this
• or: take something off stack and return it
» Java’s java.util.Stack like this

Pop must return value if no peek operation
• otherwise no way to get values out of the stack!
• we (text authors and I) prefer value-returning
Exceptional Circumstances

What could go wrong?
• try to pop off/peek at top of empty stack
• try to push onto a full stack
• try to add null to stack (is this wrong?)

Options to deal are same as with bags
• return false (if naturally void)
• return special value (if one is available)
• throw exception (checked or unchecked?)
Design Decisions

Push is naturally void
• have it return false for failure?
• have it throw an exception?

Peek is naturally value-returning
• have it return null for failure?
• have it throw an exception?

Pop can be either!
• boolean/null/exception all valid options!
Exceptions: Checked or Not?

Client can easily check if stack is empty
• there’s a method for that
Client can thus write code that will never
try to pop/peek on empty stack
 Client should not be made to deal with
exceptions
 Use unchecked exceptions

Unchecked
n
Exc s
& Interfaces
Unchecked exceptions don’t need to be
mentioned in the interface
 If they are mentioned, they may be ignored!

• implementing classes don’t need to throw them
» NOTE: checked exceptions cannot be ignored

Interface should specify them anyway
• at least in the javadoc!
• clients should know what to expect
More Design Decisions

Provide multiple versions?
• methods must have different names
» can’t have different parameters!
» pair names in some way
• two versions return null?
• two versions throw exceptions?

How many different versions?
• don’t want things to be too complex
My Decisions

Push not expected to fail
• false return value might be missed…
• …so throw an IllegalStateException

Two versions of pop method
• pop throws a NoSuchElementException
• pull returns null when stack is empty

Two versions of peek method
• top throws a NoSuchElementException
• peek returns null when the stack is empty
My Stack Interface
public interface MyStackInterface<T> {
public void push(T newEntry);
// throws IllegalStateException
public T pop(); // throws NoSuchElementException
public T top(); // throws NoSuchElementException
public T pull(); // may return null
public T peek(); // may return null
public boolean isEmpty();
}
Other Stack Interfaces/Classes
StackInterface (from Text)
java.util.Deque (*)
void push(T newEntry); // nothing!
T pop();
// throws EmptyStackExcn.
T peek();
// throws EmptyStackExcn.
void push(T newEntry);
// throws IllegalStateExcn.
// throws ClassCastExcn.
// throws NullPointerExcn.
// throws IllegalArgumentExcn.
T pop();
// throws NoSuchElementExcn.
T peek();
// may return null
(class) java.util.Stack
T push(T newEntry); // nothing
T pop();
// throws EmptyStackExcn.
T peek();
// throws EmptyStackExcn.
(*) Deque is preferred to Stack!
Using Stacks









Balancing brackets
Pre/postfix expressions
Conversion to pre/postfix from infix (“normal”)
Procedure Activation Records
Towers of Hanoi
Railway shunting
Circuit design
Equivalence classes
Maze tracing
Balancing Brackets
Want to know if a string has the right
number of closing brackets/parentheses/etc.
 Each closing item must match opening item

• ] for [, ) for (, etc.

Nesting may be involved
• “{a(1, 2), b([c, d]), {e, f, [(g), ((h))]}}”
• “(1, [2, 3, ([4, (5, 6), {7,8})])])”
Method

Scan the string one character at a time
• stack up opening brackets as you see them
• when you see a closing bracket, pop a bracket
off the top & make sure it matches

Return false if:
• try to pop from an empty stack
• popped bracket doesn’t match
• procedure ends with non-empty stack
Code
for i  1 .. Length(string)
if isOpenBracket(string[i])
stack.push(string[i]);
else if isCloseBracket(string[i])
if stack.isEmpty()
return false;
if ~match(stack.top(), string[i])
return false;
stack.pop();
return stack.isEmpty();
Trace Execution

“{a(1, 2), b([c, d]), {e, f, [(g), ((h))]}}”
{a(1, 2), b([c, d]), {e, f, [(g), ((h))]}}
(
(
[
{
{
(
(
(
[
[ [ [ [
[ [
(
( ( (
{ { { { {
{ { {
{ { { { { { { { { { { {
{ { { {
{ ( ) ( [ ] ) { [ ( ) ( ( ) ) ] } }
Stack is empty: return true
Trace Execution

“(1, [2, 3, ([4, (5, 6), {7,8})])])”
(1, [2, 3, ([4, (5, 6), {7,8})])])
[
( (
[ [ [
( ( ( (
(
[
(
[
(
[
(
[
(
{
[
(
[
(
[
(
[
(
( [ ( [ ( ) { } )
Mismatch: return false
Exercise

Trace the balancing method for the
following string:
• (1 + (12 * [1, 3, 5], )) [, 7, 87, ][]()){()}
Postfix Calculator

AKA Reverse Polish notation
• used on HP calculators

No need for parentheses
• (3 + 5)*(8 + 17*6) becomes 3 5 + 8 17 6 * + *

Number, enter, number, operation
• 5 (enter) 17 (times) [85 appears]
Method
Numbers get pushed
 Operators:

• pop top two elements
• do math according to operation
• push result
Trace Execution

3 5 + 8 17 6 * + *
5
3 3
8
8 8
3 5 + 8 17
6
17 17 102
8 8
8
8 8
8
6
*
110
8 880
+
*
(3 + 5)*(8 + 17*6) = 8*(8 + 102) = 8*110 = 880
Exercise

Evaluate the following post-fix expression
1 2 3 4 5 + * + * 10 /
• show your stack
• show the equivalent infix expression
Conversion to Postfix

Write down operators & operations the way
they need to be done
• used to compile expressions

(3 + 5)*(8 + 17*6)
•
•
•
•
3+5 first  3, 5, +
17*6 next  17, 6, *
8 + (17*6)  8, 17, 6, *, +
multiply above  3, 5, +, 8, 17, 6, *, +, *
Things to Note

(3 + 5)*(8 + 17*6)  3 5 + 8 17 6 * + *
• order of operations  17*6 instead of 8 + 17
• parentheses  3+5 instead of 5*8
• numbers written down in same order

Need to keep operations pending
• next operation may need to be done before it
• closing parenthesis  complete all ops since (
Trace of Conversion

(
(3 + 5) * (8 + 17 * 6 – 2)
+
(
(
( 3 + 5 )
3
5
+
*
+
(
*
+
(
*
(
* *
+
–
( ( (
* * *
* ( 8 + 17 * 6 –
8
17
6
*
+
(
* *
2
2
)
–
\0
*
Exercise

Write pseudo-code for the infix to postfix
conversion
• what functions would be useful?
• so use them!
• hint: tokens – isNum(token), isOp(token)
• token is a number (int) or operator (char)
Stack Implementations
Can use arrays or linked structures
 Top is the important location

• for arrays it’s at the back (of the used part)
• for linked structures it’s at the front
• both very much like a Bag
» but we only never need to remove the latest object
» just like how we did remove() at first
Stacks in Java

Use Deque instead of Stack
• import and declare (like Lists, Sets, Bags, …)
import java.util.Deque;
import java.util.ArrayDeque;
Deque<String> stack = new ArrayDeque<String>();

Deques have more operations than stacks
• use only the Stack operations!
• push/pop may throw exceptions
• peek may return null
Questions