This blog is under construction

Tuesday, 19 February 2013

C Program For Linked List Implementation Of Stack

The major disadvantage of array implementation of stack is that the size of the stack is fixed.  If we are not familiar with the size of the stack, then we can implement it using linked list.


            top                                                      
            -----------------           -----------------                ----------------
           |  10    |       -|------->|   20    |     --|---------->|   30  |      --|---->X
           ------------------           -----------------                ----------------

Push:  Insert 40 to the stack.

       top(head)                                                                     
       -----------------        -----------------       ----------------       ----------------
      |  40    |       -|---->|   10    |     --|--->|   20  |      --|--->|  30   |     --|->X
       ------------------       -----------------       ----------------       ----------------

Pop:

            top(head)                                                      
            -----------------           -----------------                ----------------
           |  10    |       -|------->|   20    |     --|---------->|   30  |      --|---->X
           ------------------           -----------------                ----------------


See Also:
C Program For Array Implementation Of Queue
C Program For Array Implementation Of Stack
C Program For Linked List Implementation Of Stack
C Program For Linked List Implementation Of Queue
C Program For Double Ended Queue (Dequeue)
C Program To Implement Circular Stack
C Program To Implement Circular Queue
C Program To Implement Priority Queue


Example Program for Linked List Implementation Of Stack:



  #include <stdio.h>
  #include <stdlib.h>

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

  struct node *top = NULL;

  struct node* createNode(int data) {
        struct node *ptr = (struct node *) malloc(sizeof(struct node));
        ptr->data = data;
        ptr->next = NULL;
  }

  void push(int data) {
        struct node *ptr = createNode(data);
        if (!top) {
                top = ptr;
                return;
        }
        ptr->next = top;
        top = ptr;
  }

  void pop() {
        struct node *ptr;
        if (!top) {
                printf("Stack underflow\n");
                return;
        }
        ptr = top;
        ptr = ptr->next;
        free(top);
        top = ptr;
  }


  void display() {
        struct node *ptr = top;
        if (!ptr) {
                printf("Stack is Empty\n");
                return;
        }
        while (ptr) {
                printf("%-3d", ptr->data);
                ptr = ptr->next;
        }
        printf("\n");
        return;
  }


  int main() {
        int data, ch;
        while (1) {
                printf("1. Push\n2. Pop\n3. Display\n");
                printf("4. Exit\nEnter ur choice:");
                scanf("%d", &ch);
                switch (ch) {
                        case 1:
                                printf("Enter ur data:");
                                scanf("%d", &data);
                                push(data);
                                break;
                        case 2:
                                pop();
                                break;
                        case 3:
                                display();
                                break;
                        case 4:
                                exit(0);
                        default:
                                printf("Pleease enter right option\n");
                                break;
                }
        }
        return 0;
  }



  Output: (C Program For Linked List Implementation Of Stack)
  jp@jp-VirtualBox:~/cpgms/data_structures$ ./a.out
  1. Push
  2. Pop
  3. Display
  4. Exit
  Enter ur choice:1
  Enter ur data:10
  1. Push
  2. Pop
  3. Display
  4. Exit
  Enter ur choice:1
  Enter ur data:20
  1. Push
  2. Pop
  3. Display
  4. Exit
  Enter ur choice:1
  Enter ur data:30
  1. Push
  2. Pop
  3. Display
  4. Exit
  Enter ur choice:3
  30 20 10 
  1. Push
  2. Pop
  3. Display
  4. Exit
  Enter ur choice:2
  1. Push
  2. Pop
  3. Display
  4. Exit
  Enter ur choice:3
  20 10 
  1. Push
  2. Pop
  3. Display
  4. Exit
  Enter ur choice:4



No comments:

Post a Comment