minStack实现

设计包含 min 函数的栈(栈)
定义栈的数据结构,要求添加一个 min 函数,能够得到栈的最小元素。
要求函数 min、push 以及 pop 的时间复杂度都是 O(1)。
 1 #include <algorithm>
 2 #include <iostream>
 3 #include <exception>
 4 #include <string>
 5 
 6 class illegalParameterValue
 7 {
 8     public:
 9         illegalParameterValue():errorMessage("Illegal parameter value"){}
10         illegalParameterValue(const char* theMessage){ errorMessage = theMessage;}
11         std::string errorMessage;
12 };
13 
14 template<typename T>
15 struct minStackElement{
16     T element;
17     T min;
18 };
19 
20 template<typename T>
21 class minStack{
22 private:
23     int top;
24     int size;
25     minStackElement<T>* arrayStack;
26 public:
27     minStack(int initCapacity)
28     {
29         try{
30             if(initCapacity < 1)
31                 throw illegalParameterValue("initCapacity must greater than 0");
32         }catch(illegalParameterValue& e){
33             std::cout << "initCapacity has been made to be 1" << std::endl;
34             initCapacity = 1;
35         }
36         arrayStack = new minStackElement<T>[initCapacity];
37         size = initCapacity;
38         top = -1;
39     }
40     ~minStack()
41     {
42         delete [] arrayStack;
43     }
44     void push(T x)
45     {
46         minStackElement<T> e;
47         e.element = x;
48         if(top == -1){
49             e.min = x;
50         }else if(x < arrayStack[top].min){
51             e.min = x;
52         }else{
53             e.min = arrayStack[top].min;
54         }
55         if(top == size-1)
56         {
57             minStackElement<T>* temp = arrayStack;
58             arrayStack = new minStackElement<T>[2*size];
59             std::copy(temp,temp+size-1,arrayStack);
60             delete [] temp;
61         }
62         arrayStack[++top] = e;
63     }
64 
65     void pop()
66     {
67         if(top == -1)
68             throw illegalParameterValue("the stack is empty");
69         top--;
70     }
71 
72     T min()
73     {
74         return arrayStack[top].min;
75     }
76 };