STACK
A stack is a data structure in which addition of new element or deletion of an existing
element always takes place at the same end. This end is known as top of the stack. When
an item is added t the stack the operation is called “push” and when an item is removed
from the stack the operation is called “pop”. Stack is also called LIFO (Last in First out)
list. If the elements are added continuously to the stack it grows at one end. On deletion
of elements the stack shrinks at the same end, as the elements at the top get removed.
For example stack of plates in cafeteria where every new plate added to the stack is added
at the top. Similarly, every new plate taken off the stack is also from the top of the stack.
top top
top 5 5 top
top 4 4 4 4 top
top
1 1 1 1 1 1 top
top= NULL 3 3 3 3 3 3 3 3 top = NULL
2 2 2 2 2 2 2 2
Push Operation Pop Operation
Push function
void push( int item)
{
if( top == MAX-1)
{
printf(“Stack is full);
return;
}
top ++;
arr[top] = item;
}
Pop function
void pop( )
{
if( top == -1)
{
printf(“Stack is emptyl);
return;
}
int data = arr[top];
top --;
return data;
}
ALGORITHM OF PUSH FUNCTION
Push(arr, top, MAX, item)
This procedure pushes an item onto a stack
1. [Stack already filled?]
if top == MAX-1 then print overflow and return
2. set top = top + 1; [increment top by 1]
3. set arr[top] = item
4. return
ALGORITHM OF POP FUNCTION
Pop(arr, top, MAX, item)
This procedure pop an item from a stack
1. [Stack is empty?]
if top == -1 then print underflow and return
2. set item = arr[top]
3. set top = top - 1; [decrement top by 1]
4. return
APPLICATIONS OF STACK
Expression Evaluation
Stack is used to evaluate prefix, postfix and infix expressions.
Expression Conversion
An expression can be represented in prefix, postfix or infix notation. Stack can be used to
convert one form of expression to another.
Syntax Parsing
Many compilers use a stack for parsing the syntax of expressions, program blocks etc.
before translating into low level code.
Backtracking
Suppose we are finding a path for solving maze problem. We choose a path and after
following it we realize that it is wrong. Now we need to go back to the beginning of the
path to start with new path. This can be done with the help of stack.
Parenthesis Checking
Stack is used to check the proper opening and closing of parenthesis.
String Reversal
Stack is used to reverse a string. We push the characters of string one by one into stack
and then pop character from stack.
Function Call
Stack is used to keep information about the active functions or subroutines.