What is Stack

Stack ek linear data structure hai jo LIFO (Last In First Out) principle pe kaam karta hai. Matlab jo element sabse last me add hota hai, wahi sabse pehle remove hota hai.

Example: Haatho mein bangles, jo bangle sabse last mein pehni gyi wo hi sabse pehle niklegi. Ham bangles nikalte time rule ko order ko break nhi kar sakte hai.

C++ mein stack ham do tareeko se implement kar sakte hai, first manually using Array's or Linked Lists and second C++ STL (Standard Template Library) ki stack class ka use kar sakte hai.

Advantages of Stack

1. Simple and Efficient: Ye implement karna easy hota hai aur bahut saare operations like Push, Pop, and Peek O(1) time complexity mein perform ho jaate hai.
2. Memory Efficiency: Ye contiguous memory allocation use karta (agar Array se implemented ho) jo overhead ko kam karta hai.
3. Syntex Parsing: Stack ka use compiler design karne ke liye bhi hota hai kioki iski help se ham ye check kar sakte hai ki program mein parentheses balanced hai ya nhi ?

Disadvantages of Stack

1. Limited Access: Sirf top element hi access ho sakta hai, random element access nhi kar sakte.
2. Fixed Size (Array Implementation): Stack Overflow jaisi condition arise ho sakti hai agar stack capacity exceed ho gyi.
3. No Flexibility: Stack strictly LIFO principle ko follow karta hai, jiski wajah se kuch operations inefficient hote hai like middle element ko access karna.

Applications of Stack

1. Expression Evaluation (Postfix, Prefix): Computer mathematical expressions ko solve karne me stack ka use karta hai.
2. Undo Functionality in Editors: Jab bhi aap kisi word processor me undo karte ho, vo functionality stack ke through implement hoti hai.
3. Backtracking Algorithms: Mostly backtracking algorithms stack ka use karti hai like, sudoku solver, maze solving, and DFS (Depth First Search) in graphs.
4. Function Call Handling: Jab program kisi function ko call karta hai, wo function call stack mein store hoti hai.
5. Parenthesis Matching: Brackets valid hai ya nhi ye bhi ham stack ki help se check karte hai.

Implementation of Stack using Array

#include <iostream>
using namespace std;

#define SIZE 100 // Stack ka maximum size

class Stack {
private:
    int arr[SIZE]; // Array to store stack elements
    int top;       // Top index

public:
    Stack() {
        top = -1; // Initial top -1 matlab stack is empty
    }

    // Push operation
    void push(int val) {
        if (top >= SIZE - 1) {
            cout << "Stack Overflow!" << endl;
            return;
        }
        arr[++top] = val;
        cout << val << " pushed to stack." << endl;
    }
    // Pop operation
    void pop() {
        if (top < 0) {
            cout << "Stack Underflow!" << endl;
            return;
        }
        cout << arr[top--] << " popped from stack." << endl;
    }

    // Peek (top element)
    int peek() {
        if (top < 0) {
            cout << "Stack is empty." << endl;
            return -1;
        }
        return arr[top];
    }

    // Check if stack is empty
    bool isEmpty() {
        return top == -1;
    }

    // Display stack elements
    void display() {
        if (isEmpty()) {
            cout << "Stack is empty." << endl;
            return;
        }
        cout << "Stack elements: ";
        for (int i = top; i >= 0; i--) {
            cout << arr[i] << " ";
        }
        cout << endl;
    }
};

int main() {
    Stack s;

    s.push(10);
    s.push(20);
    s.push(30);

    s.display();

    cout << "Top element is: " << s.peek() << endl;

    s.pop();
    s.display();

    return 0;
}

Explanation:

• arr[SIZE] ek fixed-size array hai jo stack elements ko store karta hai.
• top batata hai ki last element ka index kya hai.
• push() new element stack ke upar add karta hai.
• pop() top element ko remove karta hai.
• peek() sirf top element ko return karta hai without removing.
• isEmpty() check karta hai ki stack empty hai ya nahi.

Note: In functions ko aap pen and copy mein likh kar dry run karo aur khud se samjhne ka try karo.

Stack Implementation using Linked List

#include <iostream>
using namespace std;

// Node class
class Node {
public:
  int data;
  Node* next;

