Bonga University
Department of Computer Science
Data structures and Algorithms
Chapter 3 Hand-out – Stacks
STACK :
“A stack is an ordered list in which all insertions and deletions are made at one end, called the
top”. stacks are sometimes referred to as Last In First Out (LIFO) lists
Stacks have some useful terminology associated with them:
Push To add an element to the stack
Pop To remove an element from the stock
LIFO Refers to the last in, first out behavior of the stack
FILO Refers to the first in, last out Equivalent to LIFO
Initial Stack Push(8) Pop
TOS=> 8
TOS=> 4 4 TOS=> 4
1 1 1
3 3 3
6 6 6
Implementation:
Stacks can be implemented both as an array (contiguous list) and as a linked list. We want a set
of operations that will work with either type of implementation: i.e. the method of
implementation is hidden and can be changed without affecting the programs that use them.
The Basic Operations:
Push()
{
if there is room {
put an item on the top of the stack
Prepared by Department of Computer Science
Page 1
else
give an error message
}
}
Pop()
{
if stack not empty {
return the value of the top item
remove the top item from the stack
}
else {
give an error message
}
}
3.1. Array Implementation of Stacks: The PUSH operation
Here, as you might have noticed, addition of an element is known as the PUSH operation. So, if
an array is given to you, which is supposed to act as a STACK, you know that it has to be a
STATIC Stack; meaning, data will overflow if you cross the upper limit of the array. So, keep this
in mind.
Algorithm:
Step-1: Increment the Stack TOP by 1. Check whether it is always less than the Upper Limit of
the stack. If it is less than the Upper Limit go to step-2 else report -"Stack Overflow"
Step-2: Put the new element at the position pointed by the TOP
Implementation:
int stack[UPPERLIMIT];
int top= -1; /*stack is empty*/
..
..
main()
{
..
..
push(item);
..
..
}
Prepared by Department of Computer Science
Page 2
push(int item)
{
top = top + 1;
if(top < UPPERLIMIT)
stack[top] = item; /*step-1 & 2*/
else
cout<<"Stack Overflow";
}
Note:- In array implementation, we have taken TOP = -1 to signify the empty stack, as this
simplifies the implementation.
3.2. Array Implementation of Stacks: the POP operation
POP is the synonym for delete when it comes to Stack. So, if you're taking an array as the stack,
remember that you'll return an error message, "Stack underflow", if an attempt is made to Pop
an item from an empty Stack.
Algorithm
Step-1: If the Stack is empty then give the alert "Stack underflow" and quit; or else go to step-2
Step-2: a) Hold the value for the element pointed by the TOP
b) Put a NULL value instead
c) Decrement the TOP by 1
Implementation:
int stack[UPPPERLIMIT];
int top=-1;
..
..
main()
{
..
..
poped_val = pop();
..
..
}
int pop()
{
int del_val ;
if(top == -1)
Prepared by Department of Computer Science
Page 3
cout<<"Stack underflow"; /*step-1*/
else
{
del_val = stack[top]; /*step-2*/
stack[top] = NULL;
top = top -1;
}
return(del_val);
}
Note: - Step-2 :( b) signifies that the respective element has been deleted.
3.3. Applications of Stacks
3.3.1. Evaluation of Algebraic Expressions
e.g. 4 + 5 * 5
simple calculator: 45
scientific calculator: 29 (correct)
Question:
Can we develop a method of evaluating arithmetic expressions without having to ‘look
ahead’ or ‘look back’? ie consider the quadratic formula:
x = (-b+(b^2-4*a*c)^0.5)/(2*a)
where ^ is the power operator, or, as you may remember it :
In it’s current form we cannot solve the formula without considering the ordering of the
parentheses. i.e. we solve the innermost parenthesis first and then work outwards also
considering operator precedence. Although we do this naturally, consider developing an
algorithm to do the same . . . . . . Possible but complex and inefficient. Instead . . . .
Re-expressing the Expression
Computers solve arithmetic expressions by restructuring them so the order of each calculation
is embedded in the expression. Once converted an expression can then be solved in one pass.
Types of Expression
Prepared by Department of Computer Science
Page 4
The normal (or human) way of expressing mathematical expressions is called infix form, e.g.
4+5*5. However, there are other ways of representing the same expression, either by writing all
operators before their operands or after them,
e.g.: 4 5 5 * +
+4*55
This method is called Polish Notation (because this method was discovered by the Polish
mathematician Jan Lukasiewicz).
When the operators are written before their operands, it is called the prefix form
e.g. + 4 * 5 5
When the operators come after their operands, it is called postfix form (suffix form or reverse
polish notation)
e.g. 4 5 5 * +
The valuable aspect of RPN (Reverse Polish Notation or postfix)
Parentheses are unnecessary
Easy for a computer (compiler) to evaluate an arithmetic expression
Postfix (Reverse Polish Notation)
Postfix notation arises from the concept of post-order traversal of an expression tree (see - this
concept will be covered when we look at trees).
For now, consider postfix notation as a way of redistributing operators in an expression so that
their operation is delayed until the correct time.
Consider again the quadratic formula:
x = (-b+(b^2-4*a*c)^0.5)/(2*a)
In postfix form the formula becomes:
x b @ b 2 ^ 4 a * c * - 0.5 ^ + 2 a * / =
where @ represents the unary - operator.
Notice the order of the operands remain the same but the operands are redistributed in a non-
obvious way (an algorithm to convert infix to postfix can be derived).
Purpose
Prepared by Department of Computer Science
Page 5
The reason for using postfix notation is that a fairly simple algorithm exists to evaluate such
expressions on using a stack.
Postfix Evaluation
Consider the postfix expression :
6523+8*+3+*
Algorithm
initialise stack to empty;
while (not end of postfix expression) {
get next postfix item;
if(item is value)
push it onto the stack;
else if(item is binary operator) {
pop the stack to x;
pop the stack to y;
perform y operator x;
push the results onto the stack;
} else if (item is unary operator) {
pop the stack to x;
perform operator(x);
push the results onto the stack
}
}
The single value on the stack is the desired result.
Binary operators: +, -, *, /, etc.,
Unary operators: unary minus, square root, sin, cos, exp, etc.,
So for 6 5 2 3 + 8 * + 3 + *
The first item is a value (6) so it is pushed onto the stack
the next item is a value (5) so it is pushed onto the stack
the next item is a value (2) so it is pushed onto the stack
the next item is a value (3) so it is pushed onto the stack and the stack becomes
TOS=> 3
Prepared by Department of Computer Science
Page 6
5
the remaining items are now: + 8 * + 3 + *
So next a '+' is read (a binary operator), so 3 and 2 are popped from the stack and their
sum '5' is pushed onto the stack:
TOS=> 5
Next 8 is pushed and the next item is the operator *:
TOS=>
8
5 TOS=>
40
5 5
6 6
(8, 5 popped, 40 pushed)
Next the operator + followed by 3:
Prepared by Department of Computer Science
Page 7
TOS=>3
TOS=>
45 45
6 6
(40, 5 popped, 45 pushed, 3
pushed)
Next is operator +, so 3 and 45 are popped and 45+3=48 is pushed
TOS=> 48
Next is operator *, so 48 and 6 are popped, and 6*48=288 is pushed
TOS=> 288
Prepared by Department of Computer Science
Page 8
Now there are no more items and there is a single value on the stack, representing the final
answer 288.
Note the answer was found with a single traversal of the postfix expression, with the stack
being used as a kind of memory storing values that are waiting for their operands.
3.3.2. Infix to Postfix (RPN) Conversion
Of course postfix notation is of little use unless there is an easy method to convert standard
(infix) expressions to postfix. Again a simple algorithm exists that uses a stack:
Algorithm
initialise stack and postfix output to empty;
while(not end of infix expression) {
get next infix item
if(item is value) append item to pfix o/p
else if(item == ‘(‘) push item onto stack
else if(item == ‘)’) {
pop stack to x
while(x != ‘(‘)
app.x to pfix o/p & pop stack to x
} else {
while(precedence(stack top) >= precedence(item))
pop stack to x & app.x to pfix o/p
push item onto stack
}
}
while(stack not empty)
pop stack to x and append x to pfix o/p
Operator Precedence (for this algorithm):
4 : ‘(‘ - only popped if a matching ‘)’ is found
3 : All unary operators
2:/*
1:+-
The algorithm immediately passes values (operands) to the postfix expression, but remembers
(saves) operators on the stack until their right-hand operands are fully translated.
eg., consider the infix expression a+b*c+(d*e+f)*g
Prepared by Department of Computer Science
Page 9
Stack Output
ab
TOS=> +
TOS=> * abc
abc*+
TOS=> +
TOS=> *
abc*+de
(
TOS=> +
abc*+de*f
(
abc*+de*f+
Prepared by Department of Computer Science
Page 10
+
TOS=>
TOS=> * abc*+de*f+g
empty abc*+de*f+g*+
Prepared by Department of Computer Science
Page 11
