Stack

• A stack is a data structure that stores data

in such a way that the last piece of data
stored, is the first one retrieved
– also called last-in, first-out
• Only access to the stack is the top
element
– consider trays in a cafeteria
• to get the bottom tray out, you must first
remove all of the elements above
 What is a stack?
• It is an ordered group of homogeneous items of elements.
• Elements are added to and removed from the top of the stack (the most recently
added items are at the top of the stack).
• The last element to be added is the first to be removed (LIFO: Last In, First
Out).
 Stack Of Cups

top F

top E E

D D

C C

B B

bottom A bottom A

• Add a cup to the stack.

• Remove a cup from new stack.
• A stack is a LIFO list.
 Stacks cont..

• A stack is a container of objects that are

inserted and removed according to the last-
in-first-out (LIFO) principle.
• Objects can be inserted at any time, but only
the last (the most-recently inserted) object
can be removed.
• Inserting an item is known as “pushing”
onto the stack. “Popping” off the stack is
synonymous with removing an item.
4
 Stacks cont..

• Linear list.
• One end is called top.
• Other end is called bottom.
• Additions to and removals from the top end
only.
 Stack operations

• Push
– the operation to place a new item at the top of
the stack
• Pop
– the operation to remove the next item from the
top of the stack
 Last In First Out

E top
D top D D top
C top C C C
B top B B B B
A top A A A A A
 Last In First Out cont..

M
C C C
R push(M) item = pop()
R R
item = M
X X X
A A A
 Stack Specification
• Definitions: (provided by the user)
– MAX_ITEMS: Max number of items that might be on the stack
– ItemType: Data type of the items on the stack
• Operations
– MakeEmpty
– Boolean IsEmpty
– Boolean IsFull
– Push (ItemType newItem)
– Pop (ItemType& item) (or pop and top)
 Stacks operations

– Standard operations:
• IsEmpty … return true iff stack is empty
• IsFull … return true iff stack has no remaining capacity
• Top … return top element of stack
• Push … add an element to the top of the stack
• Pop … delete the top element of the stack
 Implementing a Stack

• At least three different ways to implement a

stack
– array
– vector
– linked list
• Which method to use depends on the
application
– what advantages and disadvantages does each
implementation have?
 Implementing Stacks: Array
• Advantages
– best performance
• Disadvantage
– fixed size
• Basic implementation
– initially empty array
– field to record where the next data gets placed into
– if array is full, push() returns false
• otherwise adds it into the correct spot
– if array is empty, pop() returns null
• otherwise removes the next item in the stack
 An Array Based
Implementation

• Using an array to store a stack’s

entries:
(a) a preliminary sketch; (b)
implementation details
 Abstract Data Type: Stack

• A finite number of objects

– Not necessarily distinct
– Having the same data type
– Ordered by when they were added
• Operations
– isEmpty()
– push(newEntry)
– pop()
– peek()
 Example of Stack codes

• First example stack ADT and

implementation
 Push (ItemType newItem)

• Function: Adds newItem to the top of the stack.

• Preconditions: Stack has been initialized and is not
full.
• Postconditions: newItem is at the top of the stack.
 push() Method (array based)

public boolean push(Object data) {

if(top == maxSize-1) { return false; } // stack is full

// add the element and then increment top

stackArray [++top] = data;
return true;
}
 Pop (ItemType& item)

• Function: Removes topItem from stack and

returns it in item.
• Preconditions: Stack has been initialized
and is not empty.
• Postconditions: Top element has been
removed from stack and item is a copy of
the removed element.
 pop() Method (array based)

public Object pop() {

if(top == -1) { return null; } // stack is empty

// decrement top and return the data

Object data = stackArray [top--];
return data;
}
 Stack Class (array based)
class Stack {
private Object[ ] stackArray;
private int top;
private int maxSize;
public Stack (int size) {
maxSize=size;
stackArray = new Object[maxSize];
top = -1;
}
public boolean push(Object data);
public Object pop();
public void clear();
public boolean isEmpty();
public boolean isFull();
}
 Remaining Methods (array based)

public void clear() {

top =-1;
}

public boolean isEmpty() {

return top == -1;
}

public boolean isFull() {

return top == maxSize-1;
}
 Additional Notes

• Notice that the array is considered empty if

top equals -1
– doesn’t matter if there is more data stored in the
array – it will never be retrieved
• pop() method will automatically return
• For a truly robust implementation
– should set array elements equal to null if they
are not being used
• why? how?
 Stack Applications

• Real life
– Pile of books
– Plate trays
• More applications related to computer science
– Program execution stack (read more from your
text)
– Evaluating expressions
 The Stack Abstract Data Type
• Example : The following table shows a series of stack operations and their
effects on an initially empty stack S of integers.

Operation Output Stack Contents

