Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

data structure
c
stack
linked list

How to implement a stack in C using a linked list

Educative Answers Team

A stack is a linear data structure that follows the Last in, First out principle (i.e.​ the last added elements are removed first).

This abstract datatype can be implemented in C in multiple ways. One such way is by using a linked list.

​Pro of using a linked list:

  • The stack grows according to the user’s requirements.

Con of using a linked list:

  • Extra memory required to store the pointers.

Implementation

The following code will implement three functions supported by a stack:

  • Push(a): It adds element a on top of the stack. It takes O(1O(1) time as each stack node is inserted in the front of the linked list.
  • Pop(): It removes the element on top of the stack. It also takes O(1)O(1) time as the root contains the pointer to the most recently added element.
  • Top(): It returns the element on top of the stack. It takes O(1)O(1) time as finding the value stored in the stack node pointed is a constant time operation given the root node.
#include<stdio.h>
#include<stdlib.h>
// Struct to hold the data and the pointer to the next element.
struct element{ 
    char data; 
    struct element* next; 
};
// Append the new element to the start of the stack
void push(char data, struct element** stack){
    struct element* Element = (struct element*)malloc(sizeof(struct element)); 
    Element -> data = data; 
    Element -> next = *stack;  
    (*stack) = Element;  
}
// Remove element from the top of the stack
void pop(struct element** stack){
    if(*stack != NULL){
        printf("Element popped: %c\n",(*stack) -> data);
        struct element* tempPtr = *stack;
        *stack = (*stack) -> next;
        free(tempPtr);
    }
    else{
        printf("The stack is empty.\n");
    }
}
// Display the element at the top of the stack
void top(struct element* stack){
    if(stack != NULL){
    printf("Element on top: %c\n", stack -> data);
    }
    else{
        printf("The stack is empty.\n");
    }
}
int main() {
    struct element* root = (struct element*)malloc(sizeof(struct element));
    root -> data = 'a';
    root -> next = NULL;
    top(root);
    push('b',&root);
    top(root);
    push('c',&root);
    top(root);
    pop(&root);
    top(root);
    pop(&root);
    top(root);
    pop(&root);
    top(root);
    pop(&root);
    return 0;
}

RELATED TAGS

data structure
c
stack
linked list
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring