Stacks

Objectives
Understands the concepts of stacks
Representation of stacks as data structure
Different method for implementing stacks
Application of stacks
Use of stacks in recursion problem

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).

Use of stack in Computer Science
Consider an example,
where we are executing function A.
main()
{ A()}
A()
{ B() }
B()
{C()}
C()
{D()}
D()
{E()}

Use of stack in Computer Science
In the course of its execution, function A calls another function B. Function B in turn calls another function C, which calls function D.

The system stack ensures a proper execution order of functions.
Therefore, stacks are frequently used in situations where the order of processing is very important, especially when the processing needs to be postponed until other conditions are fulfilled.

Operation on Stack
push(i) to insert the element i on the top of the stack
pop( ) to remove the top element of the stack and to return the removed element as a function value.
Top( ) to return the top element of stack(s)
empty() to check whether the stack is empty or not. It returns true if stack is empty and returns false otherwise
Stacks can be implemented using either arrays or linked lists.
Works on the principle of LIFO
LIFO – Last In First Out

ARRAY REPRESENTATION OF STACKS
In the computer’s memory, stacks can be represented as a linear array.
Every stack has a variable called TOP associated with it, which is used to store the address of the topmost element of the stack.
TOP is the position where the element will be added to or deleted from.
There is another variable called MAX, which is used to store the maximum number of elements that the stack can hold.
Underflow and Overflow
if TOP = NULL,(underflow), it indicates that the stack is empty and
if TOP = MAX–1,(overflow) then the stack is full.

Algorithm for PUSH operation

PUSH operation

LINKED REPRESENTATION OF STACK
Stack may be created using an array. This technique of creating a stack is easy, but the drawback is that the array must be declared to have some fixed size. In case the stack is a very small one or its maximum size is known in advance, then the array implementation of the stack gives an efficient implementation. But if the array size cannot be determined in advance, then the other alternative, i.e., linked representation, is used.
In a linked stack, every node has two parts—one that stores data and another that stores the address of the next node. The START pointer of the linked list is used as TOP.
All insertions and deletions are done at the node pointed by TOP.
If TOP = NULL, then it indicates that the stack is empty.
The storage requirement of linked representation of the stack with n elements is O(n), and the typical time requirement for the operations is O(1).

Algorithm for PUSH operation
of Stack implemented using Linked list

Algorithm for POP operation
of Stack implemented using Linked list

Algorithm for PUSH operation
Algorithm for POP operation

APPLICATIONS OF STACKS
Parentheses checker
Conversion of an infix expression into a postfix expression
Evaluation of a postfix expression
Conversion of an infix expression into a prefix expression
Evaluation of a prefix expression
Recursion
Tower of Hanoi

Parentheses Checker
Stacks can be used to check the validity of parentheses in any algebraic expression.
For example,
an algebraic expression is valid if for every open bracket there is a corresponding closing bracket.
For example,
the expression (A+B} is invalid
an expression {A + (B – C)} is valid

Algorithm:
Declare a character stack S.
Now traverse the expression string exp.
If the current character is a starting bracket (‘(‘ or ‘{‘ or ‘[‘) then push it to stack.
If the current character is a closing bracket (‘)’ or ‘}’ or ‘]’) then pop from stack and if the popped character is the matching starting bracket then fine else parenthesis are not balanced.
After complete traversal, if there is some starting bracket left in stack then “not balanced”

Pseudo code: Parenthesis Matching
valid = true /* assuming that the string is valid*/
s = empty stack;
while (not end of the string) {
symbol = next input string;
if (symbol = ‘(‘ || ‘[‘ || ‘{‘)
push(symbol);
if (symbol = ‘)‘ || ‘]‘ || ‘}‘)
{
if (empty (s))
valid = false;
else {
i = pop();
if ( i ! =symbol)
valid = false;
} //end of else
} // end of if
} //end of while
if (valid)
cout<< “the string is valid”;
else
cout<<( “ the string is invalid”;

Mathematical Notation Translation
prefix (polish)
postfix (reverse polish)

Mathematical Notation Translation
Infix – prefix (polish)
Infix – postfix (reverse polish)
The fundamental property of these notations is that the order in which the operations are to perform are completely determined by the positions of operator and operands in the expression. There is no need to use parenthesis to define any precedence
For example, if we have an expression
A + B * C, then first B * C will be done and the result will be added to A.
(A + B) * C, will evaluate A + B first and then the result will be multiplied with C

Conversion of an Infix Expression into a Postfix Expression
An algebraic expression may contain parentheses, operands, and operators.
For simplicity of the algorithm we assume only +, –, *, /, % operators.
The precedence of these operators can be given as follows:
Higher priority *, /, % Lower priority +, –
the order of evaluation of these operators can be changed by making use of parentheses.
For example, if we have an expression
A + B * C, then first B * C will be done and the result will be added to A.
(A + B) * C, will evaluate A + B first and then the result will be multiplied with C.

Algorithm
Infix Expression to a Postfix Expression

Example

Evaluation of a Postfix Expression

Evaluation of a Postfix Expression

Example

Infix to Prefix Expression

Step 1. Push “)” onto STACK, and add “(“ to start of the A.
Step 2. Scan A from right to left and repeat step 3 to 6 for each element of A until the STACK is empty or contain only “)”
Step 3. If an operand is encountered add it to B
Step 4. If a right parenthesis is encountered push it onto STACK
Step 5. If an operator is encountered then:
a. Repeatedly pop from STACK and add to B each operator (on the top of STACK) which has higher precedence than the operator.
b. Add operator to STACK
Step 6. If left parenthesis is encountered then
a. Repeatedly pop from the STACK and add to B (each operator on top of stack until a right parenthesis is encountered)
b. Remove the left parenthesis
Step 7. Reverse B to get prefix form
Method1- Algorithm Infix to Prefix Expression

Method2- Infix Expression to a Prefix Expression

Step 1. Push “)” onto STACK, and add “(“ to start of the A.
Step 2. Scan A from right to left and repeat step 3 to 6 for each element of A until the STACK is empty or contain only “)”
Step 3. If an operand is encountered add it to B
Step 4. If a right parenthesis is encountered push it onto STACK
Step 5. If an operator is encountered then:
a. Repeatedly pop from STACK and add to B each operator (on the top of STACK) which has higher precedence than the operator.
b. Add operator to STACK
Step 6. If left parenthesis is encountered then
a. Repeatedly pop from the STACK and add to B (each operator on top of stack until a right parenthesis is encountered)
b. Remove the left parenthesis
Step 7. Reverse B to get prefix form

Evaluation of a Prefix Expression

Example