How to implement a stack in C using a linked list

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;
}
Copyright ©2024 Educative, Inc. All rights reserved