C ++でO（1）時間とO（1）余分なスペースでスタックの最大値を見つけます

スタックに最大の要素を格納できるスタックを作成するとします。そして、O（1）時間でそれを得ることができます。制約は、O（1）の余分なスペースを使用する必要があるということです。

最大値を格納するユーザー定義スタックを1つ作成できます。ポップやピークなど、1つの操作が実行されると、最大値が返されます。ピーク操作の場合は、スタックトップの最大値と最大要素を返します。ポップ操作の場合は、トップ要素が大きい場合はそれを出力し、maxを2 * max –top_elementとして更新します。それ以外の場合はtop_elementを返します。プッシュ操作の場合、最大要素をx（挿入するデータ）、2 * x –maxとして更新します。

例

#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();
}

出力

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