#Implementation-of-stack-using-list-in-C-with-dataStructure

Implementation of Stack Using Linked List in C | DeveloperIndian.com

When it comes to implementing a stack in C, linked lists offer a dynamic and flexible alternative to arrays. This approach dynamically allocates memory, making it possible to avoid the fixed size limitations of array-based stacks. In this article, we’ll dive into the implementation of a stack using a linked list, explain the key operations, and highlight the advantages of using this approach.

What is a Stack?

A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. This means that the last element added to the stack is the first one to be removed. Stacks are widely used in various applications like function call management, expression evaluation, and backtracking.

Why Use a Linked List for Stack Implementation?

• Dynamic Memory Allocation: Linked lists allow the stack to grow and shrink dynamically, eliminating the risk of overflow due to fixed size.
• Efficient Memory Usage: Nodes are allocated memory as needed, avoiding the need to reserve unused space.
• Flexibility: Unlike arrays, linked lists do not require contiguous memory, making them a versatile choice for stack implementation.

Key Operations in Stack Using Linked List

1. Push: Adds an element to the top of the stack.
2. Pop: Removes the top element from the stack.
3. Peek: Returns the top element without removing it.
4. IsEmpty: Checks if the stack is empty.
5. IsFull: (Optional) Checks if the stack is full (rarely applicable with dynamic memory allocation).

Implementation of Stack Using Linked List in C

Below is the C code for implementing a stack using a linked list:

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

// Define the structure for a stack node
struct stack {
    int no;
    struct stack *next;
};

struct stack *top = NULL;

// Push operation
void push(int val) {
    struct stack *n;
    n = (struct stack *)malloc(sizeof(struct stack));            
    if (n == NULL) {
        printf("\nStack Overflow\n");
        return;
    }
    n->no = val;
    n->next = top;
    top = n;
    printf("\nNode Pushed: %d\n", val);
}

// Pop operation
int pop() {
    if (top == NULL) {
        printf("\nStack Underflow\n");
        return -999;
    }
    int val = top->no;
    struct stack *temp = top;
    top = top->next;
    free(temp);
    return val;
}

// Display stack
void show() {
    if (top == NULL) {
        printf("\nStack is Empty\n");
        return;
    }
    struct stack *p = top;
    printf("\nStack Elements: ");
    while (p != NULL) {
        printf("%d ", p->no);
        p = p->next;
    }
    printf("\n");
}

// Main function
int main() {
    int no, ch;
    do {
        printf("\n1. Push");
        printf("\n2. Pop");
        printf("\n3. Show");
        printf("\n0. Exit");
        printf("\nEnter your choice: ");
        scanf("%d", &ch);

        switch (ch) {
            case 1:
                printf("\nEnter number to push: ");
                scanf("%d", &no);
                push(no);
                break;
            case 2:
                no = pop();
                if (no != -999)
                    printf("\nPopped: %d\n", no);
                break;
            case 3:
                show();
                break;
            case 0:
                printf("\nExiting...\n");
                break;
            default:
                printf("\nInvalid choice\n");
        }
    } while (ch != 0);

    return 0;
}

How It Works

1. Push Operation: Creates a new node, assigns it the given value, and points it to the current top of the stack.
2. Pop Operation: Removes the top node and frees its memory. The next node becomes the new top.
3. Show Operation: Traverses the stack and prints each element.

Advantages of Using Linked List for Stacks

• Dynamic Memory Allocation: No predefined size limits; stack size adjusts dynamically.
• Efficient Utilization: Avoids unused reserved memory, as in arrays.
• No Overflow: Overflow occurs only when heap memory is exhausted.

Applications of Linked List-Based Stacks

• Backtracking Algorithms: Used in solving puzzles, such as mazes.
• Expression Evaluation: Essential for evaluating postfix and prefix expressions.
• Undo/Redo Functionality: Tracks changes in text editors.
• Function Call Management: Helps in managing recursive function calls.

Conclusion

In this article, we explored how to implement a stack using a linked list in C, its key operations, and why linked lists are a superior choice over arrays for dynamic memory management. This approach ensures flexibility and efficient memory utilization, making it ideal for scenarios where stack size cannot be determined in advance.

For more programming tutorials and resources, visit DeveloperIndian.com and boost your knowledge of data structures and algorithms!