Stack_Queue 固定容量的栈组SetOfStacks @CareerCup

原文：

Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this. SetOfStacks should be composed of several stacks, and should create a new stack once the previous one exceeds capacity. SetOfStacks.push() and SetOfStacks.pop() should behave identically to a single stack (that is, pop() should return the same values as it would if there were just a single stack).

FOLLOW UP

Implement a function popAt(int index) which performs a pop operation on a specific sub-stack.

译文：

栈就像叠盘子，当盘子叠得太高时，就会倾斜倒下。因此，在真实的世界中，当一叠盘子 (栈)超过了一定的高度时，我们就会另起一堆，再从头叠起。实现数据结构SetOfStacks 来模拟这种情况。SetOfStacks由几个栈组成，当前一栈超出容量时，需要创建一个新的栈 来存放数据。SetOfStacks.push()和SetOfStacks.pop()的行为应当和只有一个栈时 表现的一样。

进一步地，

实现函数popAt(int index)在指定的子栈上进行pop操作。

思路：

我们要设计自己的栈（Stack），栈节点（Node）。然后用一个ArrayList<Stack>来构成栈组SetOfStacks。

我们的栈里面的节点以链表方式存储最佳，因为我们要频繁对栈顶栈底元素操作，如果用array将会导致大量的元素移动。所以我们用链表方式存储栈内的节点，同时对每个栈，我们还维护一个capacity的变量，用来track当前栈内元素个数！

因此，就不难理解Node类的数据结构，Stack类中比较有意思的是join，相当于连接两个节点，在每push进一个新元素时，新元素都要和旧的栈顶元素做join。还有一个函数叫做removeBottom，并不expose给user调用，而是在SetOfStacks的leftShift函数中会用到。

至于SetOfStacks类，有一个原则就是，压入的新元素总是被压倒最后一个栈，这样能保证前面的栈都是满的！所以没有pushAt函数，但是我们支持popAt函数，就是制定在某个栈上pop，当某个栈（除了最后一个栈）被pop掉栈顶元素，那么那个栈就不是满的了，所以我们要递归地从下一个栈，把它的栈底元素移到当前栈。这就需要用到leftShift函数。具体步骤可参考代码，已经详细注释！

这样我们就封装好了SetOfStacks类，也是用户唯一能看到的类。

package Stack_Queue;

import java.util.ArrayList;

public class S3_3 {

	//=================================== Node 自定义栈节点，以链表节点方式存在
	static class Node {
		public Node above;
		public Node below;
		public int value;
		public Node (int value) {
			this.value = value;
		}
	}
	
	//=================================== Stack 自定义的Stack类，以链表方式存储数据！
	static class Stack {
		private int capacity;
		public Node top;
		public Node bottom;
		public int size = 0;
		
		public Stack(int capacity) {
			this.capacity = capacity;
		}
		
		// 判断stack是否满了
		public boolean isFull() {
			return size == capacity;
		}
		
		// 判断stack是否为空
		public boolean isEmpty() {
			return size == 0;
		}
		
		// 让栈内的两个元素产生关联
		public void join(Node above, Node below) {
			if(below != null) {
				below.above = above;
			}
			if(above != null) {
				above.below = below;
			}
		}
		
		// 压入一个元素
		public boolean push(int val) {
			if(size >= capacity) {
				return false;
			}
			size++;
			Node newNode = new Node(val);
			if(size == 1) {		// 该初始化bottom的情况
				bottom = newNode;
			}
			join(newNode, top);		// 把newNode放在原top的上面
			top = newNode;			// 更新栈顶指针
			return true;
		}
		
		// 弹栈
		public int pop() {
			Node ret = top;
			top = top.below;		// 更新栈顶指针
			size--;					// 更新栈size
			return ret.value;
		}
		
		// 移除栈底元素，返回被移除的值
		public int removeBottom() {
			Node ret = bottom;
			bottom = bottom.above;
			if(bottom != null) {
				bottom.below = null;
			}
			size--;
			return ret.value;
		}
	}
	
	
	//=================================== SetOfStacks 栈组
	static class SetOfStacks {
		ArrayList<Stack> stacks = new ArrayList<Stack>();
		public int capacity;
		
		public SetOfStacks(int capacity) {
			this.capacity = capacity;
		}
		
		// 从stacks中得到最后一个Stack
		public Stack getLastStack() {
			if(stacks.size() == 0) {
				return null;
			}
			return stacks.get(stacks.size() - 1);
		}
		
		// 把元素压入SetOfStacks
		public void push(int val) {
			Stack last = getLastStack();
			if(last != null && !last.isFull()) {
				last.push(val);
			} else{		// 最后一个stack已经满了，或者stacks为空，必须新建最后一个stack
				Stack stack = new Stack(capacity);
				stack.push(val);
				stacks.add(stack);
			}
		}
		
		// 从SetOfStacks中弹栈
		public int pop() {
			Stack last = getLastStack();
			int val = last.pop();
			if(last.size == 0) {		// 如果最后一个栈空了，就从stacks中移除
				stacks.remove(stacks.size()-1);
			}
			return val;
		}
		
		// 在第index个栈上弹栈
		public int popAt(int index) {
			return leftShift(index, true);
		}
		
		// 一个重要的辅助函数，移除当前栈顶元素，并利用递归移动下一个栈底元素到当前栈顶
		public int leftShift(int index, boolean removeTop) {
			Stack stack = stacks.get(index);
			int removedItem;
			if(removeTop) {
				removedItem = stack.pop();
			} else {
				removedItem = stack.removeBottom();
			}
			
			if(stack.isEmpty()) {
				stacks.remove(index);
			} else if(index+1 < stacks.size()) {		// 确保有下一个栈，否则证明现在的栈已经是最后一个栈了！
				// 把下一个栈的栈底元素移到当前栈的栈顶，这样能保证除了最后一个栈，其他栈都是满的！
				int v = leftShift(index+1, false);	
				stack.push(v);
			}
			
			return removedItem;
		}
		
		// 查看SetOfStacks栈组是否为空，只要看最后一个栈是否为空即可
		public boolean isEmpty() {
			Stack last = getLastStack();
			return last==null || last.isEmpty();
		}
		
	}
	
	
	public static void main(String[] args) {
		int capacity_per_substack = 5;
		SetOfStacks set = new SetOfStacks(capacity_per_substack);
		for (int i = 0; i < 34; i++) {
			set.push(i);
		}
		for (int i = 0; i < 34; i++) {
			System.out.println("Popped " + set.pop());
		}		
	}
}