push(5) - (5)
push(3) - (5, 3)
pop() 3 (5)
push(7) - (5, 7)
pop() 7 (5)
top() 5 (5)
pop() 5 ()
pop() "error“ ()
isEmpty() ()
push(9) true
push(7) - (9)
push(3) - (9, 7)
push(5) - (9, 7, 3)
size() - (9, 7, 3, 5)
pop() 4 (9, 7, 3, 5)
push(8) 5 (9, 7, 3)
pop() - (9, 7, 3, 8)
pop() 8 (9, 7, 3)
3 (9, 7)
 Exercise: Stacks

• Describe the output of the following series of stack

operations
– Push(8)
– Push(3)
– Pop()
– Push(2)
– Push(5)
– Pop()
– Pop()
– Push(9)
– Push(1)

25
Simple Uses of a Stack

Traces of the algorithm that checks for balanced braces

 Using Stacks with
Algebraic Expressions
• Evaluating postfix expressions

The effect of a postfix calculator on a stack when evaluating the

expression 2 * (3 + 4)
 Using Stacks with
Algebraic Expressions

A trace of the algorithm that converts the infix expression a – ( b + c * d ) / e to postfix form
 Parentheses Matching
• (((a+b)*c+d-e)/(f+g)-(h+j)*(k-l))/(m-n)
– Output pairs (u,v) such that the left parenthesis at
position u is matched with the right parenthesis at v.
• (2,6) (1,13) (15,19) (21,25) (27,31) (0,32) (34,38)
• (a+b))*((c+d)
– (0,4)
– right parenthesis at 5 has no matching left parenthesis
– (8,12)
– left parenthesis at 7 has no matching right parenthesis
 Parentheses Matching
• scan expression from left to right
• when a left parenthesis is encountered, add its
position to the stack
• when a right parenthesis is encountered, remove
matching position from stack
 Example
• (((a+b)*c+d-e)/(f+g)-(h+j)*(k-l))/(m-n)

2
1
0
 Example
• (((a+b)*c+d-e)/(f+g)-(h+j)*(k-l))/(m-n)

15
1
0 (2,6) (1,13)
 Example
• (((a+b)*c+d-e)/(f+g)-(h+j)*(k-l))/(m-n)

21
1
0 (2,6) (1,13) (15,19)
 Example
• (((a+b)*c+d-e)/(f+g)-(h+j)*(k-l))/(m-n)

27
1
0 (2,6) (1,13) (15,19) (21,25)
 Example
• (((a+b)*c+d-e)/(f+g)-(h+j)*(k-l))/(m-n)

1
0 (2,6) (1,13) (15,19) (21,25)(27,31) (0,32)

• and so on
Infix to Postfix Conversion
(Intuitive Algorithm)

(1) Fully parenthesized expression

a / b - c + d * e - a * c -->
((((a / b) - c) + (d * e)) – (a * c))

(2) All operators replace their corresponding right

parentheses.
((((a / b) - c) + (d * e)) – (a * c))

/ - +* -*
(3) Delete all parentheses.
ab/c-de*+ac*-
two passes
The orders of operands in infix and postfix are the same.
a+b*c

Token Stack Top Output

[0] [1] [2]
a -1 a
+ + 0 a
b + 0 ab
* + * 1 ab
c + * 1 abc
eos -1 abc*+
 a *1 (b +c) *2 d

Token Stack Top Output

[0] [1] [2]
a -1 a
*1 *1 0 a
( *1 ( 1 a
b *1 ( 1 ab
+ *1 ( + 2 ab
c *1 ( + )
match 2 abc
) *1 *1 = *2 0 abc+
*2 *2 0 abc+*1
d *2 0 abc+*1d
eos *2 0 abc+*1d*2
Example: postfix expressions
(cont.)
 Postfix expressions:
Algorithm using stacks (cont.)
 A Legend
The Towers of Hanoi
• In the great temple of Brahma in Benares, on a brass plate
under the dome that marks the center of the world, there
are 64 disks of pure gold that the priests carry one at a
time between these diamond needles according to
Brahma's immutable law: No disk may be placed on a
smaller disk. In the begging of the world all 64 disks
formed the Tower of Brahma on one needle. Now, however,
the process of transfer of the tower from one needle to
another is in mid course. When the last disk is finally in
place, once again forming the Tower of Brahma but on a
different needle, then will come the end of the world and
all will turn to dust.
 The Towers of Hanoi
A Stack-based Application

– GIVEN: three poles

– a set of discs on the first pole, discs of different sizes, the smallest
discs at the top
– GOAL: move all the discs from the left pole to the right one.
– CONDITIONS: only one disc may be moved at a time.
– A disc can be placed either on an empty pole or on top of a larger
disc.
 Towers Of Hanoi/Brahma

4
3
2
1

A B C
• 64 gold disks to be moved from tower A to tower C
• each tower operates as a stack
• cannot place big disk on top of a smaller one
 Towers Of Hanoi/Brahma

3
2
1

A B C
• 3-disk Towers Of Hanoi/Brahma
 Towers Of Hanoi/Brahma

2
1 3

A B C
• 3-disk Towers Of Hanoi/Brahma
 Towers Of Hanoi/Brahma

1 2 3

A B C
• 3-disk Towers Of Hanoi/Brahma
 Towers Of Hanoi/Brahma

3
1 2

A B C
• 3-disk Towers Of Hanoi/Brahma
 Towers Of Hanoi/Brahma

3
2 1

A B C
• 3-disk Towers Of Hanoi/Brahma
 Towers Of Hanoi/Brahma

3 2 1

A B C
• 3-disk Towers Of Hanoi/Brahma
 Towers Of Hanoi/Brahma

2
3 1

A B C
• 3-disk Towers Of Hanoi/Brahma
 Towers Of Hanoi/Brahma

3
2
1

A B C
• 3-disk Towers Of Hanoi/Brahma
• 7 disk moves
 Recursive Solution

A B C
• n > 0 gold disks to be moved from A to C using B
• move top n-1 disks from A to B using C
 Recursive Solution

A B C
• move top disk from A to C
 Recursive Solution

A B C
• move top n-1 disks from B to C using A
 Recursive Solution

A B C
• moves(n) = 0 when n = 0
• moves(n) = 2*moves(n-1) + 1 = 2n-1 when n > 0
 Towers Of Hanoi/Brahma

• moves(64) = 1.8 * 1019 (approximately)

• Performing 109 moves/second, a computer would take
about 570 years to complete.
• At 1 disk move/min, the monks will take about 3.4 * 1013
years.
 Chess Story

• 1 grain of rice on the first square, 2 for next, 4 for

next, 8 for next, and so on.
• Surface area needed exceeds surface area of earth.
 Chess Story

• 1 penny for the first square, 2 for next, 4 for next,

8 for next, and so on.
• $3.6 * 1017 (federal budget ~ $2 * 1012) .
 Switch Box Routing
1 2 3 4 5 6 7 8 9 10
40 11
39 12
38 13
37 14
36 15
Routing region
35 16
34 17
33 18
32 19
31 20
30 29 28 27 26 25 24 23 22 21
 Routing A 2-pin Net
1 2 3 4 5 6 7 8 9 10
40 11
Routing Routing
39 12 for pins
for pins
1-3 and 38 13 5
18-40 is 37 14 through
confined 16 is
36 15
to lower confined
35 16 to upper
left
region. 34 17 right
33 18 region.
32 19
31 20
30 29 28 27 26 25 24 23 22 21
 Routing A 2-pin Net
1 2 3 4 5 6 7 8 9 10
40 11
(u,v), Examine
39 12 pins in
u<v is a
2-pin 38 13 clock-
net. 37 14 wise
order
u is start 36 15
beginn-
pin. 35 16 ing with
v is end 34 17 pin 1.
pin. 33 18
32 19
31 20
30 29 28 27 26 25 24 23 22 21
 Routing A 2-pin Net
1 2 3 4 5 6 7 8 9 10
40 11
Start pin
39 12
=> push
onto 38 13
stack. 37 14

End pin 36 15
=> start 35 16
pin must 34 17
be at top
33 18
of stack.
32 19
31 20
30 29 28 27 26 25 24 23 22 21
 Method Invocation And Return
public void a()
{ …; b(); …}
public void b()
{ …; c(); …} return address in d()
public void c() return address in c()
{ …; d(); …} return address in e()
public void d() return address in d()
{ …; e(); …}
return address in c()
return address in b()
public void e()
return address in a()
{ …; c(); …}
Rat In A Maze
 Rat In A Maze

• Move order is: right, down, left, up

• Block positions to avoid revisit.
 Rat In A Maze

• Move order is: right, down, left, up

• Block positions to avoid revisit.
 Rat In A Maze

• Move backward until we reach a square from which

a forward move is possible.
 Rat In A Maze

• Move down.
 Rat In A Maze

• Move left.
 Rat In A Maze

• Move down.
 Rat In A Maze

• Move backward until we reach a square from which

a forward move is possible.
 Rat In A Maze

• Move backward until we reach a square from which

a forward move is possible.
• Move downward.
 Rat In A Maze

• Move right.
• Backtrack.
 Rat In A Maze

• Move downward.
 Rat In A Maze

• Move right.
 Rat In A Maze

• Move one down and then right.

 Rat In A Maze

• Move one up and then right.

 Rat In A Maze

• Move down to exit and eat cheese.

• Path from maze entry to current position operates as
a stack.