Linked List based Implementation of Stacks

Linked List based Implementation of Stacks

• The typical 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. Following Fig. 5.8.1 represents stack using linked list.

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

 

1. Push operation

The pseudo code for push operation is as given below.

void Lstack::Push(int Item, node **top)

{

   node *New;

   New= new node;

   //Using new operator the memory can be allocated.

   For example:

   New‒>next=NULL;

   New‒>data=Item;

   New‒> next = *top;

   *top = New;

}

In the main function, when the item to be inserted is entered, a call to push function is given.

If item = 10, then by new 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 ‒

New‒>next=*top;

top=New;

And we will get

When 30 is pushed then

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

 

2. Pop operation

int Lstack::Pop(node **top)

{

   int item;

   node *temp;

   item = (*top) ‒>data; // We want to delete top node. Hence in order to remember the data being deleted it is already stored In Item

   temp = *top;

   *top = (*top)‒>next; //Taking the address of top in temp node

                                  //and assigning new top to the next node.

   delete temp;

   return (item);

}

If stack is as follows.

Then we will write following for deletion operation

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

temp=*top

*top=*top‒>next         now top =20   

delete temp;               deallocating memory of node 30. That means node 30 is deleted.

Let us now see the C++ implementation of it.

C++ 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 can not be stack full condition in stack using linked list.

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

#include<iostream>

#include<cstdlib>

using namespace std;

//Declaration for data structure of linked stack

class Lstack

{

private:

typedef struct stack

{

   int data;

   struct stack *next;

}node;

node *top;

public:

Lstack();

~Lstack();

void create(),remove(),show();

void Push(int, node **);

void Display(node **);

int Pop(node **);

int Sempty(node *);

};

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The constructor defined

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

Lstack::Lstack()

{

   top = NULL;

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The destructor defined

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

Lstack:: Lstack()

{

   node *temp;

   temp=top;

   if(temp= =NULL)

   delete temp;

   else

   {

   while(temp!= NULL)

   {

      temp=temp‒>next;

      top=NULL;

      top=temp;

   }

   delete temp://de allocating memory

}

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The create function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

void Lstack::create()

{

   int data;

   cout<<"\n Enter the data";

   cin>>data;

   Push(data,&top);

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The remove function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

void Lstack::remove()

{

   int item;

   if(Sempty(top))

   cout<<"\n stack underflow!";

   else

   {

      item = Pop(&top);

      cout<<"\n The popped node is "<<<< item;

   }

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The show function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

void Lstack::show()

{

   Display(&top);

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The Push function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

void Lstack::Push(int Item, node **top)

{

   node *New

   New = new node;

   New‒>next=NULL;

   New‒>data=Item;

   New‒>next = *top;

   *top = New;

}

*/

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The Sempty Function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

int Lstack::Sempty(node *temp)

{

   if(temp= =NULL)

      return 1;

   else

      return 0;

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The Pop function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

int Lstack::Pop(node **top)

{

   int item;

   node *temp;

   item = (*top) ‒>data;

   temp = *top;

   *top = (*top)‒>next;

   delete temp;

   return(item);

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The Display function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

void Lstack::Display(node **head)

{

   node *temp;

   temp = "head;

   if(Sempty(temp))

      cout<<"\n The stack is empty!";

   else

   {

      while (temp = NULL)

      {

         cout<<" "<<temp‒> data;

         temp = temp ‒> next;

      }

  }

getch();

}

/*

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

The main function

‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒‒

*/

void main()

{

int choice;

char ans,ch;

Lstack st;

clrscr();

cout<<"\n\t\t Stack Using Linked List";

do

{

   cout<<"\n\n The main menu";

   cout<<"\n1.Push\n2.Pop\n3.Display\n4.Exit";

   cout<<"\n Enter Your Choice";

   cin>>choice;

   switch(choice)

   {

      case 1:st.create();

            break;

      case 2:st.remove();

            break;

      case 3:st.show();

            break;

      case 4:exit(0);

   }

   cout<<"\n Do you want to continue?";

   ans =getche();

   getch();

   clrscr();

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

   getch();

}

Output

The main menu

1.Push

2.Pop

3.Display

4.Exit

Enter Your Choice1

Enter the data10

Do you want to continue?

The main menu

1.Push

2.Pop

3.Display

4.Exit

Enter Your Choice1

Enter the data20

Do you want to continue?

The main menu

1.Push

2.Pop

3.Display

4.Exit

Enter Your Choice1

Enter the data30

Do you want to continue?

The main menu

1.Push

2.Pop

3.Display

4.Exit

Enter Your Choice1

Enter the data40

Do you want to continue?

The main menu

1.Push

2.Pop

3.Display

4.Exit

Enter Your Choice1

Enter the data50

Do you want to continue?

The main menu

1.Push

2.Pop

3.Display

4.Exit

Enter Your Choice3

50 40 30 20 10

Do you want to continue?

 

In push function :

The memory for 'New' node is allocated using new operator. In 'New' node we will put the data.

Initially top = NULL, hence

Suppose Item = 10 then,

New→data = Item

New → next = *top

*top = New

Now make 'New' node as 'top' node. When we push next item as 20 then,

New→data = Item;

New→ next = *top;

Now make 'New' node as 'top' node.

top = New ;

 

In POP function

We will POP the element which is at the top. Consider a scenario that we have a stack of

Then delete 'temp' node.

This will be new stack with node '30' popped.

 

Review Questions

1. Using linked list, formulate separate routines to create an empty stack and to push an element onto a stack.

2. Write a C++ program to implement stack through linked list.

3. Write a program to implement STACK through linked list.