Stack

In a stack, elements are added and removed from the top of the stack, which is the most recent element added. This means that the last element added is the first one to be removed, which is known as the Last-In-First-Out (LIFO) principle.

Some important characteristics of a stack are:

It is a dynamic data structure, meaning that its size can change during program execution.

It has a fixed memory allocation, which means that its size is limited.

It supports only two operations: push (to add an element to the top of the stack) and pop (to remove the top element from the stack).

It can be implemented using arrays or linked lists.

The main operations on a stack are:

push(element): Add an element to the top of the stack.

pop(): Remove and return the element at the top of the stack.

top(): Return the element at the top of the stack without removing it.

empty(): Check if the stack is empty.

A stack data structure has many real-life applications. Here are a few examples:

Web Browsers: Web browsers use a stack data structure to implement the back and forward button functionality. When you visit a website, it gets pushed onto a stack. When you click the back button, the last website you visited is popped off the stack and displayed.

Undo/Redo Operations: Many software applications use a stack to implement undo/redo functionality. When you perform an action, it gets pushed onto a stack. When you want to undo the action, it gets popped off the stack and the previous action is executed.

Call Stack: In computer programming, a call stack is used to keep track of function calls. When a function is called, its parameters and local variables are pushed onto the stack. When the function returns, its parameters and local variables are popped off the stack.


#include <iostream>
using namespace std;

#define MAX_SIZE 100

class Stack {
private:
    int top;
    int arr[MAX_SIZE];
public:
    Stack() {
        top = -1;
    }

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

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

    void push(int x) {
        if (isFull()) {
            cout << "Stack overflow!" << endl;
            return;
        }
        arr[++top] = x;
    }

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

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

int main() {
    Stack s;
    s.push(10);
    s.push(20);
    s.push(30);
    cout << s.pop() << endl; // 30
    cout << s.peek() << endl; // 20
    cout << s.pop() << endl; // 20
    cout << s.pop() << endl; // 10
    cout << s.pop() << endl; // Stack underflow!
    return 0;
}

This implementation uses an array of size MAX_SIZE to store the elements of the stack, and the variable top to keep track of the index of the top element.

The functions isEmpty() and isFull() check if the stack is empty or full, respectively.

The push() function adds an element to the top of the stack, and the pop() function removes and returns the top element.

The peek() function returns the value of the top element without removing it from the stack. Finally, the main() function demonstrates the usage of the stack.

PRACTICE PROBLEMS :

Check for balanced parentheses

Next greater element