Data Structure
Stack
Prepared by
Dalton Meitei Thounaojam
Stack
Stores the elements in an ordered manner.
Array representation of Stack
Terminology to be used :
TOP : points to the topmost element of the stack which is
given by the index of the last element in an array.
MAX : maximum number of elements a stack can hold
which is given by the size of an array.
TOP == NULL : stack is empty.
TOP == MAX - 1: stack is full.
Operation on a stack :
Push : insertion is done at the end of an array.
Pop : deletion is done at the end of an array.
Peek : print the last element of an array.
Push operation on a Stack
Step 1: IF TOP = MAX - 1
PRINT OVERFLOW
Goto Step 4
[END OF IF]
Step 2: SET TOP = TOP + 1
Step 3: SET STACK[TOP] = VALUE
Step 4: END
Pop operation on a Stack
Step 1: IF TOP = NULL
PRINT UNDERFLOW
Goto Step 4
[END OF IF]
Step 2: SET VAL = STACK[TOP]
Step 3: SET TOP = TOP - 1
Step 4: END
Peek operation on a Stack
It returns the value of the topmost element in a
stack if the stack is not empty.
Step 1: IF TOP = NULL
PRINT STACK IS EMPTY
Goto Step 3
[END OF IF]
Step 2: RETURN STACK[TOP]
Step 3: END
Link List representation of Stack
Terminology to be used :
TOP : points to the topmost element of the stack which is
given by the HEAD pointer.
MAX : maximum number of elements a stack can hold.
TOP = NULL : stack is empty.
TOP = MAX - 1: stack is full.
Operation on a stack :
Push : insertion is done at the first node.
Pop : deletion is done at the first node.
Peek : print the element of the first node.
Push operation on a Stack
Step 1: Allocate memory for the new node and name
it as NEW_NODE
Step 2: SET NEW_NODE -> DATA = VAL
Step 3: IF TOP = NULL
SET NEW_NODE -> NEXT = NULL
ELSE
SET NEW_NODE -> NEXT = TOP
[END OF IF]
Step 4: SET TOP = NEW_NODE
Step 5: END
Pop operation on a Stack
Step 1: IF TOP = NULL
PRINT UNDERFLOW
Goto Step 5
[END OF IF]
Step 2: SET PTR = TOP
Step 3: SET TOP = TOP -> NEXT
Step 4: FREE PTR
Step 5: END
Peek operation on a Stack
Step 1: IF TOP = NULL
PRINT STACK IS EMPTY
Goto Step 3
[END OF IF]
Step 2: RETURN TOP -> DATA
Step 3: END
Multiple Stacks
for better utilization of the memory space using
array.
More than one stacks in an array.
Stack A Stack B
1 2 3 20 10
TOP TOP
Fig.: Multiple Stacks
Application of a Stack
Reversing a list
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
Reversing a list using a Stack
#include<stdio.h>
#define MAX 10
int top = -1;
int stack[MAX];
int pop();
void push(int);
void main()
{
int n,i,temp, arr[MAX];
printf("Enter the number of elements. \n");
scanf("%d",&n);
for(i=0;i<n;i++)
{
Reversing a list using a Stack
printf("Enter the %d elements. \n",i);
scanf("%d",&temp);
push(temp);
}
printf("The reverse is : \n");
for(i=0;i<n;i++)
{
temp = pop();
arr[i] = temp;
}
for(i=0;i<n;i++)
{
printf("%d \t",arr[i]);
}
}
Reversing a list using a Stack
void push(int val)
{
if(top==MAX-1)
{
printf("\nThe stack is full.\n");
return 0;
}
top = top + 1;
stack[top] = val;
}
Reversing a list using a Stack
int pop()
{
int val;
if(top == -1)
{
printf("\n Stack underflow. \n");
return -1;
}
val = stack[top];
top = top - 1;
return val;
}
Reversing a list using a Stack
int pop()
{
int val;
if(top == -1)
{
printf("\n Stack underflow. \n");
return -1;
}
val = stack[top];
top = top - 1;
return val;
}
Infix, postfix and prefix notations
Infix notation:
(A+B)*C
Postfix notation:
AB+C*
Prefix notation:
*+ABC
Conversion of infix to postfix using stack
Step 1: Add “)” to the end of the infix expression
Step 2: Push “(“ on to the stack
Step 3: Repeat until each character in the infix notation is scanned
IF a “(“ is encountered, push it on the stack
IF an operand (whether a digit or a character) is encountered, add it to the
postfix expression.
IF a “)” is encountered, then
a. Repeatedly pop from stack and add it to the postfix expression
until a “(“ is encountered.
b. Discard the “(“ . That is, remove the “(“ from stack and do not
add it to the postfix expression
IF an operator 0 is encountered, then
a. Repeatedly pop from stack and add each operator (popped from
the stack) to the postfix expression which has the same
precedence or a higher precedence than
b. Push the operator 0 to the stack
Step 4: Repeatedly pop from the stack and add it to the postfix expression until the
stack is empty
Step 5: EXIT
Conversion of infix to postfix using stack
Conversion of infix to prefix using stack
Step 1: Reverse the infix string. Note that while
reversing the string you must interchange left and
right parentheses.
Step 2: Obtain the postfix expression of the infix
expression obtained in Step 1.
Step 3: Reverse the postfix expression to get the prefix
expression
Thank you
