Stack
Stacks are linear Data Structures which are based on the principle of
Last-In-First-Out (LIFO) where data which is entered last will be the first to
get accessed. It is built using the array structure and has operations
namely, pushing (adding) elements, popping (deleting) elements and
accessing elements only from one point in the stack called as the TOP. This
TOP is the pointer to the current position of the stack. Stacks are
prominently used in applications such as Recursive Programming, reversing
words, undo mechanisms in word editors and so forth.
LIFO Principle of Stack
In programming terms, putting an item on top of the stack is
called push and removing an item is called pop.
Stack Push and Pop Operations
In the above image, although item was kept last, it was removed first - so it
follows the Last In First Out(LIFO) principle.
Basic Operations of Stack
A stack is an object (an abstract data type - ADT) that allows the following
operations:
Push: Add an element to the top of a stack
Pop: Remove an element from the top of a stack
IsEmpty: Check if the stack is empty
IsFull: Check if the stack is full
Peek: Get the value of the top element without removing it
Algorithm for Push :
begin procedure push: stack, data
if stack is full
return null
endif
top = top + 1
stack[top] = data
end procedure
Algorithm for Pop :
begin procedure pop: stack
if stack is empty
return null
endif
data ← stack[top]
top ← top - 1
return data
end procedure
Program1: - Implemening Stack using structure in c
/*
* C program to implement Stack. Stack is a LIFO data structure.
* Stack operations: PUSH(insert operation), POP(Delete operation)
* and Display Stack.
*/
#include <stdio.h>
#include<conio.h>
#define MAX 10
struct Stack
{
int Item[MAX];
int Top;
};
/* Function to initialize stack*/
void Init(Struct Stack *p)
{
p->Top=-1;
}
/* Function to Check stack is empty*/
int IsEmpty(Struct Stack *p)
{
return p->Top==-1;
}
/* Function to Check stack is full*/
int IsFull(Struct Stack *p)
{
return p->Top==MAX-1;
}
/* Function to add an element to the Stack */
void Push(Struct Stack *p, int ele)
{
if (IsFull(p))
printf ("Stack is Full\n");
else
{
p->Top ++ ;
p->Item[p->Top] = ele;
printf("%d pushed",ele);
}
}
/* Function to delete an element from the Stack */
int Pop (Struct Stack *p)
{
int num = p->Item[p->Top];
p->Top--;
return(num);
}
/* Function to display the status of the Stack */
void Display (Struct Stack *p)
{
int i;
if (IsEmpty(p))
printf ("Stack is Empty\n");
else
{
printf ("\n The status of the Stack is \nTop ==> ");
for (i = p->Top; i >= 0; i--)
{
printf ("%d\n ", p->Item[i]);
}
}
printf ("\n");
}
void main ()
{
struct Stack S;
int n,choice;
Init(&S);
do
{ clrscr();
printf ("Stack OPERATION\n");
printf ("------------------------------------------\n");
printf (" 1 --> PUSH \n");
printf (" 2 --> POP \n");
printf (" 3 --> DISPLAY \n");
printf (" 4 --> EXIT \n");
printf ("------------------------------------------\n");
printf("Enter your choice : ");
scanf("%d", &choice);
switch (choice)
{
case 1: printf ("Enter the element to be pushed : ");
scanf ("%d", &n);
Push(&S,n);
getch(); break;
case 2: if (IsEmpty(&S))
printf ("Stack is Empty\n");
else
printf("%d Deleted",Pop(&S));
getch(); break;
case 3: Display(&S);getch();
break;
case 4: break;
default : printf("Invalid Choice");
}
}while(choice!=4);
}
Infix expression : An infix expression is an expression in which
operators (+, -, *, /) are written between the two operands. For example,
consider the expressions: A+B
Here we have written '+' operator between the operands A and B, and the -
operator in between the C and D operand.
Postfix Expression : The postfix operator also contains operator and
operands. In the postfix expression, the operator is written after the
operand. It is also known as Reverse Polish Notation. For example,
consider the expressions: AB+
Algorithm to Convert Infix to Postfix Expression Using Stack
Following is the algorithm to convert infix expression into Reverse Polish
notation.
1. Initialize the Stack.
2. Scan the Character from left to right from infix expression into “CH”.
3. If “CH” is an operand, add it to the Postfix string.
4. If “CH” is a left bracket '(', push it into the Stack.
5. If “CH” is right bracket ')',
While (X=pop( Stack)!= '(' )
add “X” to the Postfix string.
End While
6. if “CH” is the operator
While (Priority( Stack[top]) >= Priority(CH) )
X=pop( Stack)
add “X” to the Postfix string.
End While
Push “CH” to Stack
7. Repeat all steps from 2 to 8 until the infix expression is scanned.
8. While Stack is Not Empty
X=pop(Stack)
add “X” to the Postfix string.
End While
9. Display Postfix String
Infix expression ( ( A * ( B + D ) / E ) – ( F * ( G + H / K ) ) ) to
convert into its equivalent postfix expression:
CH Expression Stack
( (
( ((
A A ((
* A ((*
( A ((*(
B AB ((*(
+ AB ((*(+
D ABD ((*(+
) ABD+ ((*
/ ABD+ ((*/
E ABD+*E ((/
) ABD+*E/ (
- ABD+*E/ (-
( ABD+*E/ (-(
F ABD+*E/F (-(
* ABD+*E/F (-(*
( ABD+*E/F (-(*(
G ABD+*E/FG (-(*(
+ ABD+*E/FG (-(*(+
H ABD+*E/FGH (-(*(+
/ ABD+*E/FGH (-(*(+/
K ABD+*E/FGHK (-(*(+/
) ABD+*E/FGHK/+ (-(*
) ABD+*E/FGHK/+* (-
) ABD+*E/FGHK/+*-
Postfix Evaluation Algorithm
Assume we have a string of operands and operators, an informal, by hand
process is
1. Initialize the Stack.
2. Scan Character from left to right from postfix expression into “CH”.
3. If “CH” is an operand, push it into the Stack..
4. if “CH” is the operator
opnd2 = pop(Stack);
opnd1 = pop(Stack);
result = opnd1CH opnd2;
push result to Stack
5. Repeat all steps from 2 to 4 until the postfix expression is scanned.
Example 1: Evaluate the postfix expression: 6 2 3 + - 3 8 2 / + * 2 ^ 3 +
Prefix Expression: The postfix operator also contains operator and
operands. In the prefix expression, the operator is written before the
operand. For example, consider the expressions: +AB
Algorithm to Convert Infix to Prefix Expression Using Stack
Following is the algorithm to convert infix expression into Reverse Polish
notation.
1. Initialize the Stack.
2. Reverse Infix String. and replace ‘(’ with ‘)’ and ‘)’ with ‘(’
3. Scan the Character from left to right from infix expression into “CH”.
4. If “CH” is an operand, add it to the Prefix string.
5. If “CH” is a left bracket '(', push it into the Stack.
6. If “CH” is right bracket ')',
i. While (X=pop( Stack)!= '(' )
1. add “X” to the Prefix string.
ii. End While
7. if “CH” is the operator
i. While (Priority( Stack[top]) > Priority(CH) )
1. X=pop( Stack)
2. add “X” to the Prefix string.
ii. End While
b. Push “CH” to Stack
8. Repeat all steps from 2 to 8 until the infix expression is scanned.
9. While Stack is Not Empty
i. X=pop(Stack)
ii. add “X” to the Prefix string.
b. End While
10. Reverse and Display Prefix String
Infix expression ( ( A * ( B + D ) / E ) – ( F * ( G + H / K ) ) ) to
convert into its equivalent prefix expression:
Reverse Of Infix : ) ) ) K / H + G ( * F ( - ) E / ) D + B ( * A ( (
Modified Expression: ( ( ( K / H + G ) * F ) - ( E / ( D + B ) * A ) )
CH Expression Stack
( (
( ((
( (((
K K (((
/ K (((/
H KH (((/
+ KH/ (((+
G KH/G (((+
) KH/G+ ((
* KH/G+ ((*
F KH/G+F ((*
) KH/G+F* (
- KH/G+F* (-
( KH/G+F* (-(
E KH/G+F*E (-(
/ KH/G+F*E (-(/
( KH/G+F*E (-(/(
D KH/G+F*ED (-(/(
+ KH/G+F*ED (-(/(+
B KH/G+F*EDB (-(/(+
) KH/G+F*EDB+ (-(/
* KH/G+F*EDB+ (-(/*
A KH/G+F*EDB+A (-(/*
) KH/G+F*EDB+A*/ (-
) KH/G+F*EDB+A*/- Empty
-/*A+BDE*F+G/HK Reverse and Display
Expression
Algorithm for Prefix to Infix:
Read the Prefix expression in reverse order (from right to left)
If the symbol is an operand, then push it onto the Stack
If the symbol is an operator, then pop two operands from the Stack
Create a string by concatenating the two operands and the operator
between them.
string = (operand1 operator operand2)
And push the resultant string back to Stack
Repeat the above steps until end of Prefix expression.
Prefix Expression: -/*A+BDE*F+G/HK
CH Expression Stack
K K
H KH
/ (H/K) (H/K)
G (H/K),G
+ G+(H/K) G+(H/K)
F G+(H/K),F
* F*(G+(H/K)) F*(G+(H/K))
E F*(G+(H/K)),E
D F*(G+(H/K)),E,D
B F*(G+(H/K)),E D,B
+ (B+D) F*(G+(H/K)),E,(B+D)
A F*(G+(H/K)),E,( B+D),A
* A*( B+D), F*(G+(H/K)),E,( A*( B+D))
/ ( A*( B+D))/E F*(G+(H/K)),( ( A*( B+D))/E)
- ( ( A*( B+D))/E)- F*(G+(H/K)) ( ( A*( B+D))/E)- F*(G+(H/K))
Infix : ( ( A*( B+D))/E)- F*(G+(H/K))
Stack applications in data structure
Stacks can be used for expression evaluation.
Stacks can be used to check parenthesis matching in an expression.
Stacks can be used for Conversion from one form of expression to
another.
Stacks can be used for Memory Management.
Stack data structures are used in backtracking problems.
/* program to implement Infix to Postfix Using Stack. */
#include<stdio.h>
#include<conio.h>
#define MAX 30
struct Stack
{
char Item[MAX];
int Top;
};
/* Function to initialize stack*/
void Init(Struct Stack *p)
{
p->Top=-1;
}
/* Function to Check stack is empty*/
int IsEmpty(Struct Stack *p)
{
return p->Top==-1;
}
/* Function to Check stack is full*/
int IsFull(Struct Stack *p)
{
return p->Top==MAX-1;
}
/* Function to add an element to the Stack */
void Push(Struct Stack *p,char ele)
{
if (p->Top == MAX-1)
printf ("Stack is Full\n");
else
{
p->Top ++ ;
p->Item[p->Top] = ele;
}
}
/* Function to delete an element from the Stack */
char Pop (Struct Stack *p)
{
char num;
if (IsEmpty(p))
printf ("Stack is Empty\n");
else
{
num = p->Item[p->Top];
p->Top--;
}
return(num);
}
int IsOperator(char c)
{
if(c=='+'||c=='-'||c=='*'||c=='/'||c=='^')
return 1;
else
return 0;
}
int Priority(char c)
{
if(c=='^')
return 3;
else if(c=='*'||c=='/')
return 2;
else if(c=='+'||c=='-')
return 1;
else
return 0;
}
void main ()
{
struct Stack S;
char Infix[30],ch,ans;
int i,j;
do
{
Init(&S);
char Postfix[30];j=-1;
clrscr();
printf("Infix String :");
scanf("%s",&Infix);
for(i=0;Infix[i]!='\0';i++)
{
ch=Infix[i];
if(ch=='(')
Push(&S,ch);
else if(IsOperator(ch))
{
while(Priority(S.Item[S.Top])>=Priority(ch))
{
//printf("%c",Pop(&S));
Postfix[++j]=Pop(&S);
}
Push(&S,ch);
}
else if(ch==')')
{
while(S.Item[S.Top]!='(')
{
//printf("%c",Pop(&S));
Postfix[++j]=Pop(&S);
}
Pop(&S);
}
else
//printf("%c",ch);
Postfix[++j]=ch;
}
while( !IsEmpty(&S))
{
//printf("%c",Pop(&S));
Postfix[++j]=Pop(&S);
}
Postfix[++j]='\0';
printf("\nPostfix Notation = %s",Postfix);
printf("\n Press Y to COntinue...");
scanf("%s",&ans);
}while(ans=='y'||ans=='Y');
}
/* program Evaution of Postfix Using Stack. */
#include<stdio.h>
#include<conio.h>
#include<math.h>
#define MAX 30
struct Stack
{
int Item[MAX];
int Top;
};
/* Function to initialize stack*/
void Init(Struct Stack *p)
{
p->Top=-1;
}
/* Function to Check stack is empty*/
int IsEmpty(Struct Stack *p)
{
return p->Top==-1;
}
/* Function to Check stack is full*/
int IsFull(Struct Stack *p)
{
return p->Top==MAX-1;
}
/* Function to add an element to the Stack */
void Push(Struct Stack *p,int ele)
{
if (p->Top == MAX-1)
printf ("Stack is Full\n");
else
{
p->Top ++ ;
p->Item[p->Top] = ele;
}
}
/* Function to delete an element from the Stack */
int Pop (Struct Stack *p)
{
int num;
if (IsEmpty(p))
printf ("Stack is Empty\n");
else
{
num = p->Item[p->Top];
p->Top--;
}
return(num);
}
int IsOperator(char c)
{
if(c=='+'||c=='-'||c=='*'||c=='/'||c=='^')
return 1;
else
return 0;
}
void main ()
{
struct Stack S;
char Postfix[30],ch,ans;
int exp,op1,op2,i;
Init(&S);
do
{
clrscr();
printf("Postfix String :");
scanf("%s",&Postfix);
printf("\nInfix String = ");
for(i=0;Postfix[i]!='\0';i++)
{
ch=Postfix[i];
if(IsOperator(ch))
{
op2=Pop(&S);
op1=Pop(&S);
switch(ch)
{
case '+': exp=op1+op2; break;
case '-': exp=op1-op2; break;
case '*': exp=op1*op2; break;
case '/': exp=op1/op2; break;
case '^': exp=pow(op1,op2); break;
}
Push(&S,exp);
}
else
Push(&S,ch-48);
}
printf("%d",Pop(&S));
printf("\n Press Y to Continue...");
scanf("%s",&ans);
}while(ans=='y'||ans=='Y');
}
/* program to implement Infix to Prefix Using Stack. */
#include<stdio.h>
#include<conio.h>
#include<string.h>
#define MAX 30
struct Stack
{
char Item[MAX];
int Top;
};
/* Function to initialize stack*/
void Init(Struct Stack *p)
{
p->Top=-1;
}
/* Function to Check stack is empty*/
int IsEmpty(Struct Stack *p)
{
return p->Top==-1;
}
/* Function to Check stack is full*/
int IsFull(Struct Stack *p)
{
return p->Top==MAX-1;
}
/* Function to add an element to the Stack */
void Push(Struct Stack *p,char ele)
{
if (p->Top == MAX-1)
printf ("Stack is Full\n");
else
{
p->Top ++ ;
p->Item[p->Top] = ele;
}
}
/* Function to delete an element from the Stack */
char Pop (Struct Stack *p)
{
char num;
if (IsEmpty(p))
printf ("Stack is Empty\n");
else
{
num = p->Item[p->Top];
p->Top--;
}
return(num);
}
int IsOperator(char c)
{
if(c=='+'||c=='-'||c=='*'||c=='/'||c=='^')
return 1;
else
return 0;
}
int Priority(char c)
{
if(c=='^')
return 3;
else if(c=='*'||c=='/')
return 2;
else if(c=='+'||c=='-')
return 1;
else
return 0;
}
void main ()
{
struct Stack S;
char Infix[30],ch,ans;
int i,j;
do
{
Init(&S);
char Prefix[30];j=-1;
clrscr();
printf("Infix String :");
scanf("%s",&Infix);
strrev(Infix);
for(i=0;Infix[i]!='\0';i++)
{
ch=Infix[i];
if(ch==')')
Push(&S,ch);
else if(IsOperator(ch))
{
while(Priority(S.Item[S.Top])>Priority(ch))
{
//printf("%c",Pop(&S));
Prefix[++j]=Pop(&S);
}
Push(&S,ch);
}
else if(ch=='(')
{
while(S.Item[S.Top]!=')')
{
//printf("%c",Pop(&S));
Prefix[++j]=Pop(&S);
}
Pop(&S);
}
else
//printf("%c",ch);
Prefix[++j]=ch;
}
while( !IsEmpty(&S))
{
//printf("%c",Pop(&S));
Prefix[++j]=Pop(&S);
}
Prefix[++j]='\0';
printf("\nPrefix Notation = %s",strrev(Prefix));
printf("\n Press Y to COntinue...");
scanf("%s",&ans);
}while(ans=='y'||ans=='Y');
}
/* Implementing Stack using Object oriented concept in c++*/
#include <stdio.h>
#include<conio.h>
#define MAX 10
class Stack
{
int Item[MAX];
int Top;
public :
/* Function to initialize stack*/
void Init()
{
Top=-1;
}
/* Function to Check stack is empty*/
int IsEmpty()
{
return Top==-1;
}
/* Function to Check stack is full*/
int IsFull()
{
return Top==MAX-1;
}
/* Function to add an element to the Stack */
void Push(int ele)
{
if (IsFull())
printf ("Stack is Full\n");
else
{
Top ++ ;
Item[Top] = ele;
printf("%d pushed",ele);
}
}
/* Function to delete an element from the Stack */
int Pop ()
{
int num = Item[Top];
Top--;
return(num);
}
/* Function to display the status of the Stack */
void Display () ;
};
void Stack :: Display ()
{
int i;
if (IsEmpty())
printf ("Stack is Empty\n");
else
{
printf ("\n The status of the Stack is \nTop ==> ");
for (i = Top; i >= 0; i--)
{
printf ("%d\n ", Item[i]);
}
}
printf ("\n");
}
void main ()
{
Stack S;
int n,choice;
S.Init();
do
{
clrscr();
printf ("Stack OPERATION\n");
printf ("------------------------------------------\n");
printf (" 1 --> PUSH \n");
printf (" 2 --> POP \n");
printf (" 3 --> DISPLAY \n");
printf (" 4 --> EXIT \n");
printf ("------------------------------------------\n");
printf("Enter your choice : ");
scanf("%d", &choice);
switch (choice)
{
case 1: printf ("Enter the element to be pushed : ");
scanf ("%d", &n);
S.Push(n);
getch(); break;
case 2: if (S.IsEmpty())
printf ("Stack is Empty\n");
else
printf("%d Deleted",S.Pop());
getch(); break;
case 3: S.Display();getch();
break;
case 4: break;
default : printf("Invalid Choice");
}
}while(choice!=4);
}
