Codewhoop

# Stack using linked list

  • 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.
    4. Taking this as the basic structure of our Node:

# 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.

# Source Code - C++

#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;
}

Time Complexity - Each operation is O(1)