HarishGadade

Stack Using Linked List

Linear Search and Binary Search PPT

A stack data structure can be implemented by using linked list data structure. The stack implemented using linked list can work for unlimited number of values. That means, stack implemented using linked list works for variable size of data. So, there is no need to fix the size at the beginning of the implementation

The disadvantage of a stack implemented using an array is that its size is fixed and needs to be specified at compile time. This stack implementation is often impractical. To make the size of the stack to be dynamic and determined at run-time, we need to implement it using a linked list. By doing this, the size of the stack can shrink or grow on demand during the program execution. A stack implemented using a linked list is also known as a linked stack.

1. First, we declare the element of the stack:

struct node
{            
    int data;            
    struct node *link;
};

Function to create New node is

struct node *getnode(int item)
{
	struct node *temp;
	temp=(struct node*)malloc(sizeof(struct node));
	temp->data=item;
	temp->link=NULL;
	return(temp);
}

2. Second, we need to initialize the stack by setting the top pointer of the stack to NULL

top = NULL

3. Third, to push an element (10) into the stack, we create a new node, and point the stack pointer to the new node e.g., to push the first element:

struct node *push(struct node *top)
{
	struct node *temp;
	int item;
	printf("\nEnter New Node : ");
	scanf("%d",&item);
	temp=getnode(item);
	if(top=NULL)
		top=temp;
	else
	{
		temp->link=top;
		top=temp;
	}	
	return(top);
}

4. To pop an element from the stack, we need to get the data of the element, point the stack pointer to the next element and remove it. The following picture illustrates how to pop the top element ( 30) from the stack.

struct node *pop(struct node *top)
{
	struct node *ptr;
	if(top==NULL)
		printf("\nStack is empty\n");
	else
	{
		ptr=top;
		top=top->link;
		ptr->link=NULL;
		printf("\n%d is deleted..",ptr->data);
		free(ptr);
	}
	return(top);
}

5. To display stack

void display(struct node *top)
{
	struct node *ptr;
	for(ptr=top;ptr!=NULL;ptr=ptr->link)
		printf("%d    ",ptr->data);
}

Program for Stack Operations is as follows

#include
#include
struct node
{
    int data;
    struct node *link;
};

struct node *push(struct node *);
struct node *pop(struct node*);
void display(struct node *);
struct node *getnode(int);

void main()
{
	struct node *top=NULL;
	int choice;
	while(1)
	{
		printf("\n1. PUSH");
		printf("\n2. POP");
		printf("\n3. Display");
		printf("\n0. Exit");
		printf("\nEnter your choice : ");
		scanf("%d",&choice);
		switch(choice)
		{
			case 1:
				top=push(top);
				break;
			case 2:
				top=pop(top);	
				break;
			case 3:
				display(top);
				break;
			case 0:
				exit(0);
				break;

			default:
				printf("\nWrong choice!!");
		}
	}
}
struct node *getnode(int item)
{
	struct node *temp;
	temp=(struct node*)malloc(sizeof(struct node));
	temp->data=item;
	temp->link=NULL;
	return(temp);
}
struct node *push(struct node *top)
{
	struct node *temp;
	int item;
	printf("\nEnter New Node : ");
	scanf("%d",&item);
	temp=getnode(item);
	if(top=NULL)
		top=temp;
	else
	{
		temp->link=top;
		top=temp;
	}	
	return(top);
}	
void display(struct node *top)
{
	struct node *ptr;
	for(ptr=top;ptr!=NULL;ptr=ptr->link)
		printf("%d    ",ptr->data);
}
struct node *pop(struct node *top)
{
	struct node *ptr;
	if(top==NULL)
		printf("\nStack is empty\n");
	else
	{
		ptr=top;
		top=top->link;
		ptr->link=NULL;
		printf("\n%d is deleted..",ptr->data);
		free(ptr);
	}
	return(top);
}

Data Strucrures

Stack Using Linked List