Stacks

1
 Introduction to Stacks
●Consider a card game with a discard pile
− Discards always placed on the top of the pile
− Players may retrieve a card only from the top

What
Whatother
other examples
examplescan can
you
youthink
think of
ofthat
thatare
are
modeled
modeledby byaastack?
stack?

●We seek a way to represent and manipulate this in a

computer program
●This is a stack

2
 Introduction to Stacks

●A stack is a last-in-first-out (LIFO) data structure

●Adding an item
− Referred to as pushing it onto the stack
●Removing an item
− Referred to as
popping it from
the stack

3
 A Stack
●Definition:
− An ordered collection of data items
− Can be accessed at only one end (the top)
●Operations:
− construct a stack (usually empty)
− check if it is empty
− Push: add an element to the top
− Top: retrieve the top element
− Pop: remove the top element

4
A Conceptual View of a Stack

Adding an Element Removing an Element

Top of
Stack

5
 Uses of Stacks
The runtime stack used by a
process (running program) to
keep track of methods in
progress
Search problems
Undo, redo, back, forward

6
Examples

7
 Basic Operations on a Stack
isFullStack: Checks whether the stack is full. If full,
it returns true; otherwise, it returns false

push:
Add new element to the top of the stack
The input consists of the stack and the new element.
Prior to this operation, the stack must exist and must not be
full

8
Stack Push Operation

9
 Basic Operations on a Stack
top: Returns the top element of the stack.
Prior to this operation, the stack must exist
and must not be empty.

pop: Removes the top element of the stack.

Prior to this operation, the stack must exist
and must not be empty.

10
Stack Pop Operation

11
Stack Top Operation

12
13
 Representing Stacks in C
#define stacksize 100
struct stack
{
int top;
int items[stacksize];
};

14
 Applications of Stack
1. Polish Notation
2. Recursion
3. Reversing Data
4. Backtracking

15
 Polish Notation
Operators are either before, between or after
their operands:
before → prefix
after → postfix
Note:
between → infix

16
 Examples
a×b
prefix → × a b
postfix → a b ×
infix → a × b Note:
Prefix and Postfix are not
mirror to each other
a+b×c
prefix → + a × b c
postfix → a b c × +

17
Prefix – Polish notation
Postfix – Reverse polish notation
■ Change the following expression to
a) Reverse Polish notation
b) Polish notations
3 + (4 + 6 × 2) × ((8 – 3) × (2 - 5) + 4) – 2 × 6

a) Reverse Polish Notation:

3 4 6 2 × + 8 3 – 2 5 – × 4 + × + 2 6 × –

b) Polish Notation:

– + 3 × + 4 × 6 2 + × – 8 3 – 2 5 4 × 2 6

18
 Converting Infix to Postfix with Stack
■Read expression from Left-to-Right and

■if an operand is read copy it to the output,

■if operator is '(' then push it into the stack,
■If operator is ')' then pop the stack until '(' is not found. When
that occurs, both parentheses are discarded,
■if an operator is read and has a higher precedence than the
operator at the top of the stack, the operator being read is
pushed onto the stack,
■while the precedence of the operator being read is lower than
or equal to the precedence of the operator at the top of the
stack, the operator at the top of the stack is popped and
copied to the output,
■when reached the end of the expression, the remaining
operators in the stack are popped and copied to the output.

19
Infix to postfix conversion

infixVect
(a+b-c)*d–(e+f)

postfixVect

20
 Infix to postfix conversion
stackVect

infixVect
a+b-c)*d–(e+f)

postfixVect

21
 Infix to postfix conversion
stackVect

infixVect
+b-c)*d–(e+f)

postfixVect
a

22
 Infix to postfix conversion
stackVect

infixVect
b-c)*d–(e+f)

postfixVect
a

+
(

23
 Infix to postfix conversion
stackVect

infixVect
-c)*d–(e+f)

postfixVect
ab

+
(

24
 Infix to postfix conversion
stackVect

infixVect
c)*d–(e+f)

postfixVect
ab+

-
(

25
 Infix to postfix conversion
stackVect

infixVect
)*d–(e+f)

postfixVect
ab+c

-
(

26
 Infix to postfix conversion
stackVect

infixVect
*d–(e+f)

postfixVect
ab+c-

27
 Infix to postfix conversion
stackVect

infixVect
d–(e+f)

postfixVect
ab+c-

28
 Infix to postfix conversion
stackVect

infixVect
–(e+f)

postfixVect
ab+c-d

29
 Infix to postfix conversion
stackVect

infixVect
(e+f)

postfixVect
ab+c–d*

30
 Infix to postfix conversion
stackVect

infixVect
e+f)

postfixVect
ab+c–d*

(
-

31
 Infix to postfix conversion
stackVect

infixVect
+f)

postfixVect
ab+c–d*e

(
-

32
 Infix to postfix conversion
stackVect

infixVect
f)

postfixVect

+ ab+c–d*e

(
-

33
 Infix to postfix conversion
stackVect

infixVect
)

postfixVect

+ ab+c–d*ef

