Program to implement Stack using Linked List

Stacks

Program to implement Stack using Linked List:

/*Implementation of stacks using linked list*/

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

#define MAX 10

typedef struct stack
{
int info;
struct stack *next;
}stack;

/*create to allocate memory*/
stack *create()
{stack *temp = (stack *)malloc(sizeof(stack));
if(temp==NULL)
{printf(“\nMemory allocation error!”);
exit(1);
}
return temp;
}

/*makenode to initialize new node*/
stack *makenode(int x)
{stack *temp=create();
temp->info=x;
temp->next=NULL;
return temp;
}

/*push to insert an element in list at beginning*/
stack *push(stack *top,int x)
{stack *temp;
stack *ptr=makenode(x);
if(top==NULL)
{top=ptr;
}
else
{ptr->next=top;
top=ptr;
}
}

/*pop to remove top element from stack*/

stack *pop(stack *top)
{stack *temp;
if(top==NULL)
{printf(“\nStack Empty! Underflow.”);
return NULL;
}
printf(“\nPopped element: %d”,top->info);
temp=top;
top=top->next;
free(temp);
return top;
}

/*displays contents of stack*/
void display(stack *top)
{
stack *temp;
if(top==NULL)
{printf(“\nStack empty.”);
return;
}
temp=top;
while(temp!=NULL)
{printf(“%d->”,temp->info);
temp=temp->next;
}
printf(“\b\b “);
}

void main()
{
int ch,num;
stack *top=NULL;
while(1)
{
clrscr();
printf(“\nStack-Menu”);
printf(“\n\n1. Push”);
printf(“\n2. Pop”);
printf(“\n3. Display”);
printf(“\n4. Exit”);
printf(“\n\nEnter your choice?”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
printf(“\nEnter number to push?”);
scanf(“%d”,&num);
top=push(top,num);
break;
case 2:
top=pop(top);
break;
case 3:
display(top);
break;
case 4:
exit(0);
default:
printf(“\nInvalid choice!”);
}
getch();
}
}

Representing two stacks in an array:

Stacks

Representing two stacks in an array

One array may be considered to be composed of multiple stacks, such that the size of the array is divided by the number of stacks to be created, which results in representing multiple stacks in one array.

For example:  If we wish to represent two stacks in one array of size 10, then the size of the array (10) may be divided by 2, to result in two stacks each of size 5.

Thus, when you push or pop an element, you must also state the stack id, along with other required information.

Program for representing multiple stacks in one array:

Multiple Stacks in an array

Program for representing multiple stacks in one array

/*Implementing multiple stacks in a single array*/

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

#define MAX 10

void push(int,int[],int,int);
int pop(int,int[],int);
void display(int,int[],int);

/*array to top index for each stack*/
int t[MAX];
int top[MAX];

void main()
{
int arr[MAX],n,totstk,index;
int i,j,k=0,span,no,ch,num;
/*Input total elements of the array*/
/*This array may be divided into multiple stacks*/
printf(“\nEnter size of the array?”);
scanf(“%d”,&n);

/*Input total stacks to be created in above array*/
printf(“\nEnter total stacks to create?”);
scanf(“%d”,&totstk);

/*t[] array will contains totstk indexes for top*/
/*since total stacks to be created are totstk*/
/*Initializing t[] array with -1*/
for(i=0;i<totstk;i++)
t[i]=-1;

/*computes size of one stack*/
span=n/totstk;

/*store top of each stack in the array*/
/*this top serves as index for push/pop operations*/

top[k++]=0;
for(i=0;i<totstk-1;i++,k++)
top[k]=top[k-1]+span;

/*displaying elements of indexed array*/
for(i=0;i<totstk;i++)
printf(“%d\t”,top[i]);
do{
clrscr();
printf(“\nStacks-Menu (n stacks:1 array)”);
printf(“\n1. Push”);
printf(“\n2. Pop”);
printf(“\n3. Display”);
printf(“\n4. Quit”);
printf(“\n\nEnter your choice?”);
scanf(“%d”,&ch);

if(ch!=4)
{
printf(“\nEnter stack number (0 to %d)?”,totstk-1);
scanf(“%d”,&index);
}

switch(ch)
{
case 1:
printf(“\nEnter number to push?”);
scanf(“%d”,&no);
push(index,arr,span,no);
break;
case 2:
num=pop(index,arr,span);
printf(“\nPopped element from stack %d is %d”,index,num);
break;
case 3:
display(index,arr,span);
break;
case 4:
exit(0);
}
getch();
}while(1);
}
void push(int index,int arr[],int n,int num)
{
int topid,topelement;
topid=top[index];
topelement=t[index];
if(topelement==topid+n-1)
{printf(“\nStack Full! Overflow.”);
return;
}
topelement=++t[index];
arr[topid+topelement]=num;
}
int pop(int index,int arr[],int n)
{
int topid,topelement;
topid=top[index];
topelement=t[index];
if(topelement==-1)
{printf(“\nStack Empty! Underflow.”);
return -1;
}
t[index]–;
return(arr[topid+topelement]);
}
void display(int index,int arr[],int n)
{
int i,topid,topelement;
topid=top[index];
topelement=t[index];
if(topelement==-1)
{printf(“\nStack Empty! Underflow.”);
return;
}
for(i=topid+topelement;i>=topid;i–)
printf(“%d\t”,arr[i]);
}