本文共 3936 字,大约阅读时间需要 13 分钟。
该题目来自《程序员代码面试指南》,在理解其实现原理的基础上,将Java实现改用C++实现。
题目
实现一个特殊的栈,在实现栈的基本功能的基础上,再实现返回栈中最小元素的操作。
要求
public class MinStack1{ private StackstackData; private Stack stackMin; public MinStack1(){ stackData = new Stack (); stackMin = new Stack (); } public void push(int newNum){ if (stackMin.isEmpty()) { stackMin.push(newNum); }else if (newNum <= getMin()) { stackMin.push(newNum); } stackData.push(newNum); } public int pop(){ if (stackData.isEmpty()) { throw new RuntimeException("Your stack is empty!"); } int value = stackData.pop(); if (value == getMin()) { stackMin.pop(); } return value; } public int getMin() { if (stackMin.isEmpty()) { throw new RuntimeException("Your stack is empty!"); } return stackMin.peek(); } }
class MyStack1 //C++实现{private: stack stackData; stack stackMin;public: MyStack1(){} void push1(int numNum); int pop1(); int getmin();};void MyStack1::push1(int newNum){ if(stackMin.empty()) stackMin.push(newNum); else if(newNum <= getmin()) stackMin.push(newNum); stackData.push(newNum);}int MyStack1::pop1(){ if(stackData.empty()) { cout<<"your stack is empty."; return -1; } int value = stackData.top(); //由于c++中pop函数的返回类型为void,因此不能采用Java中的描述实现。 stackData.pop(); if(value == getmin()) stackMin.pop(); return value;}int MyStack1::getmin(){ if(stackMin.empty()) { cout<<"your stack is empty"; return -1; } return stackMin.top();}
class MinStack { //LeetCode下该问题的优质回答。结合上面正确的逻辑,这个代码实现地非常简洁清晰。private: stack s1; stack s2;public: void push(int x) { s1.push(x); if (s2.empty() || x <= getMin()) s2.push(x); } void pop() { if (s1.top() == getMin()) s2.pop(); s1.pop(); } int top() { return s1.top(); } int getMin() { return s2.top(); }};
public class MinStack2 { private StackstackData; private Stack stackMin; public MinStack(){ stackData = new Stack (); stackMin = new Stack (); } public void push(int newNum){ if (stackMin.isEmpty()) { stackMin.push(newNum); } else if (newNum <= getMin()) { stackMin.push(newNum); }else { stackMin.push(getMin()); } stackData.push(newNum); } public int pop(){ if (stackData.isEmpty()) { throw new RuntimeException("Your stack is empty!"); } int value = stackData.pop(); stackMin.pop(); return value; } public int getMin(){ if (stackMin.isEmpty()) { throw new RuntimeException("Your stack is empty!"); } return stackMin.peek(); }}