STACK IMPLEMENTATION USING LINKED LIST


/*

This is a program for implementation of the stack using single linked list.

  The operations performed on a stack are  1)push(): This is the function which is for insertion(pushing)of an element into stack

              

      It is similar to the insertion of an element at the end of a single linked list

     

            see  the function insert_end() in the program for operations of single linked list

  2)pop(): This is the function which is for deletion(popping up) of an element from the stack

           It is similar to the deletion of an element at the end of a single linked list

     see  the function delete_end() in the program for operations of single linked list

  3)stack_display():This is the function which is for displaying the elements of a stack

    

      It is similar to the forward traversal of a single linked list

      see  the function ftraverse() in the program for operations of single linked list

note:

Stack is a list of elements in which insertions and deletions are at the same end of the list called top.

The other end is known as Bottom.Insertion is also known as push,deletion is also known as pop*/

#include<iostream.h>

#include<stdlib.h>

class stack

{

 int element;

 stack* next;

public:

 stack* push(stack*,int);

 stack* pop(stack*);

 void stack_display(stack*);

}*head,object;

stack* stack::push(stack* head,int key)

{

 stack* temp,*temp1;

 temp1=head;

 temp=new stack;

 temp->element=key;

 temp->next=NULL;

 if(head==NULL)

  head=temp;

 else

 {

 while(head->next!=NULL)

  head=head->next;

 head->next=temp;

 head=temp1;

 }

 return head;

}

stack* stack::pop(stack* head)

{

 stack* temp;

 if(head!=NULL)

 {

 temp=head;

 if(head->next==NULL)

 {

  cout<<“\nthe pooped element from the stack is: “<<head->element<<endl;

  return NULL;

 }

 while(head->next->next!=NULL)

 head=head->next;

 cout<<“the popped element from the stack is  “<<head->next->element;

 cout<<endl;

 head->next=head->next->next;

 head=temp;

 return head;

 }

 else

 {

  cout<<“\nit is impossible to pop an element from the stack as “;

  return head;

 }

}

void stack::stack_display(stack* head)

{

 if(head!=NULL)

 {

 while(head->next!=NULL)

 {

  cout<<head->element<<“->”;

  head=head->next;

 }

 cout<<head->element;

 cout<<endl;

 }

 else

  cout<<“the stack is empty\n”;

}  

void choice()

{

  int key,ch;

 cout<<“\nchoose the operation to be performed\n”;

 cout<<“\n1.push\t2.pop\t3.exit\n\n”;

 cin>>ch;

head=NULL;

while(1)

{

 switch(ch)

 {

 case 1:

  

 cout<<“——————————————————————————–\n”;

  cout<<“\nenter the element to be pushed\n”;

  cin>>key;

  head=object.push(head,key);

  cout<<“\nthe stack after push operation is \n”;

  object.stack_display(head);

  

 cout<<“——————————————————————————–\n”;

  break; case 2:

 cout<<“\n“““““““““““““““““““““““““““““““““““““““\n”;

  head=object.pop(head);

  cout<<“\nthe stack after pop operation is :\n”;

  object.stack_display(head);

  

 cout<<“\n“““““““““““““““““““““““““““““““““““““““\n”;

  break;

 case 3:

  exit(1);

 default:

  cout<<“\nenter the correct choice\n”;

  break;

 }

cout<<“\nchoose the operation to be performed\n”;

 cout<<“\n1.push\t2.pop\t3.exit\n”;

 cin>>ch;

}

}

void main()

{

choice();

}

About these ads

31 thoughts on “STACK IMPLEMENTATION USING LINKED LIST”

  1. how to push multiple data such that
    stack->push(“may”, 15);
    and how to pop such multiple data onto a stack
    Source: Data Structures Demystified by Keogh and Davidson

  2. ya..u r 100% rite frndzzz…………tis site is very much useful for my seminar………………………………frndzzzz…..if u have any details regarding data structure.pls mail me kavi.skr.raj@gmail.com
    i m in need…..pls………..

  3. Hi ! This websit is helpful but not too much for beginner be cause not use of com ment AND dnt to give the basic idea about linkelist,pointer,stack,etc.

  4. @:Vinod (Owner of Post):
    Problem:

    A stack’s primitive operations (push and pop) are O(1) by definition. Your program violates this by inserting at the end every-time you push an element and also when popping, you are traversing whole list to push an element and to pop also it’s same. So, basically your program makes the stack’s push, pop complexity to be O(n) in worst case.

    Solution: Instead of pushing at end, push at beginning, this operation will be O(1), maintain top-of-stack pointer also, which will be head. When you pop, you pop it from the top-of-stack pointer and this operation will also be O(1). This approach keeps pace with the stack’s primitive operation’s complexity definition.

    @Letormente: You can have one more data element in the stack class, say “string month;”, then your required push (and corresponding pop) operation can be handled. When popping, you return pointer to node structure.

  5. hey i need to know this!
    1) user enters a mathematical expression with parenthesis ( all 3 types (),{},[]) 2) The program checks if the parenthesis are correct in the mathematical expression

    can anyone help me with it ?

  6. Pingback: telecom news

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s