#include <iostream>#include <stdio.h>#include <vector>#include <string>#include <stack>using namespace std;/*問題:Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.push(x) -- Push element x onto stack.pop() -- Removes the element on top of the stack.top() -- Get the top element.getMin() -- Retrieve the minimum element in the stack.Example:MinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.getMin();   --> Returns -3.minStack.pop();minStack.top();      --> Returns 0.minStack.getMin();   --> Returns -2.分析:最小棧。設計一個棧，支持在常量時間內返回最小元素。這是程序員面試金典的題目。記得好像使用一個棧，每次遇到將當前元素與棧頂元素中的最小值插入其中。-2 0 -3 -3 2 2 4 3最小棧為空：插入-2,0與-2比較，-2較小，繼續插入-2，-2與-3比較，-3較小，插入-3對2 2 4 3最小值一直為-3，不插入得到minStack值為:-2 -3要獲取最小元素的時候，發現當前棧頂元素為3，彈出最小棧的棧頂-3.并將-3彈出。如果正常棧的棧頂元素 != 最小棧的棧頂元素，獲取最小棧的棧頂元素；否則，輸出最小棧的棧頂元素，并彈出最小棧的棧頂元素。最小棧維護了當前標準棧的最小值輸入:5(輸入的元素個數) 13(指令個數)-2 0 -3 -3 2 push 3getMin popgetMinpopgetMinpopgetMinpopgetMinpopgetMinpop輸出:-3-3-3-3-2-2關鍵：1 設定標準棧用于完全模擬正常情況，設定最小棧，當待插入元素 <= 最小棧的棧頂元素，則在最小棧中插入該元素；pop時，如果標準棧的棧頂元素=最小棧的棧頂元素，則一起pop，否則，只pop標準棧*/class MinStack {public:    /** initialize your data structure here. */    MinStack() {    }        void push(int x) {        _normalStack.push(x);		if(!_minStack.empty())		{			//比較當前元素和最小棧的棧頂元素，如果當前元素=最小棧的棧頂元素，壓入元素			if(x <= _minStack.top())			{				_minStack.push(x);			}		}		else		{			_minStack.push(x);		}    }    	//彈出元素，彈出棧頂元素時，如果棧頂元素=最小棧棧頂元素，則一起彈出，否則繼續處理    void pop() {		if(_normalStack.empty() || _minStack.empty())		{			return;		}		int value = _normalStack.top();		_normalStack.pop();		//兩者相等，彈出最小棧的棧頂元素		if(value == _minStack.top() )		{			_minStack.pop();		}    }    	//返回棧頂元素，返回正常棧的棧頂元素    int top() {		if(!_normalStack.empty())		{			return _normalStack.top();		}		else		{			return 0;		}    }    	//獲取最小元素    int getMin() {		if(!_minStack.empty())		{			return _minStack.top();		}		else		{			return 0;		}    }PRivate:	stack<int> _minStack;	stack<int> _normalStack;//標準棧};void print(vector<int>& result){	if(result.empty())	{		cout << "no result" << endl;		return;	}	int size = result.size();	for(int i = 0 ; i < size ; i++)	{		cout << result.at(i) << " " ;	}	cout << endl;}void process(){	 vector<int> nums;	 int value;	 int num;	 vector<int> result;	 int commandNum;	 string command;	 while(cin >> num >> commandNum )	 {		 MinStack minStack;		 //nums.clear();		 for(int i = 0 ; i < num ; i++)		 {			 cin >> value;			 minStack.push(value);		 }		 for(int i = 0 ; i < commandNum ; i++)		 {			 cin >> command;			 if("push" == command)			 {				 cin >> value;				 minStack.push(value);			 }			 else if("pop" == command)			 {				 minStack.pop();			 }			 else if("getMin" == command)			 {				 cout << minStack.getMin() << endl;			 }		 }	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}