Implementation of stack using linked list

Program for implementing stack using linked list.

#include<stdio.h>
#include<malloc.h>

void push()
void pop()
void display()

struct node
{
    int info;
    struct node *link;
}*start=NULL, *new, *temp, *p;

typedef struct node N;

int main()
{
    int ch, a;

    do 
    {
        printf("\t\t\tLinked stack");
        printf("\n 1.Push");
        printf("\n 2.Pop");
        printf("\n 3.Display");
        printf("\n 4.Exit");
        printf("\n Enter your choice : ");
        scanf("%d",&ch);

        switch(ch)
        {
                case 1:
                        push();
                        break;
                case 2:
                        pop();
                        break;
                case 3:
                        display();
                        break;
                case 4:
                        exit(0);
                default:
                        printf("\nInvalid choice");
                        break;
        }
    }while(ch > 1 && ch < 3)
}

void push()
{
    new=(N*)malloc(sizeof(N));
    printf("\nEnter the item : ");
    scanf("%d",&new->info);
    new->link=NULL;
    // If stack is empty
    if(start==NULL)
        start=new;
    // Otherwise move to end(top) of the stack.
    else
    {
        p=start;
        while(p->link!=NULL)
        p=p->link;
        p->link=new;
    }
}

void pop()
{
    // If stack is empty
    if(start==NULL)
        printf("\nStack is empty");

    // If there is only one item.
    else if(start->link==NULL)
    {
        printf("\nThe deleted element is : %d",start->info);
        free(start);
        start=NULL;
    }
    // Else, move to last element.
    // 'p' holds last(top) element and 'temp' holds second last element.
    else
    {
        p=start;
        while(p->link!=NULL)
        {
            temp=p;
            p=p->link;
        }
        printf("\nDeleted element is : %d\n", p->info);
        temp->link=NULL;
        free(p);
    }
}

void display()
{
    if(start==NULL)
        printf("\nStack is empty");
    else
    {
        printf("\nThe elements are : ");
        p=start;
        while(p!=NULL)
        {
            printf("%d",p->info);
            p=p->link;
        }
        printf("\n");
    }
}


Keys : Implementation of stack using linked list, stack using linked list in c, stack implementation using linked list, stack implementation using linked list in c, linked list implementation of stack in c, stack using linked list, stack using c,c linked list,"c linked" list introduction, linked implimentation of stack in c language, program of implimentation of stack in linked lists in c language, singile linkedlists in c, list implementation using stack in c, how to implement stack in language c, linked list implementation of stack.

VN:F [1.9.22_1171]
Rating: 7.8/10 (86 votes cast)
VN:F [1.9.22_1171]
Rating: +29 (from 45 votes)
Implementation of stack using linked list, 7.8 out of 10 based on 86 ratings

10. April 2008 by Jishnu
Categories: C Programming | Tags: , , | 22 comments

