Stack using LinkedList
To implement stack using a single linked list that supports the basic operation of stack data
structure such as PUSH, POP and Traverse and it follows LIFO mechanism
Inserted of using arrays we can also used linked list to implement stack
To overcome the drawbacks of arrays that mean limited size and garbage memory allocation
Example:
44 4800 --- 33 4900 22 5000 11 NULL
4700 4800 4900 5000
TOP
4700
4700
Algorithm of stack using linked list:
Step -1 : Create a Node
Struct node
{
Int data;
Struct node *next;
};
Struct node * top = NULL;
Step -2: PUSH() - insert an element into the linked list
Create a newNode with given value
Check whether list is empty (TOP==NULL)
If it is Empty then, set newNode->next=NULL and TOP = newNode
If it is not Empty then, set newNode->next=TOP and TOP = newNode.
Step- 3: POP() -deleting/Remove an element from the linked list
check whether list is Empty(TOP==NULL)
if it is empty then, display ‘list is empty!!! Deletion is not possible” and terminate the
function
if it is not empty then, define a node pointer temp and initialize with TOP
check whether list is having only one node(temp->next ==NULL)
if it is true then set TOP =NULL and delete temp
if it is false then set TOP= temp-next, and delete temp
Step -4: traverse() – it shows output from the stack using linked list
check whether list is empty (TOP==NULL)
if it is empty then, display ‘list is empty!!!’ and terminate the function
if it is not empty then, define a node pointer temp and initialize with TOP
keep displaying temp->data with arrow (--) until temp reaches to the last node
finally display temp->data with arrow pointing to NULL (temp->data-NULL)
program:
// implementing stack using linked list
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node * top=NULL;
void push(int ele);
void pop();
void traverse();
void push(int ele)
{
struct node newnode=(struct node)malloc(sizeof(struct node));
if(top==NULL)
{
newnode->data=ele;
newnode->next=NULL;
top=newnode;
}
else
{
newnode->data=ele;
newnode->next=top;
top=newnode;
}
printf("inserted successfully..\n");
}
void pop()
{
struct node *temp;
temp=top;
if(top == NULL)
{
printf("Stack is empty\n");
}
else
{
printf("deleted element is: %d\n",temp->data);
top=temp->next;
temp->next=NULL;
free(temp);
}
}
void traverse()
{
struct node *temp;
temp=top;
if(top == NULL)
{
printf("Stack is empty\n");
}
else
{
printf("Stack elements are:\n");
while(temp->next!=NULL)
{
printf("%d\n",temp->data);
temp=temp->next;
}
printf("%d\n",temp->data);
}
}
void main() {
int choose,ele;
clrscr();
while(1)
{
printf("Stack menu\n");
printf("1. push\n 2. pop\n 3. traverse\n 4.exit\n");
printf("Choose one:");
scanf("%d",&choose);
switch(choose)
{
case 1: printf("Enter an element:");
scanf("%d",&ele);
push(ele);
break;
case 2:pop();
break;
case 3:traverse();
break;
case 4: exit(0);
break;
default: printf("Invalid choose...\n");
}
}
getch();
}
