Implement Stack Using Linked List C++ Program

Stack Linked List

In This Blog, we are going to understand the combination of two main data structures Stack and Linked List in the Data Structures C++ Program.
So a brief understanding of these topics is necessary, in case you don’t know then just take a look at the topics below.

Linked List
Linked List is a Node that stores data in one part and a link to the next node

Stack
A stack is a linear data structure that stores similar types of data like int, float, char, etc.
In Stack, we can use only two operations Push and Pop.

We can insert elements in the stack only from the top and delete elements only from the top that is the Last In Last Out ( LILO ) Algorithm.

There are two main ways to Implement stack in Data Structures C++

1. Stack Using Arrays
2. Stack using Linked Lists

Stack Using Linked Lists C++ | Dynamic Stack.

Implementing Stack using Pointers is an effective way of the utilization of memory.
Since it is dynamic therefore you don’t need to worry about the size of the stack
It will grow and shrink in the run time.

In Linked Lists, You only have to insert a new node and adjust the links of the newly inserted node with the rest of the nodes.

As we know the size of the Array is fixed or in the array representation of a stack, only a fixed number of elements can be pushed onto the stack.

If in a program the number of elements to be pushed exceeds the size of the array, the program might with an error.

We have seen that by using pointer variables we can dynamically allocate and deallocate memory, and by using linked lists we can dynamically organize data (such as an ordered list). Next, we will use these concepts to implement a stack dynamically.

Recall that in the linear representation of a stack, the value of stack top indicates the number of elements in the stack, and the value of stack top -1 points to the top item in the stack. With the help of stack Top, we can do several things, Find the top element, check whether the stack is empty, and so on.

Similar to the linear representation, in the linked representation StackTop is used to locate the top element in the stack.

However, there is a slight difference. In the former case, the stack top gives the index of the array. In this case, the stack top gives the address (memory location) of the top element of the stack.

C++ Program

Menu Driven Program of Implementation of Stack using Linked List C++

//Stack Using Linked List c++
//techindetail.com

#include<iostream>
using namespace std;

//create a structure ( node )

struct stack
{
  int data;
  stack *link;
}*top;

//push function to add items to stack

void push()
{
  int n;
  stack *node;
  node=new stack;

//if program is not able to create node

if(node==NULL)
{
  cout<<"no space avail: /n";
  return;

}
  cout<<"enter data\n";
  cin>>n;
  node->data=n;
  node->link=NULL;
  if(top==NULL)
  top=node;
else
{
  node->link=top;
  top=node;
}
}



int pop()
{
  stack *temp;
  int value;
  if(top==NULL)
{
cout<<"STack Underflow";
  return 0;
}
else
{
  temp=top;
  value=temp->data;
  top=top->link;
  delete temp;

return value;
}
}

void display()
{
  stack *temp;
  temp=top;
  if(temp==NULL)
  cout<<"stack underflow";
else
{
  cout<<"\nElements in stack are: \n";
  while(temp!=NULL)
{

  cout<<"\t\t"<<temp->data<<endl;
  temp=temp->link;
}
}
}

int main()
{
//menu based program of stack

 top=NULL;
 int ch, value;
while(1)
{   cout<<"\n\t --------- Choose ----  \n";
   cout<<"\n\tPress 1 for Push \n";
   cout<<"\tPress 2 for Pop: \n";
   cout<<"\tPress 3 for Display: \n";
  cout<<"\tPress 4 for Exit: \n";
  cout<<"\n enter choice: \n";
  cin>>ch;
switch(ch)
{
  case 1:
  push();
  break;
  case 2:
value=pop();
if(value!=0)
  cout<<"\nElement Popped is "<<value;
  break;
 case 3:
  display();
  break;
 case 4:
  return 0;
default:
cout<<"Invalid choice:\n";
}
}
return 0;

//techindetail.com
}

Code language: C++ (cpp)

Algorithm

Let Stack be a Structure whose declaration will look like.

struct stack
<strong>{</strong>
int data;
stack *link;
<strong>}</strong>*top;Code language: HTML, XML (xml)

Algorithm for PUSH

• Create a Node
• Node = new stack
• If node == NULL, error
• Else,
• Enter data
• Node->data = element
• Node->link=NULL
• If, top==NULL, then top = node
• Else,
• Node->link = top
• Top = node

Algorithm for Pop

• Create a Node Temp
• Put temp = node
• If ( top == NULL )
• Write Stack empty & return
• Else, Temp= top
• Value=temp->data
• Top = top -> link
• Delete temp
• Return (value)
• Exit

Advantages of Stack using linked lists

• Memory efficient
Linked representation of stack is an effective way and proper utilization of memory.

There is no memory wasted in linked lists because the data elements are stored at distant places in the memory whose addresses are linked by pointers.

• Time efficient

Related Data Structures:

• Linked Lists
• Doubly Linked List
• Queue
• Circular Linked List
• Tree
• Binary Tree

FAQ