Tìm tối đa trong ngăn xếp trong O (1) mà không cần sử dụng ngăn xếp bổ sung trong C ++

Giả sử chúng ta muốn tạo một ngăn xếp có thể lưu trữ phần tử tối đa trong ngăn xếp. Và chúng ta có thể nhận được nó trong O (1) thời gian. Hạn chế là nó không được sử dụng thêm bất kỳ không gian nào, vì vậy O (1) không gian thừa.

Chúng tôi có thể tạo một ngăn xếp do người dùng xác định, ngăn xếp này sẽ lưu trữ giá trị tối đa, khi một hoạt động được thực hiện, như bật hoặc nhìn, thì giá trị tối đa sẽ được trả về. Đối với hoạt động xem trước, trả về giá trị tối đa của đỉnh ngăn xếp và phần tử tối đa, đối với hoạt động bật, khi phần tử trên cùng lớn hơn, sau đó in nó và cập nhật tối đa dưới dạng 2 * max - top_element. nếu không thì trả về top_element. Đối với hoạt động đẩy, hãy cập nhật phần tử tối đa là x (dữ liệu sẽ được chèn vào), 2 * x - tối đa.

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(); // Top element.
      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();
}

Đầu ra

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