(
-

34
 Infix to postfix conversion
stackVect

infixVect

postfixVect
ab+c–d*ef+

35
 Infix to postfix conversion
stackVect

infixVect

postfixVect
ab+c–d*ef+-

36
 Example- Infix to Postfix

Input: 4 * (2 – (6 * 3 + 4) * 2) + 1
Output: 4 2 6 3 * 4 + 2 * – * 1 +

* +
( ( *
– – –
( ( (
+
* * * *

37
 Converting Infix to Prefix with Stack
■Read expression from Right-to-Left and
■if an operand is read copy it to the LEFT of the output,
■if a right parenthesis is read push it into the stack,
■when a left parenthesis is encountered, the operator at the top of
the stack is popped off the stack and copied to the LEFT of the
output until the symbol at the top of the stack is a right
parenthesis. When that occurs, both parentheses are discarded,
■if an operator is scanned and has a higher or equal precedence
than the operator at the top of the stack, the operator being
scanned is pushed onto the stack,
■while the precedence of the operator being scanned is lower than
to the precedence of the operator at the top of the stack, the
operator at the top of the stack is popped and copied to the LEFT
of the output,
■when the end of the expression is reached on the input scan, the
remaining operators in the stack are popped and copied to the
LEFT of the output.

38
Polish Notation
Converting Infix to Prefix with Stack
■Read expression from Right-to-Left and

■if an operand is read copy it to the LEFT of the output,

■if a right parenthesis is read push it into the stack,
■when a left parenthesis is encountered, the operator at the top of the
stack is popped off the stack and copied to the LEFT of the output until
the symbol at the top of the stack is a right parenthesis. When that
occurs, both parentheses are discarded,
■if an operator is scanned and has a higher or equal precedence than
the operator at the top of the stack, the operator being scanned is
pushed onto the stack,
■while the precedence of the operator being scanned is lower than to
the precedence of the operator at the top of the stack, the operator at
the top of the stack is popped and copied to the LEFT of the output,
■when the end of the expression is reached on the input scan, the
remaining operators in the stack are popped and copied to the LEFT of
the output.

39
 Example

Input: 4 * (2 – (6 * 3 + 4) * 2) + 1
Output: + * 4 – 2 * + * 6 3 4 2 1

*
+
)
* * –
) ) ) *
+ + + +

40
 Exercises
■Using stack diagrams convert the following
expressions into postfix and prefix forms of polish
notation:
a) 8–3×4+2
b) 8 – 3 × (4 + 2)
c) (8 – 3) × (4 + 2)
d) (8 – 3) × 4 + 2
e) (a + b) × (c + a) – 5

41
Evaluation of Reverse Polish Expressions
Most compilers use the polish form to translate
expressions into machine language.

Evaluation is done using a stack data-structure

Read expression from left to right and build the stack of numbers
(operands).
When an operator is read two operands are popped out of the
stack they are evaluated with the operator and the result is
pushed into the stack.
At the end of the expression there must be only one operand into
the stack (the solution) otherwise ERROR.

42
 3 4 6 2 × + 8 3 – 2 5 – × 4 + × + 2 6 × –
6× 4 + 12 8–3 5 2–5
2 2 3 2
6 12 8 5
4 4 16 16
3 3 3 3

5 × (- -15 + 4 16 × (-
-3
3) 4
11)
5 -15 -11
16 16 16
3 3 3

3 + (-176) 2× -173 – 12
6
6
-176 2 12
3 -173 -173
43
Result = -185
 Evaluation of Polish Expressions

Evaluation is done using a stack data-structure

Read expression from right to left and build the stack of
numbers (operands).
When an operator is read two operands are popped out
of the stack they are evaluated with the operator and the
result is pushed into the stack.
At the end of the expression there must be only one
operand into the stack (the solution) otherwise ERROR.

44
 – × 3 – 8 × 3 2 – ~ 4 – 6 2

6–2 -4 -4 – 4 3×
2
3
6 4 -4 2
2 4 4 -8

8–6 3× 6 – (-8)
2
8 3
6 2 6
-8 -8 -8 Result = 14

45
Recursion
What’s behind this function ?

public int f(int a){

if (a==1)
return(1);
else
return(a * f( a-1));
}

It computes f! (factorial)
46
 Factorial
Factorial:
a! = 1 * 2 * 3 * ... * (a-1) * a
Note:
a! = a * (a-1)!
remember:
...splitting up the problem into a smaller problem of the same type...

a!
a * (a-1)!

47
 Tracing the example
public int factorial(int a){
if (a==0)
return(1);
else
RECURSION !
return(a * factorial( a-1));
}

48
 Watching the Stack
public int factorial(int a){
if (a==1)
return(1);
else
return(a * factorial( a-1));
}

a=1
Return to
L4
a=2
Return to
L4
a=3
Return to
L4
a=4 a=4
Return to Return to
L4 L4
a=5 a=5 … a=5

Initial After 1 recursion After 4th recursion

Every call to the method creates a new set of local

variables ! 49
 Watching the Stack
public int factorial(int a){
if (a==1)
return(1);
else
return(a * factorial( a-1));
}

a=1
Return to
L4
a=2 a = 2*1 = 2
Return to Return to
L4 L4
a=3 a=3 a = 3*2 = 6
Return to Return to Return to
L4 L4 L4 a = 4*6 =
a=4 a=4 a=4
Return to Return to Return to 24 to
Return
L4 L4 L4 L4
a=5 a=5 a=5 a=5 a = 5*24 = 120

After 4th recursion Result

50