Stacks: Abstract Data Type & Primitive Stack Operations

 📌 Stacks: Abstract Data Type & Primitive Stack Operations

A stack is a fundamental Abstract Data Type (ADT) that follows the Last In, First Out (LIFO) principle. This means that the last element added to the stack is the first one to be removed. Stacks are widely used in programming for tasks like expression evaluation, recursion management, and memory allocation.

In this post, we will cover:
✅ Definition & Characteristics of Stacks
✅ Stack Representation
✅ Basic Stack Operations (Push, Pop, Peek, and IsEmpty)
✅ Applications of Stacks

---

1️⃣ Stack as an Abstract Data Type (ADT)

A Stack ADT defines a collection of elements with the following operations:

• Push → Adds an element to the top of the stack.
• Pop → Removes and returns the top element of the stack.
• Peek (Top) → Returns the top element without removing it.
• isEmpty → Checks if the stack is empty.

A stack can be implemented using:

• Arrays (Fixed size, faster access but less flexible).
• Linked Lists (Dynamic size, but requires extra memory for pointers).

---

2️⃣ Stack Representation

(a) Array-Based Stack

Each element is stored in an array, and a variable top keeps track of the index of the last inserted element.

#define MAX 100
int stack[MAX]; 
int top = -1;  // Stack is empty initially

---

(b) Linked List-Based Stack

Each node contains data and a pointer to the next node. The top pointer always points to the last inserted node.

struct Node {
    int data;
    struct Node* next;
};
struct Node* top = NULL;

---

3️⃣ Primitive Stack Operations

(a) Push Operation (Insert an Element)

📌 Process:
1️⃣ Check if the stack is full (for array implementation).
2️⃣ Increment the top pointer.
3️⃣ Add the element at the new top position.

C Implementation (Array-Based Stack):

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

🔹 Time Complexity: O(1)

---

(b) Pop Operation (Remove an Element)

📌 Process:
1️⃣ Check if the stack is empty.
2️⃣ Retrieve the top element.
3️⃣ Decrease the top pointer.

C Implementation (Array-Based Stack):

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

🔹 Time Complexity: O(1)

---

(c) Peek Operation (View Top Element Without Removing It)

📌 Process:
1️⃣ Check if the stack is empty.
2️⃣ Return the top element.

C Implementation:

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

🔹 Time Complexity: O(1)

---

(d) IsEmpty Operation (Check if Stack is Empty)

📌 Process:

• If top == -1, return true (empty).
• Otherwise, return false (not empty).

C Implementation:

int isEmpty() {
    return (top == -1);
}

🔹 Time Complexity: O(1)

---

4️⃣ Applications of Stacks

✅ Function Call Management → Used in recursion to store function calls.
✅ Expression Evaluation & Conversion → Used in infix to postfix conversion and postfix evaluation.
✅ Undo/Redo Operations → Text editors maintain history using stacks.
✅ Browser Back & Forward Navigation → Maintains page history using stacks.
✅ Balancing Parentheses → Checking if an expression has balanced parentheses.

---

5️⃣ Summary Table of Stack Operations

Operation	Description	Time Complexity
Push	Inserts an element at the top	O(1)
Pop	Removes the top element	O(1)
Peek	Returns the top element	O(1)
isEmpty	Checks if the stack is empty	O(1)