C++ implementation of Stack using Linked list














































C++ implementation of Stack using Linked list



  • INTRODUCTION

  • Stack is a data structure which follows LIFO i.e. Last-In-First-Out method.

  • The data/element which is stored last in the stack i.e. the element at top will be accessed first.

  • And both insertion & deletion takes place at the top.

  • When we implement stack using array :

    1. We create an array of predefined size & we cannot increase the size of the array if we have more elements to insert.
    2. If we create a very large array, we will be wasting a lot of memory space.
    3. So to solve this lets try to implement Stack using Linked list where we will dynamically increase the size of the stack as per the requirement.

#Implementation using Linked List

  • As we know that we use a head pointer to keep track of the starting of our linked list, So when we are implementing stack using linked list we can simply call the head pointer as top to make it more relatable to stack.

  • Push (insert element in stack)

    1. The push operation would be similar to inserting a node at starting of the linked list
    2. So initially when the Stack (Linked List) is empty, the top pointer will be NULL. Let's suppose we have to insert the values 1, 2 & 3 in the stack.
    3. So firstly we will create a new Node using the new operator and return its address in temporary pointer ptr.
    4. Then we will insert the value 1 in the data part of the Node : ptr->data = valueand make link part of the node equal to top : ptr->link=top.
    5. Finally we will make top = ptr to point it to the newly created node which will now be the starting of the linked list and top of our stack.
    1. Similarly we can push the values 2 & 3 in the stack which will give us a linked list of three nodes with top pointer pointing to the node containing value 3.
  • Pop (delete element from stack)

    1. The pop operation would be similar to deleting a node from the starting of a linked list.
    2. So we will take a temporary pointer ptr and equate it to the top pointer.
    3. Then we will move the top pointer to the next node i.e. top = top->link
    4. Finally, we will delete the node using delete operator and pointer ptr i.e delete(ptr)
    5. After we pop once our stack will look something like this:
  • isEmpty (check if stack is empty or not)

    1. To check if the stack is empty or not we can simply check if top==NULL, it means that the stack is empty

     Program:
#include <iostream>
using namespace std;

//Structure of the Node
struct Node
{
int data;

Node *link;
};

// top pointer to keep track of the top of the stack
Node *top = NULL;

//Function to check if stack is empty or not
bool isempty()
{
 if(top == NULL)
 return true; else
 return false;
}

//Function to insert an element in stack
void push (int value)
{
  Node *ptr = new Node();
  ptr->data = value;
  ptr->link = top;
  top = ptr;
}

//Function to delete an element from the stack
void pop ( )
{
 if ( isempty() )
  cout<<"Stack is Empty";
 else
 {
  Node *ptr = top;
  top = top -> link;
  delete(ptr);
 }
}

// Function to show the element at the top of the stack
void showTop()
{
 if ( isempty() )
  cout<<"Stack is Empty";
 else
  cout<<"Element at top is : "<< top->data;
}

// Function to Display the stack
void displayStack()
{
 if ( isempty() )
  cout<<"Stack is Empty";
 else
 {
  Node *temp=top;
  while(temp!=NULL)
  {   cout<<temp->data<<" ";
   temp=temp->link;
  }
  cout<<"\n";
 }
 }

// Main function
int main()
{

 int choice, flag=1, value;

 //Menu Driven Program using Switch
 while( flag == 1)
 {
 cout<<"\n1.Push 2.Pop 3.showTop 4.displayStack 5.exit\n";
 cin>>choice;
 switch (choice)
 {
 case 1: cout<<"Enter Value:\n";
         cin>>value;
         push(value);
         break;
 case 2: pop();
         break;
 case 3: showTop();
         break;
 case 4: displayStack();
         break;
 case 5: flag = 0;
         break;
 }
 }

return 0;
}
OUTPUT:

1.Push 2.Pop 3.showTop 4.displayStack 5.exit
 1
Enter Value:
 33

1.Push 2.Pop 3.showTop 4.displayStack 5.exit
 1
Enter Value:
45

1.Push 2.Pop 3.showTop 4.displayStack 5.exit
 1
Enter Value:
66

1.Push 2.Pop 3.showTop 4.displayStack 5.exit
1
Enter Value:
77

1.Push 2.Pop 3.showTop 4.displayStack 5.exit
2

1.Push 2.Pop 3.showTop 4.displayStack 5.exit
4
66 45 33 

1.Push 2.Pop 3.showTop 4.displayStack 5.exit
3
Element at top is : 66
1.Push 2.Pop 3.showTop 4.displayStack 5.exit
5





More Articles of Shaik Aftab Ahmed:

Name Views Likes
C++ Program to Find the Frequency of Odd & Even Numbers in the given Matrix 275 1
C++ program to Sort a Linked List Using Merge Sort 258 1
C++ Program to Implement a Linked List representation of a Binary tree 254 1
C++ Program to Check for balanced parentheses in an expression 166 1
C++ Program to Perform Inorder, Preorder, Postorder traversals in a binary tree. 213 1
C++ program to print Indian flag 248 1
C++ program to Convert a multi level linked list to a singly linked list 164 1
C++ program to print right view of a Binary tree using queue 183 1
C++ Program to implement Huffman Coding Compression Algorithm 548 1
C++ Program to Create a Height Balanced Binary Tree 186 1
C++ program to implement Prims algorithm 263 1
C++ Program for BFS Traversal 197 1
C++ Progam to Evaluate a Prefix Expression 181 1
C++ Program to Implement Queue using Linked List 191 1
C++ implementation of Stack using Linked list 202 1
C++ program to find the intersection point of two linked lists 243 1
C++ program to count the inversions in the given array 228 1
C++ program to perform D.N.F sort 259 1
C++ program to print all possible subsets of a String 233 1
C++ program to count the number of ones in a binary representation of a number 243 1
C++ program to print all possible subsets of a set 264 1
C++ program to find the largest word in a String 235 1
C++ Program to print a matrix in Spiral order 258 1
C++ program to convert from Binary to Decimal, Octal to Decimal, Hexadecimal to Decimal 249 1
C limits library 277 1
Program to add two Binary numbers 248 1

Comments