C Program to Implement Stack Using Linked List

1. Introduction

A stack is a linear data structure that follows the Last In First Out (LIFO) principle. This means that the last element added to the stack will be the first element to be removed. Unlike using arrays, when we implement a stack using linked lists, it can grow dynamically and there's no need to specify a maximum limit.

2. Program Overview

In this program, we will:

1. Create a node structure for our linked list.

2. Implement the following stack operations using a linked list:

- Push: To add an element to the top of the stack.

- Pop: To remove the top element from the stack.

- Peek: To view the top element without removing it.

- Display: To display the elements of the stack.

3. Code Program

#include <stdio.h>
#include <stdlib.h>

// Define the structure for our linked list node
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Pointer to the top of our stack
Node* top = NULL;

// Function to push an element onto the stack
void push(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("Stack Overflow. Unable to allocate memory.\n");
        return;
    }
    newNode->data = value;
    newNode->next = top;
    top = newNode;
}

// Function to pop an element from the stack
int pop() {
    if (top == NULL) {
        printf("Stack Underflow. Stack is empty.\n");
        return -1;
    }
    Node* temp = top;
    int poppedData = temp->data;
    top = top->next;
    free(temp);
    return poppedData;
}

// Function to get the top element of the stack
int peek() {
    if (top == NULL) {
        printf("Stack is empty.\n");
        return -1;
    }
    return top->data;
}

// Function to display the stack
void display() {
    Node* temp = top;
    if (temp == NULL) {
        printf("Stack is empty.\n");
        return;
    }
    while (temp) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

int main() {
    push(10);
    push(20);
    push(30);
    printf("Top element: %d\n", peek());
    display();
    printf("Popped element: %d\n", pop());
    display();
    return 0;
}

Output:

Top element: 30
30 20 10
Popped element: 30
20 10

4. Step By Step Explanation

1. We begin by defining a node structure for our linked list. Each node contains an integer data and a pointer to the next node.

2. Our top pointer points to the top of the stack, which is initially NULL (indicating an empty stack).

3. The push function creates a new node, checks if memory allocation is successful, and then adds the new node to the top of the stack.

4. The pop function removes the top element from the stack, adjusts the top pointer, and frees the memory of the popped node.

5. The peek function simply returns the data of the top node without modifying the stack.

6. The display function iterates through the linked list (stack) and prints all the elements.

7. In the main function, we demonstrate pushing elements onto the stack, viewing the top element, popping an element, and displaying the stack.