DSA Tutorial

STACK USING LINKED LIST

🔲 Stack using Linked List in DSA

A Stack is a linear data structure that follows the LIFO (Last In, First Out) principle. The last element added is the first to be removed. Unlike the array-based stack, a linked list-based stack does not have a fixed size and provides more flexibility as it dynamically grows and shrinks based on the operations performed.

Stack Implementation using Linked List

In this implementation, we use a linked list where each node of the list represents an element in the stack. The top of the stack is the head of the list. When an element is pushed, it is added at the front of the list. When an element is popped, the first element (head) is removed.

#include 
#include 

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

// Define the Stack structure
struct Stack {
    struct Node* top;
};

// Function to initialize the stack
void initStack(struct Stack* s) {
    s->top = NULL;
}

// Function to push an element onto the stack
void push(struct Stack* s, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = s->top; // New node points to the current top
    s->top = newNode; // Update the top to the new node
    printf("Pushed %d\n", value);
}

// Function to pop an element from the stack
int pop(struct Stack* s) {
    if (s->top == NULL) {
        printf("Stack Underflow\n");
        return -1;
    }
    int poppedData = s->top->data;
    struct Node* temp = s->top;
    s->top = s->top->next; // Move the top to the next node
    free(temp); // Free the memory of the popped node
    return poppedData;
}

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

// Function to check if the stack is empty
int isEmpty(struct Stack* s) {
    return (s->top == NULL);
}

int main() {
    struct Stack s;
    initStack(&s);

    push(&s, 10);
    push(&s, 20);
    push(&s, 30);

    printf("Popped: %d\n", pop(&s));
    printf("Top element: %d\n", peek(&s));

    return 0;
}

Applications of Linked List-based Stack

Linked list-based stacks offer flexibility due to their dynamic nature. Some use cases include:

Expression Evaluation: Stacks are used in evaluating expressions, particularly in converting infix expressions to postfix or prefix.
Function Call Stack: The linked list-based stack is used in the call stack for managing function calls and recursive calls.
Undo Mechanism: The undo feature in many applications is implemented using a stack that stores previous states in a linked list.
Backtracking Algorithms: Solving problems like mazes or puzzles often uses a linked list-based stack to backtrack and find solutions.

🚀 Advantages of Linked List-based Stack:
- Dynamic size, meaning no predefined limits.
- More efficient memory usage since it grows and shrinks based on demand.
- No overflow (except memory limitations) as with array-based implementations.

🚀 Try Implementing Linked List-based Stack:
- Add a function to display all the elements currently in the stack.
- Modify the program to include a function that counts the number of elements in the stack.
- Experiment with error handling, such as catching memory allocation failures.

🌟 Enjoyed Learning with Us?

Help others discover Technorank Learning by sharing your honest experience.
Your support inspires us to keep building!