  Node(int val) {
    data = val;
    next = NULL;
  }
};

// Stack class
class Stack {
private:
  Node* top;

public:
  Stack() {
    top = NULL; // Initially stack is empty
  }

  // Push operation
  void push(int val) {
    Node* newNode = new Node(val);
    newNode->next = top;
    top = newNode;
    cout << val << " pushed to stack." << endl;
  }

  // Pop operation
  void pop() {
    if (top == NULL) {
      cout << "Stack Underflow!" << endl;
      return;
    }
    Node* temp = top;
    cout << top->data << " popped from stack." << endl;
    top = top->next;
    delete temp;
  }

  // Peek (top element)
  int peek() {
    if (top == NULL) {
      cout << "Stack is empty." << endl;
      return -1;
    }
    return top->data;
  }

  // Check if stack is empty
  bool isEmpty() {
    return top == NULL;
  }

  // Display stack elements
  void display() {
    if (isEmpty()) {
      cout << "Stack is empty." << endl;
      return;
    }

    Node* temp = top;
    cout << "Stack elements: ";
    while (temp != NULL) {
      cout << temp->data << " ";
      temp = temp->next;
    }
    cout << endl;
  }
};

int main() {
  Stack s;

  s.push(10);
  s.push(20);
  s.push(30);

  s.display();

  cout << "Top element is: " << s.peek() << endl;

  s.pop();
  s.display();

  return 0;
}

Explanation:

1. Yahan humne ek Node class banayi hai jisme data aur next pointer hai.

• data ek integer variable hai jo node ke andar ki actual value ko store karta hai. Jaise ki agar humne push(10) kiya, to 10 value data me store hogi.
• next ek pointer hai jo next node ko point karta hai. Isse linked list ka structure banta hai. Har node next node se connected hoti hai.
• Yeh dono milke ek complete single linked node banate hai jo stack ke element ko represent karti hai.

2. Stack class me humne top pointer rakha hai jo latest added node ko point karta hai.

• top ek pointer hai jo stack ke sabse upar wale (recent) node ko point karta hai.
• Jab bhi koi new element push kiya jaata hai, to top pointer uss naye node par shift ho jaata hai.
• Aur jab pop kiya jaata hai to top pointer next wale node pe chala jaata hai, aur purane node ko delete kar diya jaata hai.
• Yeh pointer stack ke structure ko maintain karne ke liye bahut zaroori hota hai.

3. push() me naya node banake top ke upar append kar diya.

• Jab user push(20) jaise value add karta hai, tab ek naya node create hota hai jisme data = 20 hota hai.
• Naye node ka next pointer purane top ko point karta hai — isse yeh naye node ke neeche purana stack attach ho jaata hai.
• Fir top pointer ko naye node par shift kar diya jaata hai, jo stack ke upar aa jaata hai.
• Iss process me time complexity hoti hai O(1) — kyunki ye sirf pointer update kar raha hota hai.

4. pop() me top node ko delete kar diya jaata hai aur pointer next pe shift hota hai.

• Jab user pop() call karta hai, to sabse pehle hum check karte hain ki stack empty to nahi hai.
• Agar empty nahi hai, to top node ko ek temp pointer me store karte hain.
• Fir top pointer ko top->next par move kar dete hain, jisse next node top ban jaata hai.
• Ab temp wale node ko delete kar diya jaata hai jisse memory leak na ho.
• Ye operation bhi O(1) time me complete hota hai.

5. peek() sirf top ka data return karta hai.

• peek() function sirf stack ke top element ko dekhta hai, bina usse remove kiye.
• Agar stack empty ho to warning print karta hai, warna top->data ko return kar deta hai.
• Isse user check kar sakta hai ki current stack ke top pe kaunsa value rakha hai.
• Ye operation bhi constant time O(1) me hota hai.

6. display() saare elements top se bottom tak print karta hai.

• Is function me hum ek temporary pointer temp = top banate hain.
• Jab tak temp != NULL, tab tak hum temp->data print karte hain aur temp = temp->next karte jaate hain.
• Yeh pura stack print karta hai, lekin Last In First Out (LIFO) order ke according — pehle top, fir uske neeche waale.
• Iski time complexity hoti hai O(n) kyunki ye har node ko traverse karta hai.