面试题-Stack的最小值o(1)

冷不防 2022-01-07 14:59 162阅读 0赞

1 // Stack.cpp : 定义控制台应用程序的入口点。
     2 //
     3 
     4 #include "stdafx.h"
     5 #include <iostream>
     6 using namespace std;
     7 
     8 template <class Type>
     9 struct Stack
    10 {
    11 private:
    12 Type *_stack;
    13 int _top;
    14 int _min;
    15 int _size;
    16 
    17 
    18 public:
    19 Stack(const Type &size):_size(size),_top(0),_min(0)
    20 {    
    21 _stack = new Type[size];//(Type*)malloc(sizeof())
    22 }
    23 void push(const Type &value)
    24 {
    25 
    26 if(_top == 0)
    27 {
    28 _min = value;
    29 }
    30 else if(_top == _size)
    31 {
    32 cout<<"Push failed,the stack is full"<<endl;
    33 return;
    34 }
    35 _stack[_top++] = value-_min;
    36 if(value < _min)
    37 {    
    38 _min = value;
    39 }
    40 
    41 }
    42 Type pop()
    43 {
    44 if(_top == 0)
    45 {
    46 cout<<"Pop failed,the stack is emply."<<endl;
    47 return -1;
    48 }
    49 Type popvalue;
    50 if(_stack[--_top]<0)
    51 {
    52 popvalue = _min;
    53 _min = _min-_stack[_top];
    54 }
    55 else
    56 {
    57 popvalue = _min + _stack[_top];
    58 }
    59 return popvalue;
    60 }
    61 Type min()
    62 {
    63 return _min;
    64 }
    65 
    66 };
    67 
    68 int _tmain(int argc, _TCHAR* argv[])
    69 {
    70 Stack<int> sk(30);
    71 sk.push(8);
    72 sk.push(7);
    73 sk.push(6);
    74 sk.push(5);
    75 sk.push(9);
    76 sk.push(4);
    77 sk.push(3);
    78 
    79 cout<<sk.min()<<endl;//3
    80 cout<<sk.pop()<<endl;//3
    81 cout<<sk.min()<<endl;//4
    82 cout<<sk.pop()<<endl;//4
    83 cout<<sk.min()<<endl;//5
    84 cout<<sk.pop()<<endl;//9
    85 cout<<sk.min()<<endl;//5
    86 cout<<sk.pop()<<endl;//5
    87 cout<<sk.min()<<endl;//6
    88 cout<<sk.pop()<<endl;//6
    89 cout<<sk.min()<<endl;//7
    90 cout<<sk.pop()<<endl;//7
    91 cout<<sk.min()<<endl;//8
    92 cout<<sk.pop()<<endl;//8
    93 
    94 return 0;
    95 }
    96 
    97

转载于:https://www.cnblogs.com/harlanc/p/5172958.html