The following are some of the applications of stack:
- Evaluating the arithmetic expressions
- Conversion of Infix to Postfix Expression
- Evaluating the Postfix Expression
- Balancing the Symbols
- Function Call
- Tower of Hanoi
- 8 Queen Problem
struct node;
typedef struct node *stack; typedef struct node *position; stack S;
struct node{ int data; position next;};
int IsEmpty(Stack S); void Push(int x, Stack S); void Pop(Stack S);
int TopElement(Stack S);
- Stack Empty Operation:
- Initially Stack is Empty.With Linked List implementation, Empty stack is represented as S -> next = NULL.
- It is necessary to check for Empty Stack before deleting ( pop) an element from the stack.
Routine to check whether the stack is empty
int IsEmpty( Stack S)
{
if ( S -> next = = NULL) return ( 1 );
}
Push Operation
- It is the process of inserting a new element at the Top of the stack.
- With Linked List implementation, a new element is always inserted at the Front of the List.(i.e.) S -> next.It takes two parameters.
- Push(X, S) the element X to be inserted at the Top of the StackS.Allocate the memory for the newnode to be inserted.Insert the element in the data field of the newnode.
- Update the next field of the newnode with the address of the next node which is stored in the S -> next.
Push routine /*Inserts element at front of the list
void push(int X, Stack S)
{
Position newnode, Top;
newnode = malloc (sizeof( struct node ) ); newnode -> data = X;
newnode -> next = S -> next; S -> next = newnode;
Top = newnode;
}
- Pop Operation
- It is the process of deleting the Top element of the stack.
- With Linked List implementations, the element at the Front of the List (i.e.) S -> next is always deleted.It takes only one parameter. Pop(X).
- The element X to be deleted from the Front of the List.Before deleting the front element in the list, check for Empty Stack.
- If the Stack is Empty, deletion is not possible.Otherwise, make the front element in the list as “temp”.Update the next field of header.
- Using free ( ) function, Deallocate the memory allocated for temp node.
- Pop routine/*Deletes the element at front of list
void Pop( Stack S )
{
Position temp, Top; Top = S -> next;
if( S -> next = = NULL)
Error(“empty stack! Pop not possible”);
else
{
Temp = S -> next;
S -> next = temp -> next; free(temp);
Top = S -> next;
} }
Return Top Element
- Pop routine deletes the Front element in the List.
- If the user needs to know the last element inserted into the stack, then the user can return the Top element of the stack.
- To do this, first check for Empty Stack.
- If the stack is empty, then there is no element in the stack.
- Otherwise, return the element present in the S -> next -> data in the List.
Routine to Return Top Element
int TopElement(Stack S)
{
if(S->next==NULL)
{
error(“Stack is empty”); return 0;
else
return S->next->data;
}
Implementation of stack using ‘Linked List’
/* Dynamic implementation of stack*/ #include<stdio.h>
#include<conio.h> #include<stdlib.h>
typedef struct node * position ; struct node
{
int data ; position next ;
} ;
void create( ) ; void push( ) ; void pop( ) ; void display( ) ;
position s, newnode, temp, top ; /* Global Declarations */ void main() {
/* Main Program */ int op ;
clrscr( ) ; do {
printf( “\n ### Linked List Implementation of STACK Operations ### \n\n” ) ; printf( “\n Press 1-create\n 2-Push\n 3-Pop\n 4-Display\n5-Exit\n” ) ;
printf( “\n Your option ? ” ) ; scanf( ” % d “, & op) ; switch (op) {
case 1:
create( ) ; break ;
case 2:
push(); break;
case 3:
pop(); break;
case 4:
display(); break;
case 5: exit(0);
}
}while(op<5);
getch();
}
void create()
{
int n,i; s=NULL;
printf(“Enter the no of nodes to be created\n”); scanf(“%d”,&n);
newnode=(struct node*)malloc(sizeof(struct node)); printf(“Enter the data\t”);
scanf(“%d”,&newnode->data); newnode->next=NULL; top=newnode;
s=newnode; for(i=2;i<=n;i++)
{
newnode=(struct node*)malloc(sizeof(struct node)); printf(“Enter the data\t”);
scanf(“%d”,&newnode->data); newnode->next=top; s=newnode;
top=newnode;
} }
void display()
{ top=s; while(top!=NULL)
{
printf(“%d->”,top->data); top=top->next;
}
printf(“NULL\n”);
}
void push()
{ top=s;
newnode=(struct node*)malloc(sizeof(struct node)); printf(“Enter the data\t”);
scanf(“%d”,&newnode->data); newnode->next=top; top=newnode;
s=newnode; display();
}
void pop()
{
top=s;
if(top==NULL) printf(“Empty stack\n\n”); else
{
temp=top;
printf(“Deleted element is \t %d\n\n”,top->data); s=top->next;
free(temp); display();
} }
Output
### Linked List Implementation of STACK Operations ### Press 1-create
2-Push 3-Pop
4-Display 5-Exit
Your option ? 1
Enter the no of nodes to be created5 Enter the data 10
Enter the data20 Enter the data30 Enter the data40 Enter the data50
### Linked List Implementation of STACK Operations ### Press 1-create
2-Push 3-Pop
4-Display 5-Exit
Your option ? 4
50->40->30->20->10->NULL
### Linked List Implementation of STACK Operations ### Press 1-create
2-Push 3-Pop
4-Display 5-Exit
Your option ?2 Enter the data60 Your option ? 4
60->50->40->30->20->10->NULL
Your option ?2 Enter the data70 Your option ? 4
70->60->50->40->30->20->10->NULL
Your option ?3 Deleted element is70 Your option ? 4
50->40->30->20->10->NULL
Applications of Stack
The following are some of the applications of stack:
1.Evaluating the arithmetic expressions
Conversion of Infix to Postfix Expression,Evaluating the Postfix Expression
2.Balancing the Symbols
3.Function Call
4.Tower of Hanoi
5.Queen Problem