getMin機能のあるスタックを設計する(C++)

getMin機能のあるスタックを設計する
【テーマ】
特殊なスタックを実現し、スタックの基本機能を実現した上で、スタック種の最小要素を返す操作を実現する.
【要望】

pop,push,getMin操作の時間的複雑度はいずれもO(1)である.

によって設計されたスタックタイプは、既存のスタック構造を使用することができる.

【C++実装】
方法1
2つのスタックを使用して、1つの正常な保存データ:stack_Data、現在の状況の最小値を保存するためのもう1つ:stack_Min.
スタックの状況:

Minスタックが空いているときに直接押し込みます.

Minが空でない場合、Minスタックトップ要素はDataスタックの中で最小に保たれるため、スタックを圧縮する際に比較する必要があります.スタック要素がMinスタックトップ要素以下である場合、スタック要素はスタック後に現在の最小値となるため、Minスタックに一緒に押し込む必要があることを示します.

Dataスタックは、いつでもスタックを圧縮する必要があります.

スタックの状況:

Dataスタックが空でない場合、直接スタックを弾きます.

Dataスタックからポップアップされた要素がMinスタックトップ要素に等しい場合、Minスタックは一緒にポップアップする必要があります.

コード実装:
ヘッダ関数h:

 1#pragma once
 2#include 
 3using namespace std;
 4class MyStack {
 5public:
 6    //      
 7    stack stack_Data;
 8    //         
 9    stack stack_Min;
10
11    //  
12    void pop() {
13        if (!stack_Data.empty()) {
14            int num = stack_Data.top();
15            stack_Data.pop();
16            if (num == getMin()) {
17                stack_Min.pop();
18            }
19        }
20        else
21            throw new exception("【  】：    ！");
22
23    }
24    //  
25    void push(int number) {
26        if (stack_Min.empty())
27            stack_Min.push(number);
28        else if (number <= getMin()) {
29            stack_Min.push(number);
30        }
31        stack_Data.push(number);
32    }
33    //     
34    int getMin() {
35        if (stack_Min.empty())
36            throw new exception("【  】：    ！");
37        return stack_Min.top();
38    }
39};

メイン関数main.cpp:

 1//      getMin    .cpp :       "main"   。             。
 2//
 3
 4#include 
 5#include "MyStack.h"
 6using namespace std;
 7
 8int main(){
 9    cout <> num;
19        int min;
20        switch (num)
21        {
22        case 1:
23            cout <> number;
26            mystack.push(number);
27            cout <

方法2
1つと同様に、異なる点は、スタック要素がMinスタックトップ要素より大きい場合、方法1はスタック操作を行わず、方法2はスタック操作を行い、スタックの要素は現在の最小値(すなわちMinスタックトップ要素)である.
スタック操作の場合、メソッド1は、現在のスタック要素が現在の最小値であるかどうかを判断する必要があり、メソッド2は直接ポップアップされ、判断する必要はありません.
しかし,方法1と方法2にかかわらず,時間的複雑度はO(1),空間的複雑度はO(n)であった.