Trusted answers to developer questions
How to implement a stack in C using a linked list
Educative Answers TeamA 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 ) 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 time as the
rootcontains the pointer to the most recently added element. - Top(): It returns the element on top of the stack. It takes time as finding the value stored in the stack node pointed is a constant time operation given the
rootnode.
#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
Related Courses
