第一章：栈和队列（一）

设计一个有getMin功能的栈

【题目】

实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。

【要求】

1．pop、push、getMin操作的时间复杂度都是O(1)。

2．设计的栈类型可以使用现成的栈结构。

【难度】

士     ★☆☆☆

【解答】

在设计时，我们使用两个栈，一个栈用来保存当前栈中的元素，其功能和一个正常的栈没有区别，这个栈记为stackData；另一个栈用于保存每一步的最小值，这个栈记为stackMin。具体的实现方式有两种。

第一种设计方案

（1）压入数据规则

假设当前数据为newNum，先将其压入stackData。然后判断stackMin是否为空：

—     如果为空，则newNum也压入stackMin。

—     如果不为空，则比较newNum和stackMin的栈顶元素中哪一个更小：

Ø 如果newNum更小或两者相等，则newNum也压入stackMin；

举例：依次压入3、4、5、1、2、1的过程中，stackData和stackMin的变化如图1-1所示。

（2）弹出数据规则

先在stackData中弹出栈顶元素，记为value。然后比较当前stackMin的栈顶元素和value哪一个更小。

通过上文提到的压入规则可知，stackMin中存在的元素是从栈底到栈顶逐渐变小的，stackMin栈顶的元素既是stackMin栈的最小值，也是当前stackData栈的最小值。所以不会出现value比stackMin的栈顶元素更小的情况，value只可能大于或等于stackMin的栈顶元素。

当value等于stackMin的栈顶元素时，stackMin弹出栈顶元素；当value大于stackMin的栈顶元素时，stackMin不弹出栈顶元素，返回value。

很明显可以看出，压入与弹出规则是对应的。

（3）查询当前栈中的最小值操作

由上文的压入数据规则和弹出数据规则可知，stackMin始终记录着stackData中的最小值。所以，stackMin的栈顶元素始终是当前stackData中的最小值。

方案一的代码实现如MyStack1类所示：

	public class MyStack1 {
		private Stack<Integer> stackData;
		private Stack<Integer> stackMin;

		public MyStack1() {
			this.stackData = new Stack<Integer>();
			this.stackMin = new Stack<Integer>();
		}

		public void push(int newNum) {
			if (this.stackMin.isEmpty()) {
				this.stackMin.push(newNum);
			} else if (newNum <= this.getmin()) {
				this.stackMin.push(newNum);
			}
			this.stackData.push(newNum);
		}

		public int pop() {
			if (this.stackData.isEmpty()) {
				throw new RuntimeException("Your stack is empty.");
			}
			int value = this.stackData.pop();
			if (value == this.getmin()) {
				this.stackMin.pop();
			}
			return value;
		}

		public int getmin() {
			if (this.stackMin.isEmpty()) {
				throw new RuntimeException("Your stack is empty.");
			}
			return this.stackMin.peek();
		}
	}

第二种设计方案

（1）压入数据规则

假设当前数据为newNum，先将其压入stackData。然后判断stackMin是否为空。

如果为空，则newNum也压入stackMin；    如果不为空，则比较newNum和stackMin的栈顶元素中哪一个更小。

如果newNum更小或两者相等，则newNum也压入stackMin；        如果stackMin中栈顶元素小，则把stackMin的栈顶元素重复压入stackMin，即在栈顶元素上再压入一个栈顶元素。

举例：依次压入3、4、5、1、2、1的过程中，stackData和stackMin的变化如图1-2所示。

（2）弹出数据规则

在stackData中弹出数据，弹出的数据记为value；弹出stackMin中的栈顶，返回value。

很明显可以看出，压入与弹出规则是对应的。

（3）查询当前栈中的最小值操作

由上文的压入数据规则和弹出数据规则可知，stackMin始终记录着stackData中的最小值，所以stackMin的栈顶元素始终是当前stackData中的最小值。

方案二的代码实现如MyStack2类所示：

	public class MyStack2 {
		private Stack<Integer> stackData;
		private Stack<Integer> stackMin;

		public MyStack2() {
			this.stackData = new Stack<Integer>();
			this.stackMin = new Stack<Integer>();
		}

		public void push(int newNum) {
			if (this.stackMin.isEmpty()) {
				this.stackMin.push(newNum);
			} else if (newNum < this.getmin()) {
				this.stackMin.push(newNum);
			} else {
				int newMin = this.stackMin.peek();
				this.stackMin.push(newMin);
			}
			this.stackData.push(newNum);
		}

		public int pop() {
			if (this.stackData.isEmpty()) {
				throw new RuntimeException("Your stack is empty.");
			}
			this.stackMin.pop();
			return this.stackData.pop();
		}

		public int getmin() {
			if (this.stackMin.isEmpty()) {
				throw new RuntimeException("Your stack is empty.");
			}
			return this.stackMin.peek();
		}
	}

