C Program to Implement a Stack using Singly Linked List

  • Write a program in C to implement a stack data structure using singly linked list.

We have to implement a Stack data structure using linked list. Linked list implementation of stack data structure must support basic stack operations like push, pop, peek and isEmpty.
Given a singly linked list whose node structure is as follows: 

struct node {
    int data;
    struct node *next;
}
  • We will maintain only one node pointer "top", which always points to the head node of linked list. This will ensure that we will add or remove node from one end of linked list.
  • We will start with an empty linked list, where top pointer is set to NULL.
  • Push Operation : We will dynamically allocate memory for a struct node variable(let's say temp). Then we will attach new node in front of linked list by setting temp- >next = top. Finally set top pointer to temp.(top = temp;)
  • Pop Operation : Remove head node(pointed by top pointer) of the linked list. Store the top pointer in a temp variable. Now, move top pointer to next node(top = top->next;). Deallocate memory of temp node using free.
  • Peek Operation : Returns the value of head node of linked list without removing it.(return top->data;)
  • Is Empty Check : Check if top pointer is NULL or not. If top pointer is null then stack is empty otherwise non-empty.
Advantage of Implementing a Stack as Linked List
Dynamic size of stack. We can increase or decrease size of stack at runtime. Unlike array implementation of stack, there is no limit of maximum element in stack.

C program to Implement a Stack using Singly Linked List

/*
 * C Program to Implement a Stack using Linked List
 */
#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int data;
    struct node *next;
}*top;

/*
Initialize an empty stack
*/
void initialize() {
    top = NULL;
} 

/*
Checks if Stack is empty or not
*/
int isEmpty() {
    if (top == NULL) 
        return 1;
    else
        return 0;
}

/*
Returns the top element of Stack
*/
int peek() {
    return top->data;
}

/* Count stack elements */
int getStackSize(struct node *head){
    /* Input Validation */
    if (head == NULL) { 
       printf("Error : Invalid stack pointer !!!\n");       
       return;  
    }
     
    int length = 0;
    while(head != NULL){
        head = head->next;
        length++;
    }
    return length;
}

/* 
Push an Element in Stack 
*/
void push(int num) {
    struct node *temp;
    temp =(struct node *)malloc(1*sizeof(struct node));
    temp->data = num;
    
    if (top == NULL) {
        top = temp;
        top->next = NULL;
    } else {
        temp->next = top;
        top = temp;
    }
}

/*
Pop Operation: Removes Top Element of the Stack
*/
void pop() {
    struct node *temp;
    if (isEmpty(top)) {
        printf("\nStack is Empty\n");
        return;
    } else {
        temp = top;
        top = top->next;
        printf("Removed  Element : %d\n", temp->data);   
        free(temp); 
    }
}

/*
 Prints the linked list representation of a stack  
*/
void printStack(struct node *nodePtr) {
  while (nodePtr != NULL) {
     printf("%d", nodePtr->data);
     nodePtr = nodePtr->next;
     if(nodePtr != NULL)
         printf("-->");
  }
  printf("\n");
}

void main() {
   /* Initialize Stack */
   initialize();
   /* Push Elements in stack */
   push(1);
   push(2);
   push(3);
   push(4);
   /* Prints Size of Stack */
   printf("Stack Size : %d\n", getStackSize(top));
   /* Printing top element of Stack */
   printf("\nTop Element : %d\n", peek());
   /* Printing Stack */
   printf("Stack as linked List\n");
   printStack(top);
   /* Removing elements from stack */
   pop();
   pop();
   pop();
   pop();
   pop();
   printStack(top);
   
   return;
}
Output
Stack Size : 4

Top Element : 4
Stack as linked List
4-->3-->2-->1
Removed  Element : 4
Removed  Element : 3
Removed  Element : 2
Removed  Element : 1

Stack is Empty
Posted by
Labels: