implementation of stack using linked list

In This Blog, we are going to understand the combination of two main data structures Stack and Linked List in 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

Advertisements

Stack
A stack is a linear data structure which stores the similar type 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
Advertisements

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.

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, stackTop gives the index of the array. In this case, stackTop 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++ //wikkihut.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; //wikkihut.com }
Code language: C++ (cpp)

Algorithm

Let Stack be a Structure whose declaration will look like.

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

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:

FAQ

Can stack be implemented using 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 as linked lists are dynamic.

Is linked list a stack?

No, linked list is a data structure which has two parts, one part stores the data and 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 stack with classes also.

Similar Posts

Advertisements