CSC 1052
STACKS
10/3/2015
1
Outline
 Stacks
 Basic operations
 Examples of use
 Queues
 Basic operations
 Examples of use
 Implementations
 Array-based and linked list-based
10/3/2015
2
Static vs. Dynamic Structures
 Recall that a static data structure has a fixed size
 Arrays are static;
 once you define the number of elements it can
hold, it doesn’t change.
3
Objects

A dynamic data structure grows and shrinks as required
by the information it contains.
 We have examined a data structure where two objects
can be instantiated and chained together
 The next reference of one Node object refers to the
other node.
 This will create a linked list of Node objects.
10/3/2015
4
Stacks
 A stack ADT is also linear, like a list or queue,
 It maintains its information in a straight line.
 Items are added and removed from only one end of a
stack.
 It is therefore LIFO: Last-In, First-Out.
5
Stacks
 Stacks are often drawn vertically:
PUSH
POP
add
remove
6
A conceptual view of a stack
10/3/2015
7
Stacks
 Some stack operations:
- push -add an item to the top of the stack.
- pop - remove an item from the top of the stack.
- peek - retrieves top item without removing it.
- empty - returns true if the stack is empty.
8
Stacks
 A stack is a structure of ordered items such that items
can be inserted and removed only at one end - called the
top.
 A stack is a LIFO or Last-in/First-Out structure.
 Items are taken out of the stack in reverse order from
their insertion.
10/3/2015
9
Non-Computer Examples
 Stack of papers
 Stack of bills
 Stack of plates
 Expect O ( 1 ) time per stack operation.
 (In other words, constant time per operation, no matter
how many items are actually in the stack).
10/3/2015
10
Stack
 The stack specification lists a stack constructor and five
methods.
 One of the simplest stack implementations is to reverse
a word.
 Most compilers use stacks to analyze the syntax of a
program.
10/3/2015
11
Input NAT
Push N
N
Pop
T
Push A
Push TUsing a Stack to reverse a word
N
T
A
N
Pop A
POP N
A
Output TAN
A
N
N
10/3/2015
12
STACKS applications
 At all times in the execution of the reverse word
program,
 Only item can accessed from the stack,
 This is the item on the TOP.
10/3/2015
13
Peek()
 We will use a method called peek() to view the top item
 It looks at the top item but does not remove it.
 Stacks are also used frequently to evaluate expressions
10/3/2015
14
Applications – Evaluate expressions
 Stacks can be used to check a program for balanced
symbols (such as {}, (), []).
 Example: {()} is legal, {(}) is not
 (so simply counting symbols does not work).
10/3/2015
15
Evaluate expressions
 When a closing symbol is seen,
 it must match the most recently seen unclosed
opening symbol.
 Therefore, a stack will be appropriate.
10/3/2015
16
Balanced Symbol Algorithm
 Make an empty stack.
 Repeatedly read tokens(parenthesis);
 if the token is:
 an opening symbol, push it onto the stack
 If it is a closing symbol
 and the stack is empty, then report an error;
 otherwise pop the stack and determine if the
popped symbol is a match (if not report an error)
 At the end of the file, if the stack is not empty,