【点评】

方案一和方案二其实都是用stackMin栈保存着stackData每一步的最小值。共同点是所有操作的时间复杂度都为O(1)、空间复杂度都为O(n)。区别是：方案一中stackMin压入时稍省空间，但是弹出操作稍费时间；方案二中stackMin压入时稍费空间，但是弹出操作稍省时间。

由两个栈组成的队列

【题目】

编写一个类，用两个栈实现队列，支持队列的基本操作（add、poll、peek）。

【难度】

尉     ★★☆☆

【解答】

栈的特点是先进后出，而队列的特点是先进先出。我们用两个栈正好能把顺序反过来实现类似队列的操作。

具体实现时是一个栈作为压入栈，在压入数据时只往这个栈中压入，记为stackPush；另一个栈只作为弹出栈，在弹出数据时只从这个栈弹出，记为stackPop。

因为数据压入栈的时候，顺序是先进后出的。那么只要把stackPush的数据再压入stackPop中，顺序就变回来了。例如，将1~5依次压入stackPush，那么从stackPush的栈顶到栈底为5~1，此时依次再将5~1倒入stackPop，那么从stackPop的栈顶到栈底就变成了1~5。再从stackPop弹出时，顺序就像队列一样，如图1-3所示。

听起来虽然简单，实际上必须做到以下两点。

1．如果stackPush要往stackPop中压入数据，那么必须一次性把stackPush中的数据全部压入。

2．如果stackPop不为空，stackPush绝对不能向stackPop中压入数据。

违反了以上两点都会发生错误。

违反1的情况举例：1~5依次压入stackPush，stackPush的栈顶到栈底为5~1，从stackPush压入stackPop时，只将5和4压入了stackPop，stackPush还剩下1、2、3没有压入。此时如果用户想进行弹出操作，那么4将最先弹出，与预想的队列顺序就不一致。

违反2的情况举例：1~5依次压入stackPush，stackPush将所有的数据压入stackPop，此时从stackPop的栈顶到栈底就变成了1~5。此时又有6~10依次压入stackPush，stackPop不为空，stackPush不能向其中压入数据。如果违反2压入了stackPop，从stackPop的栈顶到栈底就变成了6~10、1~5。那么此时如果用户想进行弹出操作，6将最先弹出，与预想的队列顺序就不一致。

上面介绍了压入数据的注意事项。那么这个压入数据的操作在何时发生呢？

	public class TwoStacksQueue {
		public Stack<Integer> stackPush;
		public Stack<Integer> stackPop;

		public TwoStacksQueue() {
			stackPush = new Stack<Integer>();
			stackPop = new Stack<Integer>();
		}

		// push栈向pop栈倒入数据
		private void pushToPop() {
			if (stackPop.empty()) {
				while (!stackPush.empty()) {
					stackPop.push(stackPush.pop());
				}
			}
		}

		public void add(int pushInt) {
			stackPush.push(pushInt);
			pushToPop();
		}

		public int poll() {
			if (stackPop.empty() && stackPush.empty()) {
				throw new RuntimeException("Queue is empty!");
			}
			pushToPop();
			return stackPop.pop();
		}

		public int peek() {
			if (stackPop.empty() && stackPush.empty()) {
				throw new RuntimeException("Queue is empty!");
			}
			pushToPop();
			return stackPop.peek();
		}
	}

如何仅用递归函数和栈操作逆序一个栈

【题目】

一个栈依次压入1、2、3、4、5，那么从栈顶到栈底分别为5、4、3、2、1。将这个栈转置后，从栈顶到栈底为1、2、3、4、5，也就是实现栈中元素的逆序，但是只能用递归函数来实现，不能用其他数据结构。

【难度】

尉     ★★☆☆

【解答】

本题考查栈的操作和递归函数的设计，我们需要设计出两个递归函数。

递归函数一：将栈stack的栈底元素返回并移除。

	public static int getAndRemoveLastElement(Stack<Integer> stack) {
		int result = stack.pop();
		if (stack.isEmpty()) {
			return result;
		} else {
			int last = getAndRemoveLastElement(stack);
			stack.push(result);
			return last;
		}
	}

如果从stack的栈顶到栈底依次为3、2、1，这个函数的具体过程如图1-4所示。

	public static void reverse(Stack<Integer> stack) {
		if (stack.isEmpty()) {
			return;
		}
		int i = getAndRemoveLastElement(stack);
		reverse(stack);
		stack.push(i);
	}

如果从stack的栈顶到栈底依次为3、2、1，reverse函数的具体过程如图1-5所示。

getAndRemoveLastElement方法在图中简单表示为get方法，表示移除并返回当前栈底元素。