We can avoid the size limitation of a stack implemented with an array, with the help of a linked list to hold the stack elements. As needed in case of array, we have to decide where to insert elements in the list and where to delete them so that push and pop will run at the fastest. Primarily, there are two operations of a stack; push() and pop(). A stack carries lifo behavior i.e. last in, first out. You know that while implementing stack with an array and to achieve lifo behavior, we used push and pop elements at the end of the array. Instead of pushing and popping elements at the beginning of the array that contains overhead of shifting elements towards right to push an element at the start and shifting elements towards left to pop an element from the start. To avoid this overhead of shifting left and right, we decided to push and pop elements at the end of the array. Now, if we use linked list to implement the stack, where will we push the element inside the list and from where will we pop the element? There are few facts to consider, before we make any decision:
Insertion and removal in stack takes constant time. Singly linked list can serve the purpose. Hence, the decision is to insert the element at the start in the implementation of push operation and remove the element from the start in the pop implementation.
There are two parts of above figure.On the left hand, there is the stack implemented using an array. The elements present inside this stack are 1, 7, 5 and 2. The most recent element of the stack is 1. It may be removed if the pop() is called at this point of time. On the right side, there is the stack implemented using a linked list. This stack has four nodes inside it which are liked in such a fashion that the very first node pointed by the head pointer contains the value 1. This first node with value 1 is pointing to the node with value 7. The node with value 7 is pointing to the node with value 5 while the node with value 5 is pointing to the last node with value 2. To make a stack data strcuture using a linked list, we have inserted new nodes at the start of the linked list.
Insertion and removal in stack takes constant time. Singly linked list can serve the purpose. Hence, the decision is to insert the element at the start in the implementation of push operation and remove the element from the start in the pop implementation.
There are two parts of above figure.On the left hand, there is the stack implemented using an array. The elements present inside this stack are 1, 7, 5 and 2. The most recent element of the stack is 1. It may be removed if the pop() is called at this point of time. On the right side, there is the stack implemented using a linked list. This stack has four nodes inside it which are liked in such a fashion that the very first node pointed by the head pointer contains the value 1. This first node with value 1 is pointing to the node with value 7. The node with value 7 is pointing to the node with value 5 while the node with value 5 is pointing to the last node with value 2. To make a stack data strcuture using a linked list, we have inserted new nodes at the start of the linked list.
We are going to implement stack through linked list. Here is the code of stack implementation in C.
#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
void pop();
void push(int value);
void display();
struct node
{
int data;
struct node *link;
};
struct node *top=NULL,*temp;
int main()
{
int choice,data;
while(1) //infinite loop is used to insert/delete infinite number of elements in stack
{
printf("\n1.Push\n2.Pop\n3.Display\n4.Exit\n");
printf("\nEnter ur choice:");
scanf("%d",&choice);
switch(choice)
{
case 1: //To push a new element into stack
printf("Enter a new element :");
scanf("%d",&data);
push(data);
break;
case 2: // pop the element from stack
pop();
break;
case 3: // Display the stack elements
display();
break;
case 4: // To exit
exit(0);
}
}
getch();
return 0;
}
push(int data)
{
temp=(struct node *)malloc(sizeof(struct node)); // creating a space for the new element.
temp->data=data;
temp->link=top;
top=temp;
}
pop()
{
if(top!=NULL)
{
printf("The poped element is %d",top->data);
top=top->link;
}
else
{
printf("\nStack Underflow");
}
}
display()
{
temp=top;
if(temp==NULL)
{
printf("\nStack is empty\n");
}
while(temp!=NULL)
{
printf(" %d ->",temp->data);
temp=temp->link;
}
}
Technorati Tags: stack,stack implementation using linked list,stack using linked list,stack implementation in linked list,stack using linked list in c,c stack implementation,stack link list in c
