Monday, 11 September 2017

Implementation of Stack using Linked List in C++

The linked list  allow users to insert or delete an element at any position in the list, that is we can insert or delete an element at the beginning, at the end ,or at any intermediate position.

A stack is defined as a restricted list where all insertions and deletions are made only at one end,the top.Each stack abstract data type has a data member, commonly named as top, which point to the topmost element in the stack. There are two basic operations push and pop that can be performed on the stack; insertion of an element in the stack is called push or deletion of an element from the stack is called pop. In stacks, we can not access data elements from any intermediate positions other than the top position.

A linked list is ordered collection of data in which each element contain a minimum of two values, data and link to its successor(and/or predecessor). A list with one link field using which every element is associated to its successor is known as singly linked list. in a link list, before adding any element to the list, a memory space for that node must be allocated.
Each node of the linked list must have at least the following two fields ( data + link field)
For implementing stack by link list we have to insert new node only from one end whether from the head  or from tail side.
Note :- here head contain the address of first node of the link list and tail contain the end of a link list. it depend upon the programmer from which side they want to use for insert element into the link list. 



Implementation of Stack using Linked List 

// header files

#include<iostream>

using namespace std;
// structure of the link list node having data and link field


struct node

{
    int data;
    node *next;
};




// declaration of class in which function are defined for stack operation

class stack_ll
{
    public:
   node *top;
   public:
   stack_ll()
   {
       top=NULL;
   }


// definition of push function of stack

   void push(int value)
   {
       node *temp=new node;
       temp->data=value;
       temp->next=NULL;
       if(top==NULL)
       {
           top=temp;
           temp=NULL;
       }
       else
       {
           temp->next=top;
           top=temp;
           temp=NULL;
       }
   }


// definition of pop function of stack

   void pop()
   {
       if(top==NULL)
       {
           cout<<"nothing to delete";
       }  
       else
       {
           top=top->next;
       }
   }


// definition of display function of stack

   void display()
   {
       node *temp=new node;
       temp=top;
       while(temp!=NULL)
       {
           cout<<temp->data<<" ";
           temp=temp->next;
       }
   }  
};


// main function with different calls

int main()
{
    int i,j,k,value, num;
    stack_ll a;
    cin>>j; 


for(i=1; i<=j; i++)

    {
        cin>>value;
        a.push(value);
    }
    a.display();
    cout<<"n";
    a.pop();
    a.display();
    return 0;
}



Online Compilation of above program.







Thanks
Mukesh Rajput


No comments:

Post a Comment

Thanks
Mukesh Rajput