Topic 4

Stack

LIFO — Last In, First Out

A stack is like a pile of plates. You can only add/remove from the top.

4 Operations:
• push(value) — add to top
• pop() — remove top
• peek() — view top without removing
• display() — print all (top to bottom)

Push order: 10, 20, 30

30← top

After pop() → returns 30

20← top

📝

Array: top = -1. Push: arr[++top]. Pop: arr[top--]

📝

LL: Push = insert at head. Pop = delete head. No overflow!

📝

isFull(): top == maxSize - 1 (array only!). LL has no isFull.

📝

Display: Array prints top → 0. LL traverses current → NULL.

Array Stack vs Linked List Stack

Aspect	Array	Linked List
Size	Fixed (needs maxSize)	Dynamic (grows as needed)
Overflow	top == maxSize-1	No overflow possible
Top variable	int top = -1	Node* top = NULL
Push	arr[++top] = value	newNode->next = top
Pop	return arr[top--]	Save data, move top, delete
Memory	Contiguous block	Scattered nodes
Destructor	delete[] arr	Loop pop() until empty

#include <iostream>
using namespace std;

class Stack {
private:
    int* arr;
    int top;
    int maxSize;

public:
    // Constructor
    Stack(int size) {
        maxSize = size;
        arr = new int[maxSize];
        top = -1;
    }

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

    bool isFull() {
        return top == maxSize - 1;
    }

    // Push element
    void push(int value) {
        if (isFull()) {
            cout << "Stack Overflow!" << endl;
            return;
        }
        arr[++top] = value;
        cout << value << " pushed onto stack." << endl;
    }

    // Pop element
    int pop() {
        if (isEmpty()) {
            cout << "Stack Underflow!" << endl;
            return -1;
        }
        return arr[top--];
    }

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

    // Display stack
    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;
    }

    // Destructor
    ~Stack() {
        delete[] arr;
    }
};

int main() {
    Stack s(5);
    s.push(10);
    s.push(20);
    s.push(30);
    s.display();        // 30 20 10

    cout << "Top Element: " << s.peek() << endl;
    cout << "Popped: " << s.pop() << endl;
    s.display();        // 20 10

    return 0;
}

#include <iostream>
using namespace std;

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

class Stack {
private:
    Node* top;

public:
    Stack() {
        top = NULL;
    }

    bool isEmpty() {
        return top == NULL;
    }

    // Push: insert at top
    void push(int value) {
        Node* newNode = new Node();
        newNode->data = value;
        newNode->next = top;
        top = newNode;
        cout << value << " pushed onto stack." << endl;
    }

    // Pop: remove from top
    int pop() {
        if (isEmpty()) {
            cout << "Stack Underflow!" << endl;
            return -1;
        }
        Node* temp = top;
        int poppedValue = temp->data;
        top = top->next;
        delete temp;
        return poppedValue;
    }

    // Peek: view top
    int peek() {
        if (isEmpty()) {
            cout << "Stack is empty!" << endl;
            return -1;
        }
        return top->data;
    }

    // Display
    void display() {
        if (isEmpty()) {
            cout << "Stack is empty!" << endl;
            return;
        }
        cout << "Stack elements: ";
        Node* current = top;
        while (current != NULL) {
            cout << current->data << " ";
            current = current->next;
        }
        cout << endl;
    }

    // Destructor
    ~Stack() {
        while (!isEmpty()) {
            pop();
        }
    }
};

int main() {
    Stack s;
    s.push(10);
    s.push(20);
    s.push(30);
    s.display();

    cout << "Top Element: " << s.peek() << endl;
    cout << "Popped: " << s.pop() << endl;
    s.display();

    return 0;
}

#include <iostream>
#include <stack>
using namespace std;

int precedence(char op) {
    if (op == '^') return 3;
    if (op == '*' || op == '/') return 2;
    if (op == '+' || op == '-') return 1;
    return 0;
}

bool isOperator(char ch) {
    return (ch == '+' || ch == '-' ||
            ch == '*' || ch == '/' || ch == '^');
}

string infixToPostfix(string infix) {
    stack<char> s;
    string postfix = "";

    for (char ch : infix) {
        if (isalnum(ch)) {
            postfix += ch;           // Operand -> output
        }
        else if (ch == '(') {
            s.push(ch);              // '(' -> push
        }
        else if (ch == ')') {
            while (!s.empty() && s.top() != '(') {
                postfix += s.top();
                s.pop();
            }
            s.pop();                 // Pop '('
        }
        else if (isOperator(ch)) {
            while (!s.empty() &&
                   precedence(s.top()) >= precedence(ch)) {
                postfix += s.top();
                s.pop();
            }
            s.push(ch);
        }
    }

    while (!s.empty()) {
        postfix += s.top();
        s.pop();
    }

    return postfix;
}

int main() {
    string infix = "A+B*(C^D-E)";
    cout << "Infix:   " << infix << endl;
    cout << "Postfix: " << infixToPostfix(infix) << endl;
    // Output: ABCD^E-*+
    return 0;
}