The program is about to insert/ push an element in the stack by using linked list.
Linked list are the special type of data element usually structure that contain a reference to the data of its same type. So it is called self referential structure.
In addition to another data type linked list contains a pointer to a data type linked list contains a pointer to a data that is the same type of as that of the structure.
With the help of this pointer data elements links to one another.
struct link_list
{
Int data;
Struct link_list *next;
} L;
Types of linked list :-
There are various type of linked list :-
· Singly linked list
· Doubly linked list
· Circular singly linked list
· Circular doubly linked list
Stack is a linear data structure which uses the same principle that means, the elements in the stack are added or remove only from the one end which is called top. A stack is called a LIFO list, that means last in first out. In LIFO that element of that one inserted last is the first one to be taken out.
Stack is implemented in computer memory by tow variables:-
· TOP:- It is used to store the address of the top most elements of stack. Top is the position from where the elements are deleted or added.
· MAX:-This variable is used to store maximum variable that the stack can store.
If(TOP==NULL) then it indicates the stack is empty.
If(TOP==MAX-1)then the stack is full so in stack.
Implementation of stack can be done into two ways:-
· Array representation of stack
· Linked list representation of stack
This programme is implemented by linked list.
Linkedlist representation of stack :-
In the computer memory stack can be represented as the linear linked list . Every stack has a variable which is called top and which is used to store address of the top most element of the stack. Top is the position where the elements will be added to or deleted form.The another variable. Memory is also use will stack which stored the maximum number of elements that a stack can hold. IF top ==NULL that means stack is empty and IF top=max-1 that means stack is full.
Types of basic operation in stack:-
· PUSH:-The push operation is used to insert an element to the stack, always new elements is added at tgr top most position of the stack before inserting any value in the stack we must first check if top=NULL, then we allocate memory for newnode, store the value in the data part and set NULL at the next part, now the newnode os called top.
Algorithm:-
Step 1:- if top=max-1
Print overflow
Go to step 5
[end of if]
Step 2:- if top==NULL
Step 3:- allocate memory for newnode
Step 4:- set newnode->data =val
Set newnode->next=NULL
Set top=newnode
Else
Set newnode->next=top
Top=newnode
[end of if]
Step 5:-exit.
· Pop:-The pop operation is used to delete the top most element from the stack but before deleting the value, we must check if top==NULL then print a message of underflowthat means no more element can be deleted because stack becomes empty.
Algorithm:-
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:- exit
· PEEK:- It is an operation that returns the value of top most elements of the stack without deleting it from the stack.
Algorithm:-
Step 1:- if top==NULL
Print stack is empty
Goto step 3
[end of if]
Step 2:- else
Print top->data
Step 3:- exit.
· Program starts with the header file #include<stdio. h>, #include<conio.h>. Then we define structure list by using keyword typedef struct list, in that we define node one is data part and second is the pointer fir storing address by two variables data of int type and *next of struct list type . Then we define *top which is equal to NULL of node type. Thenwe write function prototype in which the program is based on. There are 4
functions:-
· Push:- To push the elements in stack of void type with two arguments st and val.
· Pop:- To delete the last element in stack of int type with one argument st.
· Pep:-To know the last element if stack of int type with one argument st.
· Display :- To display the stack of void type with one argument st.
Then the main() starts which is called the driver of all the functions. In the main() we first declare two variables option, val of int type, then we use clrscr() which is use to clear the console. Our program is menu driven program. Firstly we print the messages for user convince. Then we start our program by writing switch() keyword and passing option in that. We define case 1 for pushing the value in stack by using push(), case 2to pop up the value by using pop(), case 3to pep the value by using pep(), case 4 to display the values by using display() and at last case 5 to exit. And then our loop ends if the condition is goes false.
Then we write the function definitions :-
· Firstly we write the push() definition. To push the elementsin the stack.
· Then we write the pop() definition. To pop the elements from the stack.
· Then we write the pep() definition. To pep the value from the stack.
· Then we write the display() definition. To display all the elements present in the stack.
PROGRAM
Stack implementation using linked list
#include<conio.h>
#include<stdio.h>
typedef struct list
{
int data ;
struct list *next;
}node;
node*top=NULL;
node*push(node*,int);
node*pop(node*);
int peep(node*);
node*display(node*);
void main()
{
int option ,val;
clrscr();
do{
printf("\n main menu\n");
printf("\n1:PUSH\n");
printf("\n2:POP\n");
printf("\n3:PEEP\n");
printf("\n4:DISPLAY");
printf("\n5:EXIT");
printf("\nenter your option: ");
scanf("%d",&option);
switch(option)
{
case 1: printf("\n enter value to insert in stack\n");
scanf("%d",&val);
top=push(top,val);
// printf("%d inserted value" ,val);
break;
case 2: top=pop(top);
break;
case 4:top=display(top);
break;
case 3:val=peep(top);
if(val!=1)
printf("\n the value on the top of stack is %d",val);
else
printf("\n stack is empty");
break;
case 5:exit(0);
default :
printf("not a correct option") ;
}
}
while(option!=5);
getch();
}
node*push(node* top,int val)
{
node *ptr;
ptr=(node*)malloc(sizeof(node));
ptr->data=val;
if(top==NULL)
{
ptr->next=NULL;
top=ptr;
}
else
{
ptr->next=top;
top=ptr;
}
return(top) ;
}
node *display(node*top)
{
node*ptr;
ptr=top;
if(top==NULL)
{
printf("stack is empty");
exit(0);
}
else
{
while(ptr!=NULL)
{
printf("\t%d",ptr->data);
ptr=ptr->next;
}
}
return(top);
}
node *pop(node*pop)
{
node*ptr;
ptr=top;
if(top==NULL)
{
printf("stack is empty") ;
exit(0) ;
}
else
{
top=top->next;
free(ptr);
printf("\n %d delete from stack ",ptr->data);
}
return(top);
}
int peep(node*top)
{
if(top==NULL)
return(-1);
else
return(top->data);
}
Post a Comment