The Blog

How To Implement A Stack Using Linked List in C?

How To Implement A Stack Using Linked List in C?

Have you heard about data structures? Do you want to know how to implement a stack using Linked List in C?

Don’t worry! We are here to make it simpler for you.

In this post, we will be looking at how to implement a stack using linked list in C. We will also be looking a little into what is a stack and what are the operations we can perform on it.

Before we get into the actual question of ‘How to implement a stack using linked list in C?’ Let us look into what are stacks and linked list for better understanding.

So, without any further delay, let us get started!

 

What is a Stack?

 

A stack is a linear data structure which follows the ‘Last In First Out’ order to perform its operations. The Last In First Out order is often termed as LIFO.

This means that the last element which is inserted in the stack will be the first element to be removed from it.

Let us think about it using an example. Imagine that you are making a stack of coins in front of you by placing some coins one over the other.

Now, the coin which is on top of the stack will be the first one to be removed from the stack. Also, this coin is also the last coin which was the last coin added to the stack.

Hence, it follows the Last In First Out order.

There are four basic operations of stack.

Let us know about these 4 operations to get to know how to implement a stack using linked list in C.

 

What are the 4 basic operations of stack?

 

The 4 basic operations of stack are as follows:

  1. Push: The push operation in stack is used to insert or add an element in the stack.
  2. Pop: The pop operation is stack is used to remove or delete an element from the stack.
  3. isFull: The isFull operation in stack checks if the stack is full or not. When the stack is full, no more elements can be pushed into it, hence it results in Stack Overflow.
  4. isEmpty: The isEmpty operation in stack checks if the stack is empty or not. When the stack is empty, no more elements can be popped from it, hence it results in Stack Underflow.

Now, let us look into what is a linked list.

 

What is Linked List?

 

Just like stack, a linked list is also a linear data structure. The elements in a linked list are connected or linked with each other with the help of pointers.

Each element of a linked list is called a ‘Node’.

Each node consists of two fields, one is for storing the data and the other is to store a link or a reference to the node which comes next in the list.

Linked lists are of various types: Singly linked list, doubly linked list and circular linked list.

 

How to implement a stack using linked list in C?

 

How to implement a stack using linked list in C?

In this post, to look at how to implement a stack using linked list in C, we will be use a singly linked list.

A singly linked list, as the name suggests can be traversed in one direction only. Hence, it is linked in a single direction.

Let us now look at the code for understanding how to implement a stack using linked list in C.

 

Code to implement a stack using linked list

 

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#include <limits.h>

struct Node

{

    int data;          // for storing the elements

    struct Node *next; // pointer of the last node

};

struct Node *top = NULL; // points to the first node of the linked list

// Push

void push(int element)

{

    struct Node *newNode = top;

    if (newNode == NULL)

    {

        newNode = (struct Node *)malloc(sizeof(struct Node));

        newNode->data = element;

        newNode->next = NULL;

        top = newNode; // top will point to the recently created node (newNode)

        printf("Element inserted! \n");

    }

    else

    {

        while (newNode->next != NULL)

        { // traversing through the linked list

            newNode = newNode->next;

        }

        // when newNode->next will be equal to NULL, we will come out of the while loop

        struct Node *lastNode = (struct Node *)malloc(sizeof(struct Node));

        newNode->next = lastNode;

        lastNode->data = element;

        lastNode->next = NULL;

        printf("Element inserted! \n");

    }

}

// isEmpty() function to check if the stack is empty

int isEmpty(){

        if(top == NULL){

            return 1;

        }else{

                return 0;

        }

}

// Pop

int pop(){

    struct Node *temp = top;

    int remove;

    if(isEmpty() == 1){

        return INT_MIN;

    }else if(temp->next == NULL){

        remove = top->data;

        free(temp);

        top = NULL;

    }else{

            struct Node *prevNode;

            while(temp->next != NULL){

                    prevNode = temp;

                    temp = temp->next;

            }

            // when we come out of the loop, temp will point to the last node

            remove = temp->data;

            prevNode->next = NULL;

            free(temp);

    }

    return remove;

}

void display(){

    struct Node *temp = top;

    if (temp == NULL)

    {

        printf("Stack is empty !! \n");

    }

    else

    {

        printf("Elements present in the list are : \n");

        while (temp != NULL)

        { // temp will be equal to NULL when we reach the end of the linked list

            if (temp->next != NULL)

                printf("%d ---> ", temp->data);

            else

                printf("%d ---> NULL", temp->data);

            temp = temp->next;

        }

        printf("\n");

    }

}

int main()

{

    int element, position, choice, searchFor, del;

    printf("\t\t STACK IMPLEMENTATION USING LINKED LIST \n");

    do

    {

        printf("\t OPERATIONS \n");

        printf("1. Push \n");

        printf("2. Pop \n");

        printf("3. Display Elements \n");

        printf("4. Exit \n");

        printf("Enter your choice : ");

        scanf("%d", &choice);

        switch (choice)

        {

        case 1:

            printf("Push \n");

            printf("Enter the element you want to insert : ");

            scanf("%d", &element);

            push(element);

            break;

        case 2:

            printf("Pop \n");

            del = pop();

            if (del == INT_MIN)

            {

                printf("Stack is empty!! \n");

            }

            else

            {

                printf("%d removed from the list. \n", del);

            }

            break;

        case 3:

            display();

            break;

        case 4:

            exit(0);

        default:

            printf("Wrong choice entered!! Please enter the correct choice. \n");

            break;

        }

        printf("\nPress enter to continue \n\n");

        getch();

    } while (1);

    return 0;

}

In this program, we have implemented a stack called ‘Node’ of the structure data type using linked list.

Node has two data members, ‘data’ for storing the elements and ‘next’ which is the reference to the last node in the stack which we have implemented using linked list.

In the main() function, we have used switch case to perform operations like push and pop in the stack.

Also, we have defined push(), pop(), isEmpty() and display() functions to perform the operations on the stack.

Let us look how the stack is implemented by executing the program.

 

Output:

Output

We start by performing the push operation on the stack by inserting 2 elements (23 and 34) into it.

To confirm if the elements are indeed present, we display the elements in the stack. Here, we can see that the elements are linked in a single direction.

The topmost element or the last element in the stack is 34.

Output

After this, we perform the pop operation on the stack.

Upon displaying the elements present in the stack, we see that the element which is popped out of the stack is 34 which was the last element.

Hence, we see that the stack is implemented using linked list and follows the LIFO order.

 

I hope, you have now understood how to implement a stack using linked list in C?

If  you need help with your C programming homework  don’t worry! Visit https://codingzap.com/ and our expert team will be there to help you out.

We also offer a wide range of programming and coding help services for you to benefit from. Don’t miss out!

Checkout our other listed services as well!

Computer science Homework Help

Java Homework Help 

C++ Programming Homework Help

Python Homework Help

PHP Homework Help

 

Sanjana Grover
Sanjana Grover

Leave a Comment