Implementation of Stack using Linked List

Implementation of Stack using Linked List

• Stack is a special case of list and therefore we can represent stack using arrays as well as using linked list.

• The advantage of implementing stack using linked list is that we need not have to worry about the size of the stack. Since we are using linked list as many elements we want to insert those many nodes can be created. And the nodes are dynamically getting created so there won't be any stack full condition.

• The typical 'C' structure for linked stack can be struct stack

{

int data;

struct stack next;

}node;

• Each node consists of data and the next field. Such a node will be inserted in the stack. Fig. 2.4.1 represents stack using linked list.

•  There are various operations that can be performed on the linked stack. These operations are -

1. Push

2. Pop

3. Stack empty

4. Stack full

1. Push operation

The  pseudo code for push operation is as follows :

In the main function, when the item to be inserted is entered, a call to push function is given. In push function another function get_node is invoked to allocate the memory for a node as follows:

If item=10, then by get node function node will be allocated. Then

*top= New

This is our new top node. Hence stack will look like this

If again Push function is called for pushing the value 20 then

This can be done using following statements-

Thus by pushing the items repeatedly we can create a stack using linked list.

2. Pop operation

If we write

item = *(top)->data    then item=30

temp=*top

*top=*top->next      now top=20

free(temp);  deallocating memory of node 30. That means node 30 is deleted.

Program

/**********************************************************

Program for creating the stack using the linked list.

Program performs all the operations such as push,pop and

display. It takes care of stack underflow condition. There cannot be stack full condition in stack using linked list.

**********************************************************

#include <stdio.h>

#include <conio.h>

#include <process.h>

#include <stdlib.h>

#include <alloc.h>

/*Declaration for data structure of linked stack*/

typedef struct stack

{

int data;

struct stack *next;

}node;

void main()

{

/* Local declarations */

node *top;

int data,item,choice;

char ans,ch;

void Push(int, node **);

void Display(node **);

int Pop(node **);

int Sempty(node *);

clrscr();

top=NULL;

printf("\n\t\t Stack Using Linked List");

do

{

printf("\n\n The main menu");

printf("\n1.Push\n2.Pop\n3.Display\n4.Exit");

printf("\n Enter Your Choice");

scanf("%d", &choice);

switch(choice)

{

case 1:printf("\n Enter the data");

scanf("%d", &data);

Push(data,&top);

break;

case 2:if(Sempty(top)) /*before popping the data whether stack is empty or not is checked*/

printf("\n stack underflow!");

else

{

item = Pop(&top);

printf("\n The popped node is %d",item);

}

break;

case 3:Display(&top);

/*displays stack from top to bottom*/

break;

case 4:printf("\n Do You want To Quit?(y/n)");

ch=getche();

if(ch=='y')

exit(0);

else

break;

}

printf("\n Do you want to continue?");

ans =getche();

getch();

clrscr();

} while(ans =='Y' || ans =='y');

getch();

}

*/void Push(int Item, node **top)

{

node *New;

node * get_node(int);

New = get_node (Item);

New->next = *top;

*top = New;

}

node * get_node( int item)

{

node * temp;

temp =(node *)malloc(sizeof(node));

if (temp==NULL)

printf("\nMemory Can not be allocated \n");

temp -> data = item;

temp->next = NULL;

return(temp);

}

int Sempty(node *temp)

{

if(temp == NULL)

return 1;

else

return 0;

}

int Pop(node **top)

{

int item;

node *temp;

item = (*top) ->data;

temp *top;

*top = (*top)->next;

free(temp);

return(item);

}

void Display(node **head)

{

node *temp;

temp = *head;

if(Sempty(temp))

printf("\n The stack is empty!");

else

{

while (temp != NULL)

{

printf("%d\n",temp-> data);

temp = temp->next;

}

}

getch();

}

Stack Using Linked List

The main menu

1.Push

2.Pop

3.Display

4.Exit

Enter Your Choice1

Enter the data10

Do you want to continue?y

The main menu

1.Push

2.Pop

3.Display

4.Exit

Enter Your Choice1

Enter the data20

Do you want to continue?y

The main menu

1.Push

2.Pop

3.Display

4.Exit

Enter Your Choice1

Enter the data30

Do you want to continue?y

The main menu

1.Push

2.Pop

3.Display

4.Exit

Enter Your Choice3

30

20

10

Do you want to continue?y

The main menu

1.Push

2.Pop

3.Display

4.Exit

Enter Your Choice2

The popped node is30

Do you want to continue?y

The main menu

1.Push

2.Pop

3.Display

4.Exit

Enter Your Choice3

20

10

Review Question

Write an algorithm for Push and Pop operations on stack using linked list.