C Stack Using Linked list

Summary: in this tutorial, you will learn how to implement stack data structure using a linked list.

If you don’t know anything about the stack data structure, you can follow the stack implemented using an array tutorial.

The disadvantage of a stack implemented using an array is that its size is fixed and needs to be specified at compile time. This stack implementation is often impractical. To make the size of the stack to be dynamic and determined at run-time, we need to implement it using a linked list. By doing this, the size of the stack can shrink or grow on demand during the program execution. A stack implemented using a linked list is also known as a linked stack.

First, we declare the element of the stack:

struct node
{
    int data;
    struct node* next;
};
Code language: C++ (cpp)

Second, we need to initialize the stack by setting the head pointer of the stack to NULL:

void init(struct node* head)
{
    head = NULL;
}
Code language: C++ (cpp)

Third, to push an element into the stack, we create a new node, and point the stack pointer to the new node e.g., to push the first element:

To push the second element:

/*
    push an element into stack
*/
struct node* push(struct node* head,int data)
{
    struct node* tmp = (struct node*)malloc(sizeof(struct node));
    if(tmp == NULL)
    {
        exit(0);
    }
    tmp->data = data;
    tmp->next = head;
    head = tmp;
    return head;
}
Code language: C++ (cpp)

To pop an element from the stack, we need to get the data of the element, point the stack pointer to the next element and remove it. The following picture illustrates how to pop the top element ( 5) from the stack.

struct node* pop(struct node *head,int *element)
{
    struct node* tmp = head;
    *element = head->data;
    head = head->next;
    free(tmp);
    return head;
}
Code language: C++ (cpp)

To display the stack content, we traverse the stack elements from the first element to NULL.

void display(struct node* head)
{
    struct node *current;
    current = head;
    if(current!= NULL)
    {
        printf("Stack: ");
        do
        {
            printf("%d ",current->data);
            current = current->next;
        }
        while (current!= NULL);
        printf("\n");
    }
    else
    {
        printf("The Stack is empty\n");
    }

}
Code language: C++ (cpp)

Putting it all together.

Linked stack header file (stack.h)

/*
 * File:    stack.h
 * Author:  learnc.net
 * Purpose: linked stack header file
 */
#ifndef LINKEDSTACK_H_INCLUDED
#define LINKEDSTACK_H_INCLUDED

int empty(struct node *s);
struct node* push(struct node *s,int data);
struct node* pop(struct node *s,int *data);
void init(struct node* s);
void display(struct node* head);
#endif // LINKEDSTACK_H_INCLUDED
Code language: C++ (cpp)

Linked stack source code file (stack.c)

/*
 * File:    stack.c
 * Author:  learnc.net
 * Purpose: linked stack implementation
 */

#include <stdio.h>

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

/*
    init the stack
*/
void init(struct node* head)
{
    head = NULL;
}

/*
    push an element into stack
*/
struct node* push(struct node* head,int data)
{
    struct node* tmp = (struct node*)malloc(sizeof(struct node));
    if(tmp == NULL)
    {
        exit(0);
    }
    tmp->data = data;
    tmp->next = head;
    head = tmp;
    return head;
}
/*
    pop an element from the stack
*/
struct node* pop(struct node *head,int *element)
{
    struct node* tmp = head;
    *element = head->data;
    head = head->next;
    free(tmp);
    return head;
}
/*
    returns 1 if the stack is empty, otherwise returns 0
*/
int empty(struct node* head)
{
    return head == NULL ? 1 : 0;
}

/*
    display the stack content
*/
void display(struct node* head)
{
    struct node *current;
    current = head;
    if(current!= NULL)
    {
        printf("Stack: ");
        do
        {
            printf("%d ",current->data);
            current = current->next;
        }
        while (current!= NULL);
        printf("\n");
    }
    else
    {
        printf("The Stack is empty\n");
    }

}
Code language: C++ (cpp)

Linked stack test program:

/*
 * File   : stack.c
 * Author : learnc.net
 * Purpose: linked stack program
 */

#include <stdio.h>

#include "linkedstack.h"

int main()
{
    struct node* head = NULL;
    int size, element;
    int counter = 0;

    printf("Enter the number of stack elements:");
    scanf("%d",&size);

    printf("--- Push elements into the linked stack ---\n");

    init(head);

    while(counter < size)
    {

        printf("Enter a number to push into the stack:");
        scanf("%d",&element);
        head = push(head,element);
        display(head);
        counter++;
    }

    printf("--- Pop elements from the linked stack --- \n");
    while(empty(head) == 0)
    {
        head = pop(head,&element);
        printf("Pop %d from stack\n",element);
        display(head);
    }

    return 0;
}
Code language: C++ (cpp)

The output of the program:

Enter the number of stack elements:5
--- Push elements into the linked stack ---
Enter a number to push into the stack:1
Stack: 1
Enter a number to push into the stack:2
Stack: 2 1
Enter a number to push into the stack:3
Stack: 3 2 1
Enter a number to push into the stack:4
Stack: 4 3 2 1
Enter a number to push into the stack:5
Stack: 5 4 3 2 1
--- Pop elements from the linked stack ---
Pop 5 from stack
Stack: 4 3 2 1
Pop 4 from stack
Stack: 3 2 1
Pop 3 from stack
Stack: 2 1
Pop 2 from stack
Stack: 1
Pop 1 from stack
The Stack is empty

Process returned 0 (0x0)   execution time : 3.793 s
Press any key to continue.
Code language: plaintext (plaintext)

In this tutorial, you have learned how to implement the stack data structure using a linked list in C.