Tìm max trong stack O(1) không dùng stack phụ trong C++

Tương tự bài 1003081472: Triển khai stack lấy max O(1) với O(1) bộ nhớ thêm bằng kỹ thuật lưu giá trị biến đổi (2*x - max).

Ví dụ

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

class CustomStack {
    stack<int> stk;
    int stack_max;
public:
    void getMax() {
        if (stk.empty()) cout << "Stack is empty" << endl;
        else cout << "Maximum Element in the stack is: " << stack_max << endl;
    }
    void peek() {
        if (stk.empty()) { cout << "Stack is empty "; return; }
        int top = stk.top();
        cout << "Top Most Element is: " << endl;
        (top > stack_max) ? cout << stack_max : cout << top;
    }
    void pop() {
        if (stk.empty()) { cout << "Stack is empty" << endl; return; }
        cout << "Top Most Element Removed: ";
        int top = stk.top(); stk.pop();
        if (top > stack_max) {
            cout << stack_max << endl;
            stack_max = 2 * stack_max - top;
        } else cout << top << endl;
    }
    void push(int element) {
        if (stk.empty()) {
            stack_max = element;
            stk.push(element);
            cout << "Element Inserted: " << element << endl;
            return;
        }
        if (element > stack_max) {
            stk.push(2 * element - stack_max);
            stack_max = element;
        } else stk.push(element);
        cout << "Element Inserted: " << element << endl;
    }
};

int main() {
    CustomStack stk;
    stk.push(4);
    stk.push(6);
    stk.getMax();
    stk.push(8);
    stk.push(20);
    stk.getMax();
    stk.pop();
    stk.getMax();
    stk.pop();
    stk.peek();
}

Kết quả

Element Inserted: 4
Element Inserted: 6
Maximum Element in the stack is: 6
Element Inserted: 8
Element Inserted: 20
Maximum Element in the stack is: 20
Top Most Element Removed: 20
Maximum Element in the stack is: 8
Top Most Element Removed: 8
Top Most Element is: 6