创建一个带获取最小元素的功能的栈，要求push，pop，getMin的时间复杂度均为O(1)。StackWithMin.h/* * StackWithMin.h * * Created on: 2012-10-8 * Author: dapengking */#ifndef STACKWITHMIN_H_#define STACKWITHMIN_H_#includeusing namespace std;template class node{public: T item; node *min; node *next; node(T x,node *p){ item = x; min = 0; next = p; } void setMin(node *pMin){ min = pMin; }};template class StackWithMin{private: node *head;public: StackWithMin(); ~StackWithMin(); int isEmpty(); void push(T x); T pop(); T getMin();};template StackWithMin ::StackWithMin(){ head = new node ((T)0,0); head->min = 0;}template StackWithMin ::~StackWithMin(){ delete(head); head = 0;}template int StackWithMin ::isEmpty(){ return head->next == 0;}template void StackWithMin ::push(T x){ node *pNewNode = new node (x,head->next); if(head->next != 0){ if(x <= head->next->min->item){ pNewNode->min = pNewNode; }else{ pNewNode->min = head->next->min; } }else{ pNewNode->min = pNewNode; } head->next = pNewNode;}template T StackWithMin ::pop(){ T v = head->next->item; node *p = head->next; head->next = p->next; delete(p); return v;}template T StackWithMin ::getMin(){ T min; if(head->next != 0){ min = head->next->min->item; } return min;}#endif /* STACKWITHMIN_H_ */
100-2.cpp//============================================================================// Name : 100-2.cpp// Author : dapengking// Version :// Copyright : Your copyright notice// Description : Hello World in C++, Ansi-style//============================================================================#include#include "StackWithMin.h"using namespace std;int main() { StackWithMin s; s.push(100); s.push(15); s.push(2); s.push(30); while(!s.isEmpty()){ cout << "min:" << s.getMin() << endl; cout << s.pop() << " "; } cout << endl; return 0;}