How to implement Linked List Using Stack?

To implement a stack using a linked list, you need to understand the basic operations of a stack (push, pop, peek) and how they can be mapped to operations on a linked list. Here is a detailed explanation and example code in C for implementing a stack using a singly linked list.

Key Concepts

1. Stack: A linear data structure that follows the Last In, First Out (LIFO) principle. The main operations are:

   • Push: Add an element to the top of the stack.
   • Pop: Remove the top element from the stack.
   • Peek: Retrieve the top element without removing it.
   • isEmpty: Check if the stack is empty.

2. Linked List: A data structure consisting of nodes where each node contains data and a reference (link) to the next node in the sequence. In a singly linked list, each node points to the next node, and the last node points to NULL.

Implementation Steps

1. Define the Node Structure: Each node will have two fields: data and next.
2. Initialize the Stack: Use a pointer top to keep track of the top of the stack.
3. Push Operation: Create a new node, set its data, and adjust pointers to add it to the top.
4. Pop Operation: Remove the node at the top and adjust the top pointer.
5. Peek Operation: Return the data of the top node without removing it.
6. isEmpty Operation: Check if the top pointer is NULL.

Example Code in C

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

// Define the node structure
struct Node {
    int data;
    struct Node* next;
};

// Initialize the top of the stack
struct Node* top = NULL;

// Function to push an element onto the stack
void push(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Stack overflow\n");
        return;
    }
    newNode->data = value;
    newNode->next = top;
    top = newNode;
    printf("Pushed %d onto the stack\n", value);
}

// Function to pop an element from the stack
void pop() {
    if (top == NULL) {
        printf("Stack underflow\n");
        return;
    }
    struct Node* temp = top;
    printf("Popped %d from the stack\n", temp->data);
    top = top->next;
    free(temp);
}

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

// Function to check if the stack is empty...