設(shè)計包含min函數(shù)的棧。
定義棧的數(shù)據(jù)結(jié)構(gòu)，要求添加一個min函數(shù)，能夠得到棧的最小元素。
要求函數(shù)min、push以及pop的時間復(fù)雜度都是O(1)。

理解：

1.建立兩個順序棧A,B。

A：依次push輸入的節(jié)點(diǎn)；

B：每次向push節(jié)點(diǎn)的同時，向B中pushA中的最小值。

比如：

A ? ? B

2 ? ? 2

4 ? ? 2

6 ? ? 2

1 ? ? 1 ??

3 ? ? 1

5 ? ? 1

/** micro3.h** Created on: 2011-3-13* Author: zq*/#ifndef MICRO3_H_ #define MICRO3_H_ class SqStack{ public:int *base;int *top;//int length;int stacksize;SqStack(int *b=0,int *t=0,int l=0,int size=50):base(b),top(t),stacksize(size){base = new int[stacksize];top = base;}~SqStack(){delete []base;}int Push(int data);int Pop(); };#endif /* MICRO3_H_ */ /** micro3.cpp** Created on: 2011-3-13* Author: zq*/ #include <iostream> #include "micro3.h" using namespace std;int SqStack::Push(const int newdata){//if(top-base >= stacksize)*++top = newdata;//++length;return 0; }int SqStack::Pop(){if (top == base) return NULL;int data = *top--;//--length;return data; }int main(){SqStack S,minS;int data;cout << "輸入數(shù)據(jù)： " <<endl;cin >> data;while(data != 9999){S.Push(data);if (minS.top == NULL ||*minS.top > data)minS.Push(data);else minS.Push(*minS.top);cin >> data;}//cout << "S.length: " <<S.length << endl;int length = S.top-S.base;cout << "S.length: " <<length << endl;for (int i = 1;i <= length;i++){cout << "顯示第"<< i <<"次出棧數(shù)據(jù)"<< S.Pop() << endl;cout << "顯示第"<< i <<"次出棧前棧中最小值： " << minS.Pop() << endl;}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/phoenixzq/archive/2011/03/17/1986930.html

總結(jié)

以上是生活随笔為你收集整理的微软算法面试题（2）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。