Data Structures and Algorithms in C (DSA)

📘 Stack (Using Array & Linked List)

A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. The most recent element added is the first one to be removed.

📚 Applications of Stack

• Expression evaluation and conversion (Infix, Prefix, Postfix)
• Backtracking (e.g., maze, puzzles)
• Function call management (Recursion stack)
• Undo/Redo operations
• Syntax parsing in compilers

📌 Basic Stack Operations

• Push: Add element to top of stack
• Pop: Remove top element
• Peek: View top element
• isEmpty: Check if stack is empty

🧱 Stack Implementation Using Array

#define MAX 100
int stack[MAX];
int top = -1;

void push(int val) {
    if (top >= MAX - 1)
        printf("Stack Overflow\n");
    else
        stack[++top] = val;
}

int pop() {
    if (top == -1) {
        printf("Stack Underflow\n");
        return -1;
    }
    return stack[top--];
}

int peek() {
    return stack[top];
}
  

📌 Stack Implementation Using Linked List

struct Node {
    int data;
    struct Node* next;
};

struct Node* top = NULL;

void push(int val) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = val;
    newNode->next = top;
    top = newNode;
}

int pop() {
    if (top == NULL) {
        printf("Stack Underflow\n");
        return -1;
    }
    int val = top->data;
    struct Node* temp = top;
    top = top->next;
    free(temp);
    return val;
}
  

📊 Array vs Linked List Stack

🧪 Real-Life Example – Browser History

A browser like UdaanPath’s Web App may use a stack to keep track of visited pages. The back button works by popping the last page visited from the stack.

🧠 Interview Questions

• Implement two stacks in one array
• Check for balanced parentheses using stack
• Convert infix to postfix expression
• Design a stack that supports getMin() in O(1)

📚 Practice Tasks

• Push and Pop elements using both implementations
• Reverse a string using stack
• Check palindrome using stack logic
• Implement a postfix calculator

✅ Summary

• Stack uses LIFO order
• Can be implemented using arrays or linked lists
• Widely used in memory management, parsing, undo features

📤 Coming Next

In the next chapter, we’ll implement the Queue using both Arrays and Linked Lists.