Skip to content
site-logo
  • Home
  • Blog
  • JavaScript
  • Machine Learning
  • Numerical Techniques C++
  • Data Structures C++
  • Typing Guide
site-logo
Home / Data Structures C++ / Implement Stack Using Linked List C++ Program

Implement Stack Using Linked List C++ Program

ByLonz Updated onAugust 22, 2021
Data Structures C++
stack using linked list
Ad
Table of contents
  1. Stack Linked List
  2. Stack Using Linked Lists C++ | Dynamic Stack.
  3. C++ Program
  4. Algorithm
    1. Algorithm for PUSH
    2. Algorithm for Pop
    3. Advantages of Stack using linked lists
  5. FAQ

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

Ad

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.

An easy method to learn the implementation of stack using arrays in C++ data structure

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.

implementing stack using linked list c++

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.

Ad

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

Can stack be implemented using a linked list?

Yes Easily, as you can implement stack using arrays same you can implement stack using a linked list, there is one difference arrays are static while linked lists are dynamic.

Is linked list a stack?

No, a linked list is a data structure that has two parts, one part stores the data, and the other part stores the address of another node.

What happens when we implement stack by using linked

If we Implement a stack using a linked list it becomes a Dynamic stack, we can insert and delete elements only from the top, and we don’t need to set the size of the stack, because of linked lists.

What is a Dynamic Stack?

If we implement a Stack using Linked List, it is called a Dynamic Stack because linked lists are dynamic data structures that grow and shrinks in the run time.

Can I implement stack using linked list with class

Yes, you can implement a stack with classes also.

Post navigation

Previous Previous
How to Add Paragraph in Typing Master | Custom Text Lessons
NextContinue
Lagrange Interpolation Formula with Solved Example
Search

Ad

Categories

  • C++ Programing
  • C++ Programs
  • Computer Graphics
  • Data Structures C++
  • JavaScript
  • Machine Learning
  • Numerical Techniques C++
  • Processor
  • Tech Updates
  • Typing Guide
  • Un Categorised

Recent Posts

  • NetSuite Cloud ERP Features
  • Is i7 Better Than i5
  • setTimeout vs setInterval JavaScript Methods
  • String Formatting In JavaScript

Ad


  • Home
  • Blog
  • Privacy Policy
  • Disclaimer
  • Sitemap

Copyright © 2023 Tech In Detail

  • Home
  • Blog
  • JavaScript
  • Machine Learning
  • Numerical Techniques C++
  • Data Structures C++
  • Typing Guide
Search