Stack implementation using linked list, push, pop and display in C

Categories Data Structures 6 mins read

Write a C program to implement stack data structure using linked list with push and pop operation. In this post I will explain stack implementation using linked list in C language.

In my previous post, I covered how to implement stack data structure using array in C language. Here, in this post we will learn about stack implementation using linked list in C language. We also learn to perform basic stack operations with linked list implementation.

Stack implementation using linked list in C

Required knowledge

Functions, Linked List, Dynamic Memory Allocation, Stack

What is stack?

Stack is a LIFO (Last In First Out) data structure. It allows us to insert and remove an element in special order. Stack allows element addition and removal from the top of stack.

Operations performed on Stack

In this post I will explain how to perform basic operation on stack using linked list. Following are the basic operations performed on stack.

Before we perform any operation on stack, we must define its node structure.

// Stack node structure
struct stack 
{
    int data;
    struct stack *next;
} *top;

// Will contain size of stack
int size = 0;

How to push elements in stack using linked list

Insertion of new element to stack is known as push operation in stack. We can push elements at top of stack.

Step by step descriptive logic to push elements in stack.

  1. Check stack overflow, i.e. if (size >= CAPACITY), then print “Stack overflow” error message. Otherwise move to below step.
  2. Create a new stack node using dynamic memory allocation i.e. struct stack * newNode = (struct stack *) malloc(sizeof(struct stack));.
  3. Assign data to the newly created node using newNode->data = data;.
  4. Link new node with the current stack top most element. Say newNode->next = top; and increment size count by 1.
  5. Finally make sure the top of stack should always be the new node i.e. top = newNode;.

How to pop elements from stack using linked list

Removal of top most element from stack is known as pop operation in stack.

Step by step descriptive logic to pop elements from stack.

  1. If size <= 0 then throw “Stack is Empty” error, otherwise move to below step.
  2. Assign the top most element reference to some temporary variable, say struct stack *topNode = top;. Similarly copy data of stack top element to some variable say int data = top->data;.
  3. Make second element of stack as top element i.e. top = top->next;.
  4. Delete the top most element from memory using free(topNode);.
  5. Decrement stack size by one and return data.

Note: You can directly find size of stack using the size variable. It will always contains the current size of stack.

Program to implement stack data structure using linked list

/**
 * Stack implementation using linked list in C language.
 */

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>     // For INT_MIN

#define CAPACITY 10000  // Stack maximum capacity

// Define stack node structure
struct stack 
{
    int data;
    struct stack *next;
} *top;

// Stack size
int size = 0;



/* Function declaration to perform push and pop on stack */
void push(int element);
int  pop();


int main()
{
    int choice, data;

    while(1)
    {
        /* Menu */
        printf("------------------------------------\n");
        printf("    STACK IMPLEMENTATION PROGRAM    \n");
        printf("------------------------------------\n");
        printf("1. Push\n");
        printf("2. Pop\n");
        printf("3. Size\n");
        printf("4. Exit\n");
        printf("------------------------------------\n");
        printf("Enter your choice: ");

        scanf("%d", &choice);

        switch(choice) 
        {
            case 1: 
                printf("Enter data to push into stack: ");
                scanf("%d", &data);
                
                // Push element to stack
                push(data);
                break;

            case 2: 
                data = pop();

                // If stack is not empty
                if (data != INT_MIN)
                    printf("Data => %d\n", data);
                break;

            case 3: 
                printf("Stack size: %d\n", size);
                break;

            case 4: 
                printf("Exiting from app.\n");
                exit(0);
                break;

            default: 
                printf("Invalid choice, please try again.\n");
        }

        printf("\n\n");
    }


    return 0;
}



/**
 * Functiont to push a new element in stack.
 */
void push(int element)
{
    // Check stack overflow
    if (size >= CAPACITY)
    {
        printf("Stack Overflow, can't add more element to stack.\n");
        return;
    }

    // Create a new node and push to stack
    struct stack * newNode = (struct stack *) malloc(sizeof(struct stack));

    // Assign data to new node in stack
    newNode->data = element;

    // Next element after new node should be current top element
    newNode->next = top;        

    // Make sure new node is always at top
    top = newNode;

    // Increase element count in stack
    size++;

    printf("Data pushed to stack.\n");
}


/**
 * Function to pop element from top of stack.
 */
int pop()
{
    int data = 0;
    struct stack * topNode;
    
    // Check stack underflow
    if (size <= 0 || !top)
    {
        printf("Stack is empty.\n");

        // Throw empty stack error/exception
        // Since C does not have concept of exception
        // Hence return minimum integer value as error value
        // Later in code check if return value is INT_MIN, then
        // stack is empty
        return INT_MIN;
    }

    // Copy reference of stack top to some temp variable
    // Since we need to delete current stack top and make
    // Stack top its next element
    topNode = top;

    // Copy data from stack's top element
    data = top->data;

    // Move top to its next element
    top = top->next;

    // Delete the previous top most stack element from memory
    free(topNode);

    // Decrement stack size
    size--;

    return data;
}
------------------------------------
    STACK IMPLEMENTATION PROGRAM
------------------------------------
1. Push
2. Pop
3. Size
4. Exit
------------------------------------
Enter your choice: 2
Stack is empty.


------------------------------------
    STACK IMPLEMENTATION PROGRAM
------------------------------------
1. Push
2. Pop
3. Size
4. Exit
------------------------------------
Enter your choice: 1
Enter data to push into stack: 10
Data pushed to stack.


------------------------------------
    STACK IMPLEMENTATION PROGRAM
------------------------------------
1. Push
2. Pop
3. Size
4. Exit
------------------------------------
Enter your choice: 1
Enter data to push into stack: 20
Data pushed to stack.


------------------------------------
    STACK IMPLEMENTATION PROGRAM
------------------------------------
1. Push
2. Pop
3. Size
4. Exit
------------------------------------
Enter your choice: 1
Enter data to push into stack: 30
Data pushed to stack.


------------------------------------
    STACK IMPLEMENTATION PROGRAM
------------------------------------
1. Push
2. Pop
3. Size
4. Exit
------------------------------------
Enter your choice: 3
Stack size: 4


------------------------------------
    STACK IMPLEMENTATION PROGRAM
------------------------------------
1. Push
2. Pop
3. Size
4. Exit
------------------------------------
Enter your choice: 2
Data =&gt; 30


------------------------------------
    STACK IMPLEMENTATION PROGRAM
------------------------------------
1. Push
2. Pop
3. Size
4. Exit
------------------------------------
Enter your choice: 2
Data =&gt; 20


------------------------------------
    STACK IMPLEMENTATION PROGRAM
------------------------------------
1. Push
2. Pop
3. Size
4. Exit
------------------------------------
Enter your choice: 3
Stack size: 1


------------------------------------
    STACK IMPLEMENTATION PROGRAM
------------------------------------
1. Push
2. Pop
3. Size
4. Exit
------------------------------------
Enter your choice: 2
Data =&gt; 10


------------------------------------
    STACK IMPLEMENTATION PROGRAM
------------------------------------
1. Push
2. Pop
3. Size
4. Exit
------------------------------------
Enter your choice: 3
Stack size: 0


------------------------------------
    STACK IMPLEMENTATION PROGRAM
------------------------------------
1. Push
2. Pop
3. Size
4. Exit
------------------------------------
Enter your choice: 2
Stack is empty.


------------------------------------
    STACK IMPLEMENTATION PROGRAM
------------------------------------
1. Push
2. Pop
3. Size
4. Exit
------------------------------------
Enter your choice: 4
Exiting from app.