第2章 第1节 栈和队列(一)

设计一个有getMin功能的栈

【题目】

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

【要求】

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

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

【难度】

士     ★☆☆☆

【解答】

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

第一种设计方案

(1)压入数据规则

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

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

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

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

Ø 如果stackMin中栈顶元素小,则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将最先弹出,与预想的队列顺序就不一致。

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

这个选择的时机可以有很多,调用add、poll和peek三种方法中的任何一种时发生“压”入数据的行为都是可以的。只要满足如上提到的两点,就不会出错。具体实现请参看如下的TwoStacksQueue类:
	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的栈底元素返回并移除。

具体过程就是如下代码中的getAndRemoveLastElement方法。
	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所示。


递归函数二:逆序一个栈,就是题目要求实现的方法,具体过程就是如下代码中的reverse方法。该方法使用了上面提到的getAndRemoveLastElement方法。
	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方法,表示移除并返回当前栈底元素。