一、题目:包含Min函数的栈
题目:定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中,调用min、push及pop的时间复杂度都是O(1)。
这里我们要实现的就是min、push以及pop三个方法:
public class MinInStack<T> where T : struct
{
private Stack<T> dataStack;
private Stack<T> minStack; public MinInStack()
{
this.dataStack = new Stack<T>();
this.minStack = new Stack<T>();
} public bool IsEmpty()
{
return this.dataStack.Count == ;
} public T Top()
{
return this.dataStack.Peek();
} public void Push(T item)
{
} public T Pop()
{
} public T Min()
{
}
}
二、解题思路
2.1 核心步骤
把每次的最小元素(之前的最小元素和新压入栈的元素两者的较小值)都保存起来放到另外一个辅助栈里。下图展示了栈内压入3、4、2、1之后接连两次弹出栈顶数字再压入0时,数据栈、辅助栈和最小值的状态。
从表中我们可以看出,如果每次都把最小元素压入辅助栈,那么就能保证辅助栈的栈顶一直都是最小元素。
2.2 代码实现
(1)Push方法
public void Push(T item)
{
// 把新元素添加到数据栈
dataStack.Push(item);
// 当新元素比之前的最小元素小时,把新元素插入辅助栈里;
// 否则把之前的最小元素重复插入辅助栈里
if (minStack.Count == || item.CompareTo(minStack.Peek()) < )
{
minStack.Push(item);
}
else
{
minStack.Push(minStack.Peek());
}
}
(2)Pop方法
public T Pop()
{
T item = dataStack.Pop();
if(minStack.Count > )
{
minStack.Pop();
} return item;
}
(3)Min方法
public T Min()
{
return minStack.Peek();
}
三、单元测试
3.1 测试用例
[TestMethod]
public void MinTest1()
{
MinInStack<int> stack = new MinInStack<int>();
stack.Push();
Assert.AreEqual(stack.Min(),);
} [TestMethod]
public void MinTest2()
{
MinInStack<int> stack = new MinInStack<int>();
stack.Push();
stack.Push();
Assert.AreEqual(stack.Min(), );
} [TestMethod]
public void MinTest3()
{
MinInStack<int> stack = new MinInStack<int>();
stack.Push();
stack.Push();
stack.Push();
Assert.AreEqual(stack.Min(), );
} [TestMethod]
public void MinTest4()
{
MinInStack<int> stack = new MinInStack<int>();
stack.Push();
stack.Push();
stack.Push();
stack.Push();
Assert.AreEqual(stack.Min(), );
} [TestMethod]
public void MinTest5()
{
MinInStack<int> stack = new MinInStack<int>();
stack.Push();
stack.Push();
stack.Push();
stack.Push();
stack.Pop();
Assert.AreEqual(stack.Min(), );
} [TestMethod]
public void MinTest6()
{
MinInStack<int> stack = new MinInStack<int>();
stack.Push();
stack.Push();
stack.Push();
stack.Push();
stack.Pop();
stack.Pop();
Assert.AreEqual(stack.Min(), );
} [TestMethod]
public void MinTest7()
{
MinInStack<int> stack = new MinInStack<int>();
stack.Push();
stack.Push();
stack.Push();
stack.Push();
stack.Pop();
stack.Pop();
stack.Pop();
Assert.AreEqual(stack.Min(), );
} [TestMethod]
public void MinTest8()
{
MinInStack<int> stack = new MinInStack<int>();
stack.Push();
stack.Push();
stack.Push();
stack.Push();
stack.Pop();
stack.Pop();
stack.Pop();
stack.Push();
Assert.AreEqual(stack.Min(), );
}
3.2 测试结果
(1)测试通过情况
(2)代码覆盖率