MS - 2 - 设计包含 min 函数的栈

定义栈的数据结构，要求添加一个 min 函数，能够得到栈的最小元素。要求函数 min、push 以及 pop 的时间复杂度都是 O(1)。

 template<typename T>

 struct MinStackElement

 {

     T data;

     T min;

 };

 template<typename T>

 struct MinStack

 {

     MinStack() : pData(NULL), size(), top(){}

     MinStackElement<T>* pData;

     int size;

     int top;

 };

 template<typename T>

 void MinStackInitialize(MinStack<T>& s, int maxSize)

 {

     MinStackFree(s);

      s.pData = (MinStackElement<T>*)malloc(maxSize*sizeof(MinStackElement<T>));

      memset(s.pData, , maxSize*sizeof(MinStackElement<T>));

      s.size = maxSize;

      s.top = ;

  }

  template<typename T>

  void MinStackFree(MinStack<T>& s)

  {

      if (s.pData)

      {

          free(s.pData);

          s.pData = nullptr;

      }

      s.size = ;

      s.top = ;

  }

  template<typename T>

  void MinStackPush(MinStack<T>& s, T data)

  {

      if (s.size == )

      {

          printf("Stack is not initialized.\n");

          return;

      }

      if (s.top == s.size)

      {

          printf("Stack is full.\n");

          return;

      }

      s.pData[s.top].data = data;

      s.pData[s.top].min = (s.top ==  ? data : s.pData[s.top - ].min);

      if (s.pData[s.top].min > data)

      {

          s.pData[s.top].min = data;

      }

      wcout << L"stack push " << data << endl;

      s.top++;

  }

  template<typename T>

  T MinStackPop(MinStack<T>& s)

  {

     if (s.top == )

     {

         printf("Stack is empty.\n");

         return -;

     }

     T data = s.pData[--s.top].data;

     wcout << L"stack pop " << data << endl;

     return data;

  }

 template<typename T>

 T MinStackGetMin(const MinStack<T>& s)

 {

     if (s.top == )

     {

         printf("Stack is empty.\n");

         return ;

     }

     T min = s.pData[s.top - ].min;

     printf("Min :%d\n", min);

     return min;

 }

 int _tmain(int argc, _TCHAR* argv[])

 {

     int min = ;

     MinStack<int> s;

     MinStackPush(s, );

     MinStackInitialize(s, );

     MinStackPush(s, );

     MinStackPush(s, );

     MinStackPush(s, );

     MinStackPush(s, );

     MinStackPop(s);

     MinStackGetMin(s);

     MinStackPush(s, );

     MinStackPush(s, );

     MinStackPush(s, );

     MinStackPop(s);

     MinStackPush(s, );

     MinStackPush(s, );

     MinStackGetMin(s);

     MinStackPop(s);

     MinStackGetMin(s);

     MinStackPop(s);

     MinStackGetMin(s);

     MinStackPop(s);

     MinStackGetMin(s);

     MinStackPop(s);

     MinStackGetMin(s);

     MinStackPop(s);

     MinStackGetMin(s);

     MinStackPop(s);

     MinStackPop(s);

     MinStackPop(s);

     MinStackGetMin(s);

     MinStackFree(s);

     return ;

 }

>test.exe
Stack is not initialized.
stack push 9
stack push 5
stack push 6
stack push 4
stack pop 4
Min :5
stack push 3
stack push 8
stack push 2
stack pop 2
stack push 7
stack push 1
Min :1
stack pop 1
Min :3
stack pop 7
Min :3
stack pop 8
Min :3
stack pop 3
Min :5
stack pop 6
Min :5
stack pop 5
stack pop 9
Stack is empty.
Stack is empty.

巴特西

MS - 2 - 设计包含 min 函数的栈

最新文章

热门文章