Stack

Stack

A stack is a linear data structure that follows the Last In First Out (LIFO) principle. The last element that is added to the stack is the first one to be removed. The insertion and deletion operations are performed at the same end, known as the top of the stack.

Operations

The following operations can be performed on a stack:

1. Push: Adds an element to the top of the stack.
2. Pop: Removes the top element from the stack.
3. Peek: Returns the top element of the stack without removing it.
4. isEmpty: Checks if the stack is empty.
5. isFull: Checks if the stack is full.
6. Size: Returns the number of elements in the stack.

Implementation

#include <iostream>
using namespace std;

#define MAX 1000

class Stack {
    int top;

public:

    int a[MAX];

    Stack() { top = -1; }

    bool push(int x) {
        if (top >= (MAX - 1)) {
            cout << "Stack Overflow";
            return false;
        }
        else {
            a[++top] = x;
            cout << x << " pushed into stack\n";
            return true;
        }
    }

    int pop() {
        if (top < 0) {
            cout << "Stack Underflow";
            return 0;
        }
        else {
            int x = a[top--];
            return x;
        }
    }

    int peek() {
        if (top < 0) {
            cout << "Stack is Empty";
            return 0;
        }
        else {
            int x = a[top];
            return x;
        }
    }

    bool isEmpty() {
        return (top < 0);
    }

    int size() {
        return top + 1;
    }
};

int main() {
    Stack s;
    s.push(10);
    s.push(20);
    s.push(30);
    cout << s.pop() << " popped from stack\n";
    cout << "Top element is " << s.peek() << endl;
    cout << "Stack size is " << s.size() << endl;
    return 0;
}

Complexity

The time complexity of the push, pop, peek, isEmpty, and size operations is O(1).

STL Implementation

The C++ Standard Template Library (STL) provides a stack container that can be used to implement a stack. The stack container is defined in the <stack> header file.

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

int main() {
    stack<int> s;
    s.push(10);
    s.push(20);
    s.push(30);
    cout << s.top() << " is at the top of the stack\n";
    s.pop();
    cout << s.top() << " is at the top of the stack\n";
    cout << "Stack size is " << s.size() << endl;
    return 0;
}

Applications

1. Balanced Parentheses: Checking for balanced parentheses in an expression.
2. Function Call Stack: Used to store function call information in programming languages.
3. Expression Evaluation: Evaluating postfix expressions.
4. Backtracking: Used in backtracking algorithms to store the state of the search.