Tim's Notes

Activity Log

Stack Data Type in C

2 min read

Today we will discuss how to implement a Dynamic Stack in C using a linked list approach. We will also implement the basic stack operations, such as push, pop, peek etc.

let’s begin;

Stack Data Type

A stack is a linear data structure that follows the Last In First Out (LIFO) principle. The last element that is added to the stack is the first element to be removed. We will implement a stack using a linked list, in order to have a dynamic, resizable stack.

Implementation

#include <stdio.h>
#include <stdlib.h>
 
typedef struct Node {
    int data;
    struct Node* next;
} Node;
 
void push(Node** top, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        // too many elements
        printf("Heap overflow!\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = *top;
    *top = newNode; // increase the top pointer
}
 
int pop(Node** top) {
    if (*top == NULL) {
        // no elements to pop
        printf("Stack underflow!\n");
        exit(1);
    }
    Node* temp = *top;
    int popped = temp->data;
    *top = (*top)->next; // decrease the top pointer
    free(temp);
    return popped;
}
 
int peek(Node* top) {
    if (top == NULL) {
        printf("Stack is empty!\n");
        exit(1);
    }
    return top->data;
}
 
void print_stack(Node* top) {
    Node* temp = top;
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}
 
int main() {
    Node* stack = NULL;
 
    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);
 
    print_stack(stack);
 
    // pop the top element
    printf("Popped: %d\n", pop(&stack));
 
    print_stack(stack);
    return 0;
}
devnyxie:stacks$ ./a.out
# that's what will happen under the hood:
# 1. push 10
#   top -> [10 | NULL]
# 2. push 20
#   top -> [20 | *] -> [10 | NULL]
# 3. push 30
#   top -> [30 | *] -> [20 | *] -> [10 | NULL]
30 20 10 # 30 is the top of the stack
Popped: 30
20 10 # 20 is the top of the stack

Info

In the push() operation, we check for overflow by verifying if memory allocation succeeds, and in the pop() operation, we check for underflow when the stack is empty. While underflow is a common issue in linked list-based stacks, overflow occurs only when the system runs out of available heap memory (Memory Exhaustion).

Graph View

Tags