report an error.
10/3/2015
17
Example
 Input: { ( ) }
 Push {
 Push ( stack now has { (
(
{
 Pop - Next comes a ) , pop an item, it is ( which matches ).
 Stack now has {
{
 Pop – Next comes a } , pop an item, it is { which matches }.
 End of file;
stack is empty, so all is good.
10/3/2015
18
Input: ( { } { } )
Empty
Stack
Read and
Push (
Read Read first
and
} , pop
Push { matching {
(
Read )
and Pop
(
{
{
(
Read
and
Push
2nd {
Read 2nd },
pop
matching {
(
(
(
10/3/2015
19
Input: [ { } { } ]{}
Initial
Empty
Stack
Read
and
Push [
Read and
Push {
Read first },
pop
matching {
{
[
1
[
3
2
Read and
Push 2nd {
[
4
Read 2nd }, pop
matching {
{
[
[
5
6
And so
on..
10/3/2015
20
Performance
 Running time is O( N ),
 where N is amount of data (that is, number of tokens).
 Algorithm is online:
 it processes the input sequentially, never needing to
backtrack.
10/3/2015
21
Balancing an expression
 In the method IsBalanced(String exp) an expression is
checked to see if all the parentheses match.
 A charStack is set up whose legal characters are:
“() {} [} “
 A switch is used
10/3/2015
22
Method Stack
 Matching symbols is similar to method call and
method return,
 because when a method returns, it returns to the
most recently active method.
 A method stack can be used to keep track of this.
10/3/2015
23
Method call and return
 Abstract idea:
 when a method call is made,
 save current state of the method on a stack.
 On return,
 restore the state by popping the stack.
10/3/2015
24
Stack Frames or Activation Records
 Programs compiled from modern high level languages
make use of a
 stack frame for the working memory of each method
invocation.
 When any method is called, a number of words - the
stack frame - is pushed onto a program stack.
 When the method returns, this frame of data is popped
off the stack.
10/3/2015
25
Stack frame or Activation Record
 The Stack Frame or Record contains the :
 Method arguments
 Return address
 And local variables of the method to be stored
10/3/2015
26
method f( int x, int y) {
int a;
if ( end_cond ) return
…;
a = ….;
return g( a );
}
method g(
int p,
p = ….
return
}
int z ) {
q;
; q = …. ;
f(p,q);
Context for execution of f:
Each frame contains :
parameters, return address and local variables
10/3/2015
27
Activation Records
 As a method calls another method,
 first its arguments,
 then the return address and
 finally space for local variables is pushed onto the stack.
10/3/2015
28
current method environment.
The top of stack stores the current method environment.
 When the method is called,
 the new environment(parameters etc.) is pushed onto
stack.
 When the method ends and returns,
 the old environment is restored by popping the method
environment.
10/3/2015
29
Stack Frames
  Since each function runs in its own "environment" or
context,
 it becomes possible for a function to call itself - a
technique known as recursion.
  This capability is extremely useful and extensively used
 - because many problems are elegantly specified or
solved in a recursive way.
10/3/2015
30
Stack Frames
 The most common applications for stacks have a space
restraint
 so that using an array implementation for a Stack is a
natural and efficient one.
 In most operating systems, allocation and de-allocation
of memory costs time and space , e.g.
 there is a penalty for the flexibility of linked list
implementations..
10/3/2015
31
Array Implementations
 Stacks can be implemented with
 an array and
 an integer top that stores the array index of the top of
the stack.
 Empty stack has top equal to -1.
10/3/2015
32
Operations of a Stack
 To push an object on the stack ,


increment the top counter, and
write in the array position.
 To pop an item from the stack:
decrement the top counter.
10/3/2015
33
Stages
B
top(-1)
A
top(0)
top(1)
A
10/3/2015
34
Array Doubling
 If stack is full (because array size has been reached), we
can extend the array, using array doubling.
 We allocate a new, double-sized array and copy contents
over:
array =[T] new Object[ OldArray.length * 2 ];
for( int j = 0; j < OldArray.length; j++ )
Array[ j ] = OldArray[ j ];
OldArray = array;
10/3/2015
35
Running Time
 Without array doubling,
 all operations are constant time, and
 They do not depend on number of items in the stack.
 With array doubling,
 A push could occasionally be O( N ).
10/3/2015
36
Big O of Stack
 However,
 if the array doubling occurs infrequently,
 it is essentially O( 1 )
 because each array doubling that costs N assignments
 is preceded by N/2 non-doubling pushes.
10/3/2015
37
EXPRESSION EVALUATION
10/3/2015
38
Infix Expressions
 Example: 1 + 2 * ( 3 + 4 )
 Operands appear both before and after operator.
 When there are several operators,
 precedence and associativity determine how operators
are processed.
10/3/2015
39
Precedence and Associativity
 Precedence: used to decide which of two operators
should be processed.
 Associativity: used to decide which of two operators
should be processed when both operators have the
same precedence.
 Exponentiation: Right to Left
 Multiplication/Division: Left to Right
 Addition/Subtraction: Left to Right
10/3/2015
40
Examples
 4-4-4 evaluates to -4
 2^2^3 evaluates to 256
 Parenthesis override precedence and associativity.
10/3/2015
41
Evaluating Infix expressions
 In developing an application to use a stack to evaluate an
infix expression,
 several items must be considered.
10/3/2015
42

A fully parenthized expression can be evaluated using
the Stack data structure.

The implementation is complicated because of necessity
for two stacks:
 1. Operator stack to store unprocessed operators.
 2. Operand stack to store unprocessed operands
 The time analysis is:
 2n reads/peeks + n operations + 3n pushed + 3n
popped = 9n
10/3/2015
43
Difficulty of Infix Evaluation
 Infix evaluation is difficult because of precedence rules:
 when an operator is seen, it may or may not need to be
deferred.
 if it has a lower precedence than an operator further
along in the expression.
 Even if operator needs to be used, the second operand
has still not been processed.

1+2*…
10/3/2015
44
Postfix Expressions
 An alternate form is the postfix expression
 Let's examine a program that uses a stack to evaluate
postfix expressions
 In a postfix expression, the operator comes after its two
operands
10/3/2015
45
Infix to Postfix
 We generally use infix notation, with parentheses to force
precedence:
(3 + 4) * 2
 In postfix notation, this would be written
3 4 + 2 *
 In postfix, when you come to an operator, you already
have it operands
10/3/2015
46
Postfix Example – Let’s solve it
 123*+
 Push 1, Push 2, Push 3.
 When * is seen, Pop 3, Pop 2, evaluate 2 * 3, and Push
the result 6.
 When + is seen, Pop 6, Pop 1, evaluate 1 + 6, and Push
the result 7.
 At end of expression, stack should have one item,
 which is the answer.
10/3/2015
47
 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, only the answer will be on the stack
10/3/2015
48
Postfix Example, Continued
WHEN YOU THE FIRST OPERATOR IS MET, -- THE *,
The following operations will store the expression on
POP THE 3 AND THE 2 , MULTIPLY THEM
the stack. As an operator is encountered the operators
areAND
popped
appropriate
operation
STOREand
THEthe
PRODUCT
- 6 – ON
THE STACKperformed.
123*+
1
Push 1
3
2
1
2
1
Push 2
Push 3
When the last operator (+) is met,
pop 6 and 1 and add them, and
push the result on the stack
6
1
7
Pop 3
Pop 6
Pop 2
Pop 1
Push 6 Push 7
10/3/2015
49
OLD COMPILERS translated infix expressions using two stacks into
machine language.
AN OPERATOR IS PLACED BETWEEN ITS OPERANDS
c – d + (e * f – g * h) / i
INFIX
MACHINE LANGUAGE
THIS GETS MESSY BECAUSE OF PARENTHESES
AND NEED FOR TWO STACKS
NEWER COMPILERS:
INFIX
POSTFIX
MACHINE LANGUAGE
IN POSTFIX NOTATION, AN OPERATOR IS PLACED
IMMEDIATELY AFTER ITS OPERANDS.
INFIX
a+b
POSTFIX
ab+
a+b*c
abc*+
a*b+c
ab*c+
(a + b) * c
ab+c*
PARENTHESES NOT NEEDED – AND NOT USED – IN POSTFIX
10/3/2015
51
Infix to Postfix Conversion
 By converting infix expressions to postfix, an
expression can be easily evaluated.
 This computer first changes infix to postfix and
theN solves the postfix expression
10/3/2015
52
Infix to Postfix
 The basic algorithm is operator precedence
parsing.
 When an operand is seen, it is immediately
output. Below we write out the 1
 What happens when an + operator is seen?
 1 + 2 * ( 3 + 4 )
10/3/2015
53
Infix to Postfix Conversion
 When an operator is seen,
 it can never be output immediately,
 because the second operand has not been seen yet.
 The operator must be saved, and eventually output.
 A stack is used to store operators that have been seen
but not yet output.
10/3/2015
54
Operator Stack
 In an expression such as :
 infix expression - 1 + 2 * 3 ^ 4 + 5
 postfix expression - 1 2 3 4 ^ * + 5 +.
 Infix expression - 1*2+3^4+5
 postfix expression - 1 2 * 3 4 ^ + 5 +.
 In both cases, when the second operator is about to be
processed, we have output 1 and 2, and there is one
operand on the stack.
10/3/2015
55
Exiting the Operator Stack
 The question is:
 How do operators exit the stack?
 An operator exits the stack if the precedence and
associativity rules indicate that
 it should be processed instead of the current operator.
10/3/2015
56
Precedence Rules
 Basic rule:
 If the current operator has a lower precedence
than the operator on the top of the stack,
 then the top of stack operator exits the stack.
10/3/2015
57
Equal precedence
 Associativity rules decide what to do if current operator
has same precedence as operator on the top of stack.
 If operators are left associative, stack operator is popped
 4-4-4 = 4 4 - 4 –
 If operators are right associative, stack operator is not
popped.
 2^2^3 = 2 2 3 ^ ^
10/3/2015
58
LET’S CONVERT AN INFIX STRING TO A POSTFIX
STRING.
x–y*z
10/3/2015
59
INFIX
POSTFIX
x–y*z
x
We write out the x to postfix and move to the operator -
10/3/2015
60
INFIX
POSTFIX
x–y*z
x
We do not yet have the operands for the “-”
SO ‘-’ MUST BE TEMPORARILY SAVED SOMEWHERE.
10/3/2015
61
INFIX
POSTFIX
x–y*z
xy
We put ‘-’ on the stack and write the Y to postfix
10/3/2015
62
INFIX
POSTFIX
x–y*z
xy
*
THE OPERANDS FOR ‘*’ ARE NOT YET IN POSTFIX,
SO ‘*’ MUST BE TEMPORARILY saved on the stack ,
AND ‘*’ has a higher precedence than ‘-’.,
so it is pushed on the stack.
10/3/2015
63
Exiting the Stack
 The rule is that the an operator:
 does not exit the stack
*
-
 Unless it has a higher precedence than the
operator being considered
 The minus sign has lower precedence than the *
10/3/2015
64
INFIX
POSTFIX
x–y*z
xyz
INFIX
x–y*z
*
-
POSTFIX
xyz* –
We Come to the end of the infix expression and so pop all the
operators.
10/3/2015
65
INFIX
POSTFIX
x–y*z
xyz* –
10/3/2015
66
THE TEMPORARY STORAGE FACILITY IS A STACK.
FOR EACH OPERATOR IN THE INFIX EXPRESSION:
LOOP UNTIL an OPERATOR IS TO BE PUSHED:
IF OPERATOR STACK IS EMPTY,
PUSH OPERATOR ON THE STACK
ELSE IF INFIX OPERATOR HAS GREATER PRECEDENCE
THAN TOP OPERATOR ON STACK,
PUSH THE INFIX OPERATOR ON THE STACK
ELSE
POP OPERATOR ON STACK AND APPEND TO POSTFIX
EXPRESION
10/3/2015
67
 Infix expression - 1 * 2 + 3 ^ 4 + 5
 postfix expression - 1 2 * 3 4 ^ + 5 +.
1.
Write the 1 to output
2.
Put * on the stack
3.
Write the 2 to output
4.
The + has lower precedence to the *, so pop the * , write it
out and put the + on the stack
2.
*
4.
5.
+
Write out the 3 and put the ^ on the stack
6. Write out the 4, the + has lowest precedence so pop
^ and the + (associativity) and push the + on the stack
7. Write out the 5, no more input so pop stack
Output: 1 2 * 3 4 ^ + 5 +
10/3/2015
5.
^
+
6. +
68
WHAT ABOUT PARENTHESES?
LEFT PARENTHESIS: HAS LOWEST PRECEDENCE
SO PUSH ON THE STACK
RIGHT PARENTHESIS: POP ALL OPERATORS AND
APPEND THEM TO POSTFIX UNTIL THE ‘(‘ IS MET.
DISCARD ‘(‘
10/3/2015
69
STACK APPLICATION
CONVERTING FROM INFIX TO POSTFIX
10/3/2015
70
Multiple Stack Exits
 In expression such as 1+2*3^4+5, with postfix
equivalent:
1234^*+5+
when second + is seen, ^ * + are all popped.
 Thus, several exits can occur on one symbol.
10/3/2015
71
Infix to Postfix Example
Infix: 1 – 2 ^ 3 ^ 3 - ( 4 + 5 * 6 ) * 7
Postfix: 1 2 3 3 ^ ^ - 4 5 6 * + 7 * 1
1
^ 3
^
3
*
+
(
*
2
-
2
^^- (
(
*
+
( 6
6
*+
)
^
^
^ 3
3
^
^
^
( 4
4
+
(
+
+
( 5
5
*
*
* 7
7
*-
10/3/2015
72
Parentheses
 The Left parenthesis is the higher precedence operator
when it is an input symbol
 (meaning that it is always pushed on the stack).
 Left parenthesis is a lower precedence operator when it is
on the stack. Only a right parenthesis can pop it
 Right parenthesis pops the stack until a left parenthesis is
met and then pops the left parens
 Operators are written to output, but parenthesis are
discarded.
10/3/2015
73
Algorithm Summary infix - postfix
 Operands: Immediately output.
 Left parenthesis: push on the stack
 Right parenthesis: Pop stack symbols until an open
parenthesis is seen. Pop and discard left parens.
 Operator: Pop all stack symbols until
(1) Stack is empty
(2) Meet a left parenthesis
(3) we see a symbol of lower precedence, or a right- associative
symbol of equal precedence.
(4) Then push the operator.
 End of input: Pop all remaining symbols.
10/3/2015
74
Precedence Table
 The Algorithm is implemented by use of a precedence
table;
 associativity can be incorporated into precedences.
 Each symbol has two precedences: one as current
symbol, one as top of operator stack.
10/3/2015
75
The LinkedStack Class
 Now let's examine a linked implementation of a stack
 We will reuse the LinearNode class that we used in
LinkedList implementation to define the linked
implementation of a set 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
10/3/2015
76
A linked implementation of a stack
10/3/2015
77
LinkedStack - the push Operation
Top is declared at the top of the class as:
LinearNode top ( similar to head)
What method is this similar to?
10/3/2015
78
The stack after pushing element T
10/3/2015
79
LinkedStack - the pop Operation
What method is this similar to?
10/3/2015
80
The stack after a pop operation
10/3/2015
81
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 T 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
10/3/2015
82
An array implementation of a stack
10/3/2015
83
ArrayStack - 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 (T element)
{
if (size() == stack.length)
expandCapacity();
// store the element in the array
// increment top
}
10/3/2015
84
The stack after pushing element E
10/3/2015
85
ArrayStack - 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 T pop() throws EmptyStackException
{
if (isEmpty())
throw new EmptyStackException();
// decrement top;
// store the element in top –in an object of type T to return it
// set top of stack to null
return result;
}
10/3/2015
86
The stack after popping the top element
10/3/2015
87
The java.util.Stack Class
 The Java Collections framework defines a Stack with
similar operations
 It is derived from the Vector class and thus has
methods that are not appropriate for a 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.
10/3/2015
88
Stacks
 The java.util package contains a Stack class that is
implemented using a Vector.
 It contains methods that correspond to standard stack
operations plus method that returns an integer
corresponding to the position in the stack of the
particular object.
 This type of searching is not usually considered to be part
of the classic stack ADT.
10/3/2015
89
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
10/3/2015
90
Collections Framework
 Let’s review more about the properties that all the
collection classes have in common:
 Allow the collection size to increase dynamically
 All only hold items that are generic - T
 Provides at least two constructors –
 one to create an empty collection and
 one that accepts as a parameter any other collection
object and creates a new collection object that holds
the same information.
10/3/2015
91
Collections Framework
 The collections differ in:
 Logical structure of the elements they contain
 The underlying implementation’
 The efficiency of the various operations
 The set of supported operations
 Whether they allow duplicates
 Whether they allow keys
 Whether the elements are sorted
10/3/2015
92
Collections Framework
 The Vector class has been replaced by the ArrayList class
which provides the same methods in a single thread
environment.
 The HashTable class also supports synchronization so for
single thread programs you should use HashMap.
 The Stack class of the Collections Framework is
implemented with a Vector. There are the expected
problems with performance due to concurrency and a
logical error. Vectors allow access anywhere in the array,
stacks do not.
10/3/2015
93
Collections Framework
 The Collection Interface is used by classes that do not support
a unique key value, e.g. unkeyed lists and sets.
 Some methods in the interface are:
 boolean Add(T obj) - adds obj to Collection
 boolean addAll(Collection c) –add c to Collection
 boolean contains(T obj) – return true if obj is
in Collection
 boolean isEmpty() - returns true if collection is empty
10/3/2015
94
Collections Framework
 The MAP interface::
 This interface is used by library collection classes that
map unique keys to values.
 It defines a method to retrieve an object based on its key
value.
 Classes that implement the MAP interface are:
 AbstractMap, HashMap and HashTable.
10/3/2015
95
Collections Framework
 The AbstractCollection Class implements the Collection
interface. The Collection interface defines 15 operations
 Some of these methods define fundamental operations
which will vary with the particular collection. Others will
be the same no matter what the implementation, e.g.
 The size method will depend upon the implementation
so it is an abstract method but the isEmpty() method can
be implemented as:
public boolean isEmpty()
{
return (this.size() == 0)
}
10/3/2015
96
Collections Framework
 By defining as many methods as possible in terms of the
fundamental operations, the AbstractCollection class
cuts down on the time to implement a new collection.
 In addition, two other abstract classes extend the
AbstractCollection class – AbstractSet and AbstractList.

 Both these classes perform the same services as the
AbstractCollection class
 Finally, concrete classes extend AbstractSet and
AbstractList.
10/3/2015
97
Collection
List
Set
AbstractList
ArrayList
interface
LinkedList
abstract class
AbstractSet
HashSet
TreeSet
fully-defined class
10/3/2015
98
Descargar

COP-3530 Data Structures