Comments (22)

  1. i believe this is the best way to implemantate a stack using a linked list. The writing is simple and really understanding. i am thrilled and i wish this man could teach everyone this excellent way of writing.

  2. Thank u very much………

  3. Thank you,I got valuable information.

  4. ya its really good but while you are implementing its better to check the stack overflow condition along with stack underflow.

  5. I've tried to same the using Java with illustrative pictures.

    Stack using Linked Lists

  6. txxxxxxxxx alot dear

  7. OMG!!! This is working properly BUT this is not the way you wanna implement stack! Why would keep track of the bottom of the STACK!?!?!? And than go through the whole list when you want to do both pop or push!!! The much more efficient way is to just keep track of the top of the stack so you don’t need to go through the whole list!

  8. Hey it really worksss. Thanx a lot!!!!

  9. shall i give another method of implementation

  10. shall i give one type of implementation

  11. @Aishu, Sure you can,

  12. @jishnu, stack means LIFO
    i hve exe ur code is giving FIFO not LIFO

  13. thank u sir its really nice program

  14. those who r using borland try this

    /* MENU DRIVEN PROGRAM TO CONCATENATE TWO STRINGS AND FIND THE LENGTH OF A STRING USING POINTERS */
    #include
    #include
    #include
    void menu();
    void CONCAT(char*,char*);
    int LENGTH(char*);
    void main()
    {
    char str1[30],str2[30];
    int choice;

    while(1)
    {
    menu();
    scanf(“%d”,&choice);
    fflush(stdin);
    switch(choice)
    {
    case 1:printf(“Concatenation operation
    “);
    printf(”
    Enter first string”);
    gets(str1);
    fflush(stdin);
    printf(”
    Enter second string”);
    gets(str2);
    fflush(stdin);
    CONCAT(str1,str2);
    printf(“Concatenated String is
    “);
    puts(str1);
    break;

    case 2:(”
    Length operation
    “);
    printf(”
    Enter the string”);
    gets(str1);
    printf(”
    Length %d”,LENGTH(str1));
    break;
    case 3:exit(0);
    }
    getch();
    }
    }
    /* Menu function */
    void menu()
    {
    clrscr();
    printf(”
    1.Concatenate of two strings”);
    printf(”
    2.Find the length of the string”);
    printf(”
    3.Exit”);
    printf(”
    Enter your choice”);
    }
    /* function to concatenate two strings */
    void CONCAT(char *ptr1,char *ptr2)
    {
    while(*ptr1!=”)++ptr1;
    while(*ptr2!=”)
    {
    *ptr1=*ptr2;
    ++ptr1;
    ++ptr2;
    }
    *ptr1=”;
    return;
    }
    /* runction to find the length of the string */
    int LENGTH(char *ptr)
    {
    int i=0;
    while(*ptr!=”)
    {
    ++i;
    ++ptr;
    }
    return(i);
    }

    Program 2
    /*MENU DRIVEN PROGRAM TO FIND gcd OF TWO NUMBERS AND FACTORIAL OF GIVEN NUMBER*/
    #include
    #include
    #include
    void menu();
    int GCD(int,int);
    long FACTORIAL(int);
    void main()
    {
    int choice,n,m;
    while(1)
    {
    menu();
    scanf(“%d”,&choice);
    switch (choice)
    {
    case 1: printf(”
    GCD of two numbers
    “);
    printf(”
    Enter two numbers”);
    scanf(“%d%d”,&n,&m);
    printf(“GCD of Únd %d=%d”,n,m,GCD(n,m));
    break;
    case 2: printf(”
    Factorial of a number
    “);
    printf(”
    Input a number”);
    scanf(“%d”,&n);
    printf(“Factorial of %d = ”,n,FACTORIAL(n));
    break;
    case 3: exit(0);
    }
    getch();
    }
    }
    /* MENU FUNCTION */
    void menu()
    {
    clrscr();
    printf(”
    1.GCD of two numbers”);
    printf(”
    2.Factorial of a number”);
    printf(”
    3.Exit”);
    printf(”
    Enter your choice”);
    }
    /* function to find the GCD of two numbers */
    int GCD(int x,int y)
    {
    if(x==y)return x;
    if(x>y)return GCD(x-y,y);
    return GCD(x,y-x);
    }
    /* Function to find the factorial of a number */
    long FACTORIAL(int n)
    {
    if(n==0)return 1;
    return n*FACTORIAL(n-1);
    }

    Program 9(a)
    /* implementation of quicksort */
    #include
    #include
    void quicksort(int*,int,int);
    void partition(int*,int,int,int*);
    void main()
    {
    int a[20],n,i;
    clrscr();
    printf(“Enter the numer of elements
    “);
    scanf(“%d”,&n);
    printf(“Enter %d elements
    “,n);
    for(i=0;i scanf("%d",&a[i]);
    printf("The UnSorted elements are
    ");
    for(i=0;i printf(" %d",a[i]);
    printf("
    ");
    quicksort(a,0,n-1);
    printf("The Sorted elements are
    ");
    for(i=0;i printf(" %d",a[i]);
    printf("
    ");
    }
    /* function quick sort function */
    void quicksort(int a[],int low,int high)
    {
    int Pos;
    if(low {
    partition(a,low,high,&Pos);
    quicksort(a,low,Pos-1);
    quicksort(a,Pos+1,high);
    }
    }
    /* function to create partition */
    void partition(int a[],int low,int high,int *p)
    {
    int X,up,down,temp;
    X = a[low];
    up = high;
    down = low;
    while(down < up)
    {
    while((a[down]<=X)&&(down X)
    up = up - 1;
    if(down < up)
    {
    temp = a[down];
    a[down] = a[up];
    a[up] = temp;
    }
    }
    a[low] = a[up];
    a[up] = X;
    *p = up;
    }

    Program 9(b)
    /* IMPLEMENTATION OF INSERTION SORT */
    #include
    #include
    void main()
    {
    int a[100],n;
    int i,j,temp;

    clrscr();
    printf("
    Enter number of elements");
    scanf("%d",&n);
    printf("
    Enter array elements
    ");
    for(i=0;i scanf("%d",&a[i]);
    printf(" The unsorted list is
    "); /*it is correctly sorted*/
    for(i=0;i printf(" %d",a[i]);
    printf("
    ");
    for(i=1;i=1)
    {
    if(a[j] {
    temp = a[j];
    a[j] = a[j-1];
    a[j-1] = temp;
    }
    j=j-1;
    }
    }
    printf("
    The sorted list is
    ");
    for(i=0;i printf(" %d",a[i]);
    printf("
    ");
    getch();
    }

    Program 10
    /* IMPLEMENTATION OF BINARY SEARCH */
    #include
    #include
    int Binary_search(int *,int,int);
    void main()
    {
    int a[100],ele,pos,n,i;
    clrscr();
    printf("
    Enter the array size: ");
    scanf("%d",&n);
    printf("
    Enter %d elements in sorted order
    ",n);
    for(i=0;i scanf("%d",&a[i]);
    printf("Enter the element to search
    ");
    scanf("%d",&ele);
    pos= Binary_search(a, ele,n);
    if(pos == -1)
    printf("Element is not present
    ");
    else
    printf(" Element found in position: %d
    ",pos);
    }
    /* Function to perform Binary search */
    int Binary_search(int a[],int e, int m)
    {
    int low,high,mid;
    low=0;
    high = m-1;
    while(low<=high)
    {
    mid = (low+high)/2;
    if(e == a[mid])
    return(mid+1);
    if(e < a[mid])
    high = mid -1;
    else
    low = mid+1;
    }
    return(-1);
    }

    /* implementation and selection sort*/
    #include
    #include
    void main()
    {
    int a[100],n;
    int i,j,small,Pos;

    clrscr();
    printf("
    Enter number of elements");
    scanf("%d",&n);
    printf("
    Enter array elements
    ");
    for(i=0;i scanf("%d",&a[i]);

    printf("
    The UnSorted list is
    ");
    for(i=0;i printf(" %d",a[i]);
    printf("
    ");

    for(i=0;i {
    small = a[i];
    Pos = i;
    for(j=i+1;j if(a[j] < small)
    {
    small=a[j];
    Pos = j;
    }
    a[Pos] = a[i];
    a[i] = small;
    }
    printf("
    The Sorted list is
    ");
    for(i=0;i printf(" %d",a[i]);
    printf("
    ");
    getch();
    }

    /* IMPLEMENTATION OF STACK USING POINTERS */
    #include
    #include
    #include
    #include
    struct node
    {
    int info;
    struct node *link;
    };
    typedef struct node NODE;
    NODE *TOP;

    void Display(NODE*);
    void PUSH(int);
    int POP();
    void main()
    {
    int ele,ch;
    clrscr();
    TOP = NULL;
    printf("
    Stack Operations

    ");

    do
    {
    printf("
    1.PUSH");
    printf("
    2.POP");
    printf("
    3.EXIT");
    printf("

    Enter your choice : ");
    scanf("%d",&ch);
    switch(ch)
    {
    case 1:
    {
    printf("
    Enter element to add : ");
    scanf("%d",&ele);
    PUSH(ele);
    printf("
    The contents of the stackis
    ");
    Display(TOP);
    break;
    }
    case 2:
    {
    ele = POP();
    printf("
    Deleted element is : %d ",ele);
    printf("
    The contents of the stack is
    ");
    Display(TOP);
    break;
    }
    }
    }
    while(ch !=3);
    getch();
    }
    /* function to display linked list elements */
    void Display(NODE *Currptr)
    {
    while(Currptr!= NULL)
    {
    printf("%d ",Currptr->info);
    Currptr=Currptr->link;
    }
    printf(“NULL
    “);
    }
    /* function to add a node to astack */
    void PUSH(int ITEM)
    {
    NODE *NewNode;
    NewNode=(NODE*)malloc(sizeof(NODE));
    NewNode->info=ITEM;
    NewNode->link=TOP;
    TOP = NewNode;
    }

    /* function to delete a node from a stack */
    int POP()
    {
    NODE *CurrNode;
    int ele;
    if(TOP == NULL)
    {
    printf(”
    Stack Underflow”);
    getch();
    }
    CurrNode = TOP;
    ele = CurrNode->info;
    TOP = CurrNode->link;
    free(CurrNode);
    return(ele);
    }

    Program 4
    /*creation of linked list and insertion of an element into it */
    #include
    #include
    #include
    #include
    struct node
    {
    int info;
    struct node *link;
    };
    typedef struct node NODE;
    NODE *HEAD;
    void Create_link_list(int);
    void Display(NODE*);
    void Insert_Beginning(int);
    void Insert_End(int);
    void Insert_Position(int,int);
    void main()
    {
    int ele,Pos;
    char ch;
    clrscr();
    HEAD = NULL;
    printf(”
    Linked list creation

    “);
    do
    {
    printf(“Enter information field of the node
    “);
    scanf(“%d”,&ele);
    Create_link_list(ele);
    printf(“Add another node
    “);
    flushall();
    scanf(“%c”,&ch);
    }
    while(toupper(ch)==’y');
    printf(“The linked list is
    “);
    Display(HEAD);
    printf(”
    Insert Operation

    “);
    do
    {
    printf(”
    Choose Position To Insert:
    “);
    printf(”
    1.AT THE BEGINNING “);
    printf(”
    2.AT THE END”);
    printf(”
    3.AT A GIVEN POSITION”);
    printf(”

    Enter your choice : “);
    scanf(“%d”,&ch);

    switch(ch)
    {
    case 1:{
    printf(”
    Enter element to add : “);
    scanf(“%d”,&ele);
    Insert_Beginning(ele);
    Display(HEAD);
    break;
    }
    case 2:{
    printf(”
    Enter element to add:”);
    scanf(“%d”,&ele);
    Insert_End(ele);
    Display(HEAD);
    break;
    }
    case 3:{
    printf(”
    Enter element to add: “);
    scanf(“%d”,&ele);
    printf(”
    Enter position to add:”);
    scanf(“%d”,&Pos);
    Insert_Position(ele,Pos);
    Display(HEAD);
    break;
    }
    }
    }
    while(ch !=4);
    getch();
    }

    /* function to add a node to the linke list */
    void Create_link_list(int ele)
    {
    NODE *NewNode,*CurrPtr;

    NewNode=(NODE*)malloc(sizeof(NODE));
    NewNode->info=ele;
    NewNode->link=NULL;

    if(HEAD==NULL)
    HEAD=NewNode;
    else
    {
    CurrPtr=HEAD;
    while(CurrPtr->link!=NULL)
    CurrPtr=CurrPtr->link;

    CurrPtr->link=NewNode;
    }
    }

    /* function to display linked list elements */
    void Display(NODE *CurrPtr)
    {
    while(CurrPtr!=NULL)
    {
    printf(“%d “,CurrPtr->info);
    CurrPtr=CurrPtr->link;

    }
    printf(“NULL
    “);
    }

    /* function to add a node to the linked list at the beginning */
    void Insert_Beginning(int ITEM)
    {
    NODE *NewNode;

    NewNode=(NODE*)malloc(sizeof(NODE));

    NewNode->info=ITEM;
    NewNode->link=HEAD;
    HEAD = NewNode;
    }
    /* function to add a node to the linked list at the End */
    void Insert_End(int ITEM)
    {
    NODE *NewNode,*CurrPtr;

    NewNode=(NODE*)malloc(sizeof(NODE));
    NewNode->info=ITEM;
    NewNode->link=NULL;
    CurrPtr=HEAD;
    while(CurrPtr->link!=NULL)
    CurrPtr=CurrPtr->link;

    CurrPtr->link=NewNode;
    }

    /* function to add a node to the linked list after given node */
    void Insert_Position(int ITEM,int POS)
    {
    NODE *NewNode,*CurrPtr;
    int i;

    NewNode=(NODE*)malloc(sizeof(NODE));
    NewNode->info=ITEM;

    CurrPtr = HEAD;
    for(i=1;ilink;
    NewNode->link = CurrPtr->link;
    CurrPtr->link = NewNode;
    }

    Program 7
    /* IMPLEMENTATION OF QUEUES USING POINTERS */
    #include
    #include
    #include
    #include
    struct node
    {
    int info;
    struct node *link;
    };
    typedef struct node NODE;
    NODE *FRONT,*REAR;
    void Display(NODE*);
    void Add_Node(int);
    int Delete_Node();
    void main()
    {
    int ele,ch;

    clrscr();
    FRONT = NULL;
    REAR = NULL;
    printf(”
    Queue Operation

    “);

    do
    {
    printf(”
    1.Add_Node”);
    printf(”
    2.Delete_Node”);
    printf(”
    3.EXIT”);
    printf(”

    Enter your choice : “);
    scanf(“%d”,&ch);

    switch(ch)
    {
    case 1: {
    printf(”
    Enter element to add : “);
    scanf(“%D”,&ele);
    Add_Node(ele);
    Display(FRONT);
    break;
    }
    case 2:
    {
    ele = Delete_Node();
    printf(”
    Deleted element is : %d “,ele);
    printf(”
    Deleted element of the queue is
    “);
    Display(FRONT);
    break;
    }
    }
    }
    while(ch != 3);
    getch();
    }
    /* function to display linked list elements */
    void Display(NODE *CurrPtr)
    {
    while(CurrPtr!= NULL)
    {
    printf(“%d “,CurrPtr->info);
    CurrPtr=CurrPtr->link;
    }
    printf(“NULL
    “);
    }
    /* function to add a node to a queue */
    void Add_Node(int ITEM)
    {
    NODE *NewNode;

    NewNode=(NODE*)malloc(sizeof(NODE));
    NewNode->info=ITEM;
    NewNode->link=NULL;
    if(FRONT == NULL)
    {
    FRONT = NewNode;
    REAR = NewNode;
    }
    else
    REAR->link=NewNode;
    REAR=NewNode;
    }
    /* function to delete a node from a queue */
    int Delete_Node( )
    {
    NODE *CurrNode;
    int ele;
    if(FRONT == NULL)
    {
    printf(”
    Queue Underflow”);
    getch();
    }
    CurrNode = FRONT;
    ele = CurrNode->info;
    FRONT = CurrNode->link;
    free(CurrNode);
    return(ele);

    }

  15. code is gud indeed….but the “condition of overflow is missing in push() function..As the max size is 10 what if a person is inserting 11th node.though nodes are dynamically created but it shud check the condition for OVERFLOW.

  16. @Sasi,
    The program is LIFO. I ‘ve added some comments so that you can understand easily.

  17. @anamay mishra,
    Actually, We don’t need to the MAXSIZE parameter since we are doing dynamic memory allocation.
    I mistakenly included the #define value. Now I removed it.

  18. please try to write small program

  19. very waste codings

  20. this codings are not use to me

  21. while(ch>1 && ch < 3) how this will work in case of push()?
    but using as while(ch>=1 && ch<3) worked for me.

Leave a Reply