Thursday, 9 March 2017

Program for Implementation of Stack Using Linked List

This question has appeared in the interviews of following companies:

Microsoft, FactSet, Codenation, Samsung

Source: geeksforgeeks

In the question you have to create a stack to perform using Linked List. Remember that when you creating the stack using Linked List then the first node of the linked list should contain the top element of the stack.

For Example:

If a Linked List is: 2->5->7->1  and top pointer is pointed to node containing data element 2.
Then, after push operation of element 9 Linked List will be: 9->2->5->7->1 and top pointer will be pointed to the node containing data element 9.
                   
                             

ALGORITHM:

1.   set top=NULL /*top is the pointer to the head node */
2.   FOR PUSH OPERATIONS
3.   Check if top==NULL:
4.               set:  top.data=value
5.               set:  top.next=NULL
6.         else:
7.               create a temporary node
8.               set: temp.data=value
9.               set: temp.next=top
10.              set: top=temp
11.        End IfElse
12.  Repeat step 2 to 11 for PUSH operations
13.  FOR POP OPERATIONS
14.  Check if top=NULL:
15.            print: stack is empty
16.        Else:
17.            set:   element=top.data
18.            set:   top=top.next  /*updating the top node*/
19.        End IfElse
20.  Exit


PROGRAM:


#include <stdio.h>
#include <stdlib.h>
using namespace std;

struct StackNode{
    int data;
    struct StackNode *next;
};

class Stack_using_linkedlist{
 
    private:
          StackNode *top=NULL;
    public:
          void push(int x);
          int pop();
};

void Stack_using_linkedlist::push(int x)
{
    
    if(top==NULL)
    {
           top=(struct StackNode*)malloc(sizeof(struct StackNode));
           top->data=x;
           top->next=NULL;
    }
    else
    {
           struct StackNode *newnode;
           newnode=(struct StackNode*)malloc(sizeof(struct StackNode));
           newnode->data=x;
           newnode->next=top;
           top=newnode;
    }
}
int Stack_using_linkedlist::pop()
{
    if(top==NULL)
    {
           printf("\nStack is in underflow condition, element can't be popped !");
           return 0;
    }
    else
    {
           int element;
           element=top->data;
           top=top->next;
           return element;
    }
}
int main()
{

    int element,ch,choice;
    Stack_using_linkedlist  sll;
    do
    {
           printf("\n--Main Menu--");
           printf("\n1. PUSH Operation");
           printf("\n2. POP Operation");
           printf("\nEnter your choice: ");
           scanf("%d",&choice);
           switch(choice)
           {
                case 1:  printf("\n\nEnter the element: ");
                         scanf("%d",&element);
                         sll.push(element);
                         break;
                case 2:  element=sll.pop();
                         if(element==0)
                         {
                            break;
                         }
                         else
                         {
                              printf("\nThe popped element is: %d",element);
                              break;
                         }
                default: printf("\nYou have entered the wrong choice, try again");
           }
           printf("\n\nDo you want to continue[1/0]: ");
           scanf("%d",&ch);
    }while(ch==1);
    return 0;
}

OUTPUT:





EmoticonEmoticon