Stack
Abstract Data Types (ADTs)
An abstract data type (ADT) Example: ADT modeling
is an abstraction
a simple stock trading system
of a data structure The data stored are buy/sell orders
An ADT specifies:
Data stored
The operations supported are
order buy(stock, shares, price)
order sell(stock, shares, price)
Operations on the data void cancel(order)
Error conditions
associated with operations
Error conditions:
Buy/sell a nonexistent stock
Cancel a nonexistent order
The Stack ADT
The Stack ADT Auxiliary stack operations:
stores arbitrary objects object top():
returns the last inserted
Insertions and deletions element without removing it
follow the last-in first-out scheme
integer size():
Think of a returns the number of
elements stored
spring-loaded plate dispenser
Main stack operations:
boolean isEmpty():
indicates whether no
push(object):
elements are stored
inserts an element
object pop():
removes and returns the last inserted
element
Stack: operations and their
effects
ExampleI using built-in Stack:
Reversing an Array
Refer to ArrayReverseApp project
The elements of an array can be reversed
Using the Java built-in class called Stack
Which is part of the [Link] package
Number is a base class for
BigDecimal, BigInteger
Byte, Double, Float, Integer, Long and Short
ExampleII using built-in Stack:
Reversing an Array
Refer to SecretMessageApp project
The secret message is
Encoded by having each individual word reversed
And then decoded by means of an auxiliary stack
Character are displayed in reverse order when
Popped from the auxiliary stack variable
Our Stack Interface
public interface Stack {
Java interface corresponding to
our Stack ADT public int size();
Requires the definition of class public boolean
StackException isEmpty();
public Object top()
Different from the built-in Java throws
class [Link] StackException;
public void
push(Object o) throws
StackException;
public Object pop()
throws
StackException;
}
Exceptions
Attempting the execution In the Stack ADT, operations
of an operation of ADT may pop and top cannot be
sometimes cause an error condition, performed if the stack is empty
called an exception
push cannot be
Exceptions are said to be performed if the stack is full
“thrown” by an operation that
cannot be executed Attempting the execution
of pop or top on an empty stack
throws an StackException
of push on a full stack throws
an StackException
Array-based Stack
A simple way of implementing Algorithm size()
the Stack ADT return t + 1
uses an array
We add elements Algorithm pop()
from left to right if isEmpty() then
throw
A variable keeps track StackException
of the index of the top element else
tt1
return S[t + 1]
…
S
0 1 2 t
Array-based Stack (cont.)
The array
storing the stack elements may
become full Algorithm push(o)
if t = [Link] 1 then
A push operation will then throw a throw
StackException
Limitation of the array-based StackException
implementation else
tt+1
Not intrinsic to the Stack ADT
S[t] o
…
S
0 1 2 t
Example III using our Stack:
Parentheses Matching
“(”, “{”, or “[” must be paired with a matching “)”,“}”, or “[”
correct: ( )(( )){([( )])}
correct: ((( )(( )){([( )])}
incorrect: )(( )){([( )])}
incorrect: ({[ ])}
incorrect: (
Refer to GroupingSymbolsApp project
Parentheses Matching Algorithm
Algorithm ParenMatch(X,n):
Input: An array X of n tokens, each of which is either a
grouping symbol, a variable, an arithmetic operator, or a
number
Output: true if and only if all the grouping symbols in X
match
Let S be an empty stack
for i=0 to n-1 do
if X[i] is an opening grouping symbol then
[Link](X[i])
else if X[i] is a closing grouping symbol then
if [Link]() then
return false {nothing to match with}
if [Link]() does not match the type of X[i] then
return false {wrong type}
if [Link]() then
return true {every symbol matched}
else
return false {some symbols were never matched}