Stack is a data structure that
follows first-in last-out ordering. This means that the data that you have
inserted at last will be retrieved or popped off first. There are two basic
operations that can be applied on the stack to update it. These are:-
·
Push, and
·
Pop.
The push operation is used to
insert any element in the stack, and the pop operation is used to delete any
element from the stack.
We have basically two methods for
implementing stacks, one using arrays and other using linked-list. Arrays being
static in nature don’t provide any dynamic expansion of stack and the total
number of elements should be already known to us, but this is not the case with
the linked list implementation of stacks. Linked list being a dynamic data
structure can be expanded dynamically and there is no need to have any prior
knowledge of total number of elements.
This post explains you how to
implement stacks in computer’s memory using linked lists.
The following program shows the implementation of Stacks using Arrays.
/*************************************************************/
//IMPLEMENTATION OF STACKS USING
ARRAYS
#include<stdio.h>
#include<conio.h>
int max;
int top=-1;
int *a;
void printstack();
int pop();
void push(int);
int main()
{
int
k,ch,num;
clrscr();
printf("ENTER
THE MAXIMUM NUMBER OF ELEMENTS : ");
scanf("%d",&max);
a=(int
*)malloc(sizeof(int)*max);
while(1)
{
printf("YOU
HAVE THE FOLLOWING CHOICES : \n");
printf("1.PUSH\n");
printf("2.POP\n");
printf("3.DISPLAY
THE CONTENTS OF THE STACK : \n");
printf("4.EXIT\n");
printf("ENTER
YOUR CHOICE : ");
scanf("%d",&ch);
switch(ch)
{
case
1:
printf("ENTER
THE VALUE YOU WANT TO PUSH : ");
scanf("%d",&num);
push(num);
break;
case
2:
pop();
break;
case 3:
printstack();
break;
case
4:
exit(1);
default:
printf("YOU
HAVE ENTERED A WRONG CHOICE...\n");
}
printf("\n\nPRESS
ANY KEY TO CONTINUE...\n");
getch();
clrscr();
}
k=pop();
printf("%d\n",k);
k=pop();
printf("%d",k);
getch();
return
1;
}
void push(int tmp)
{
if(top==max-1)
printf("OVERFLOW");
else
a[++top]=tmp;
printf("VALUE
PUSHED SUCCESSFULLY IN STACK\n");
}
int pop()
{
if(top==-1)
{
printf("UNDERFLOW");
return
1;
}
else
return
a[top--];
}
void printstack()
{
int
i;
for(i=top;i>=0;i++)
{
printf("%d\n",a[i]);
}
}
/***************************************************************/
The following program shows the implementation of Stacks using Linked-List # 1.
/****************************************************************/
#include<stdio.h>
#include<conio.h>
struct stack
{
int
value;
struct
stack*next;
};
typedef struct stack stack;
stack* makenode(int);
stack* push(stack*,stack*);
stack* pop(stack*);
void print(stack*);
int main()
{
int
n,ch;
stack*
nn ;
stack*
top=NULL;
clrscr();
while(1)
{
printf("YOU
HAVE THE FOLLOWING CHOICES : \n");
printf("1.PUSH\n");
printf("2.POP\n");
printf("3.PRINT\n");
printf("4.EXIT\n");
printf("ENTER
YOUR CHOICE : ");
scanf("%d",&ch);
switch(ch)
{
case
1:
printf("ENTER THE NUMBER YOU WANT TO
PUSH : ");
scanf("%d",&n);
nn= makenode(n);
top= push(nn,top);
break;
case
2:
top=pop(top);
break;
case
3:
print(top);
break;
case
4:
exit(0);
default:
printf("YOU
HAVE ENTERED A WRONG CHOICE...");
}
printf("\nPRESS
ANY KEY TO CONTINUE...");
getch();
clrscr();
}
getch();
return
0;
}
stack*makenode(int n)
{
stack*
nn;
nn=(stack*)malloc(sizeof(stack));
nn->value=n;
nn->next=NULL;
return
nn;
}
stack* push(stack* nn,stack* top)
{
if(top==NULL)
top=nn;
else
{
nn->next=top;
top=nn;
}
printf("THE
VALUE IS PUSHED SUCCESSFULLY\n");
return
top;
}
stack* pop(stack* top)
{
if(top==NULL)
printf("UNDERFLOW");
else
{
top=top->next;
}
//printf("THE
VALUE IS POPPED SUCCESSFULLY\n");
return
top;
}
void print(stack* top)
{
while(top!=NULL)
{
printf("%d\n",top->value);
top=pop(top);
}
}
/*****************************************************************/
The following program shows the implementation of Stacks using Linked-List # 2.
/***************************************************************/
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
struct node
{
int
data;
struct
node*next;
};
typedef struct node node;
node*makenode(int);
void printlist(node*);
node*push(node*,node**,node*);
node*pop(node*,node**);
int main()
{
int
i,num,ch;
node*start,*last,*nn;
nn=last=start=NULL;
clrscr();
printf("CREATE
YOUR STACK\n");
while(1)
{
printf("ENTER
THE DATA PART OF THE NODE : ");
scanf("%d",&num);
if(num==0)
break;
nn=makenode(num);
if(start==NULL)
{
start=last=nn;
}
else
{
last->next=nn;
last=nn;
}
}
while(1)
{
printf("\nYOU
HAVE THE FOLLOWING CHOICES : \n");
printf("1.PUSH\n");
printf("2.POP\n");
printf("3.PRINT
THE LIST\n");
printf("4.EXIT\n");
printf("\nENTER
YOUR CHOICE : ");
scanf("
%d",&ch);
switch(ch)
{
case
1:
printf("ENTER
THE VALUE YOU WANT TO PUSH INSIDE YOUR STACK : ");
scanf("%d",&num);
nn=makenode(num);
start=push(start,&last,nn);
break;
case
2:
start=pop(start,&last);
break;
case
3:
printlist(start);
break;
case
4:
exit(1);
default:
printf("YOU
HAVE ENTERED A WRONG CHOICE\n");
}
printf("\n\nPRESS
ANY KEY TO CONTINUE...\n");
getch();
clrscr();
}
getch();
return
1;
}
node*makenode(int num)
{
node*nn;
nn=(node*)malloc(sizeof(node));
nn->data=num;
nn->next=NULL;
return
nn;
}
void printlist(node*start)
{
while(start)
{
printf("%d\t",start->data);
start=start->next;
}
}
node*push(node*start,node**p2last,node*nn)
{
if(start==NULL)
{
start=(*p2last)=nn;
return
start;
}
(*p2last)->next=nn;
(*p2last)=nn;
printf("\nELEMENT
PUSHED SUCCESSFULLY...\n");
return
start;
}
node*pop(node*start,node**p2last)
{
node*tmp,*ptr;
tmp=(*p2last);
ptr=start;
if(start==NULL)
{
printf("\nUNDER-FLOW\n");
return
start;
}
if(start==(*p2last))
{
start=(*p2last)=NULL;
return
start;
}
while(1)
{
if(ptr->next==(*p2last))
break;
ptr=ptr->next;
}
(*p2last)=ptr;
(*p2last)->next=NULL;
free(tmp);
printf("\nELEMENT
POPPED SUCCESSFULLY...\n");
return
start;
}
/***************************************************************/
No comments:
Post a Comment