November 13, 2012

Stack implementation through Linked list in C

We can avoid the size limitation of a stack implemented with an array, with the help of a linked list to hold the stack elements. As needed in case of array, we have to decide where to insert elements in the list and where to delete them so that push and pop will run at the fastest. Primarily, there are two operations of a stack; push() and pop(). A stack carries lifo behavior i.e. last in, first out. You know that while implementing stack with an array and to achieve lifo behavior, we used push and pop elements at the end of the array. Instead of pushing and popping elements at the beginning of the array that contains overhead of shifting elements towards right to push an element at the start and shifting elements towards left to pop an element from the start. To avoid this overhead of shifting left and right, we decided to push and pop elements at the end of the array. Now, if we use linked list to implement the stack, where will we push the element inside the list and from where will we pop the element? There are few facts to consider, before we make any decision:
Insertion and removal in stack takes constant time. Singly linked list can serve the purpose. Hence, the decision is to insert the element at the start in the implementation of push operation and remove the element from the start in the pop implementation.
clip_image001
clip_image002
There are two parts of above figure.On the left hand, there is the stack implemented using an array. The elements present inside this stack are 1, 7, 5 and 2. The most recent element of the stack is 1. It may be removed if the pop() is called at this point of time. On the right side, there is the stack implemented using a linked list. This stack has four nodes inside it which are liked in such a fashion that the very first node pointed by the head pointer contains the value 1. This first node with value 1 is pointing to the node with value 7. The node with value 7 is pointing to the node with value 5 while the node with value 5 is pointing to the last node with value 2. To make a stack data strcuture using a linked list, we have inserted new nodes at the start of the linked list.
We are going to implement stack through linked list. Here is the code of stack implementation in C.



#include "stdio.h"
#include "stdlib.h"
#include "conio.h"



void pop();
void push(int value);
void display();


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

struct node *top=NULL,*temp;

int main()
{
    int choice,data;
  
   
    while(1) //infinite loop is used to insert/delete infinite number of elements in stack
    {
       
        printf("\n1.Push\n2.Pop\n3.Display\n4.Exit\n");
        printf("\nEnter ur choice:");
        scanf("%d",&choice);
        switch(choice)
        {
        case 1:  //To push a new element into stack
           
           
            printf("Enter a new element :");
            scanf("%d",&data);
            push(data);
            break;
           
        case 2: // pop the element from stack
            pop();
            break;
           
        case 3: // Display the stack elements
            display();
            break;
        case 4: // To exit
            exit(0);
        }
       
    }     
getch();
return 0;
}

push(int data)
{
         temp=(struct node *)malloc(sizeof(struct node)); // creating a space for the new element.
         temp->data=data;
            temp->link=top;
            top=temp;
                    
}

pop()
{
            if(top!=NULL)
            {
                printf("The poped element is %d",top->data);
                top=top->link;
            }
            else
            {
                printf("\nStack Underflow");   
            }
           
}

display()
{
         temp=top;
            if(temp==NULL)
            {
                printf("\nStack is empty\n");
            }
           
            while(temp!=NULL)
            {
                printf(" %d ->",temp->data);
                temp=temp->link;
            }
               
}





9 comments:

  1. This comment has been removed by a blog administrator.

    ReplyDelete
  2. Wonderful...gave me some initution on this topic

    ReplyDelete
  3. This comment has been removed by the author.

    ReplyDelete
  4. Replies
    1. You can find the solution here http://www.techcrashcourse.com/2014/10/c-program-examples.html

      Delete
  5. This comment has been removed by the author.

    ReplyDelete


  6. Very informative article.Thank you author for posting this kind of article .



    http://www.wikitechy.com/view-article/explain-in-details-about-array-implementation-of-linked-list-in-c



    Both are really good,.
    Cheers,
    Venkat

    ReplyDelete
  7. good and efficient solution, thanks man
    Refer below link for code in c++, python and java
    http://code2begin.blogspot.com/2016/11/stack-implementation-using-array.html

    ReplyDelete

C program to Read From a File

#include <stdio.h> #include <stdlib.h> void main() {     FILE *fptr;     char filename[15];     char ch;   ...