Stack_Queue 一个数组实现三个栈 @CareerCup

原文：

Describe how you could use a single array to implement three stacks.

译文：

你如何只用一个数组实现三个栈？

分两种情况：1）固定的栈，即栈和栈之间无法共享空间，每个栈都只有固定的空间。用n个栈顶指针来记录栈顶位置即可。

2）非固定的栈：有必要构造一个StackData的类来存放关于某个栈的信息，包括栈的开始位置，指向当前栈顶元素的位置，实际装有元素个数，可装元素的容量

还要一个关键的shift函数，用于把某个栈整体往后挪一位，以便为前一个栈腾出空间。

package Stack_Queue;

public class S3_1_Fixed {

	// ================ Version 1 Fixed Division Stack
	static int stackSize = 100;
	static int[] buffer = new int[stackSize * 3];
	static int[] stackPointer = {-1, -1, -1};	// 存放用于记录栈顶元素的index
	
	// 把value压入第stackNum个栈
	public static void push(int stackNum, int value) throws Exception{
		if(stackPointer[stackNum] + 1 >= stackSize) {
			throw new Exception("Out of space.");
		}
		
		stackPointer[stackNum]++;
		buffer[absTopOfStack(stackNum)] = value;
	}
	
	// 取出第stackNum个栈的栈顶元素
	public static int pop(int stackNum) throws Exception {
		if(stackPointer[stackNum] == -1) {
			throw new Exception("Trying to pop an empty stack");
		}
		int value = buffer[absTopOfStack(stackNum)];
		buffer[absTopOfStack(stackNum)] = 0;		// 栈顶元素置零
		stackPointer[stackNum]--;			// 把栈顶元素index减一
		return value;
	}
	
	// 查看第stackNum个栈的栈顶元素
	public static int peek(int stackNum) throws Exception {
		int index = absTopOfStack(stackNum);
		if(stackPointer[stackNum] == -1) {
			throw new Exception("Trying to peek an empty stack");
		}
		return buffer[index];
	}
	
	// 判断第stackNum个栈是否为空
	public static boolean isEmpty(int stackNum) {
		return stackPointer[stackNum] == -1;
	}
	
	// 返回第stackNum个栈的栈顶元素的index
	public static int absTopOfStack(int stackNum) {
		return stackNum * stackSize + stackPointer[stackNum];
	}
	

	public static void main(String [] args) throws Exception  {
		push(2, 4);
		System.out.println("Peek 2: " + peek(2));
		push(0, 3);
		push(0, 7);
		push(0, 5);
		System.out.println("Peek 0: " + peek(0));
		pop(0);
		System.out.println("Peek 0: " + peek(0));
		pop(0);
		System.out.println("Peek 0: " + peek(0));
	}
	
	
}

package Stack_Queue;

import CtCILibrary.AssortedMethods;

public class S3_1_Flexible {

	//================ Version 2 Flexible Division Stack
	static int number_of_stacks = 3;
	static int default_size = 4;
	static int total_size = default_size * number_of_stacks;
	static StackData[] stacks = { new StackData(0, default_size),
											  new StackData(default_size, default_size),
											  new StackData(default_size * 2, default_size) };
	static int[] buffer = new int[total_size];

	public static void main(String[] args) throws Exception {
		push(0, 10);
		push(1, 20);
		push(2, 30);

		push(1, 21);
		push(0, 11);
		push(0, 12);

		pop(0);

		push(2, 31);

		push(0, 13);
		push(1, 22);

		push(2, 31);
		push(2, 32);
		push(2, 33);
		push(2, 34);

		System.out.println("Final Stack: " + AssortedMethods.arrayToString(buffer));

		pop(1);
		push(2, 35);

		System.out.println("Final Stack: " + AssortedMethods.arrayToString(buffer));
	}

	// 3个栈总共的element数量
	public static int numberOfElements() {
		return stacks[0].size + stacks[1].size + stacks[2].size;
	}

	// 得到index的下一个位置，关键是处理wrap
	public static int nextElement(int index) {
		if (index + 1 == total_size) {		// wrap
			return 0;
		} else {
			return index + 1;
		}
	}

	// 得到index的前一个位置，关键是处理wrap
	public static int previousElement(int index) {
		if (index == 0) {		// wrap
			return total_size - 1;
		} else {
			return index - 1;
		}
	}

	// 把第stackNum栈的所有元素往后移1位
	public static void shift(int stackNum) {
		StackData stack = stacks[stackNum];
		if (stack.size >= stack.capacity) {
			int nextStack = (stackNum + 1) % number_of_stacks;
			shift(nextStack); 			// make some room
			stack.capacity++;
		}
		
		// end of array
		for (int i = (stack.start + stack.capacity - 1) % total_size;  stack.isWithinStack(i, total_size); i = previousElement(i)) {
			buffer[i] = buffer[previousElement(i)];
		}
		
		buffer[stack.start] = 0;
		stack.start = nextElement(stack.start);		// move start start
		stack.pointer = nextElement(stack.pointer); 	// move stack pointer
		stack.capacity--; 									// return capacity to original
	}

	/* Expand stack by shifting over other stacks */
	public static void expand(int stackNum) {
		shift((stackNum + 1) % number_of_stacks);	// 把第stackNum + 1栈的所有元素往后移1位，使得第stackNum栈多一个元素的空间
		stacks[stackNum].capacity++;
	}

	// 在第stackNum栈内压入value
	static void push(int stackNum, int value) throws Exception {
		StackData stack = stacks[stackNum];
		/* Check that we have space */
		if (stack.size >= stack.capacity) {
			if (numberOfElements() >= total_size) { 		// Totally full
				throw new Exception("Out of space.");
			} else { 					// just need to shift things around
				expand(stackNum);
			}
		}
		/*
		 * Find the index of the top element in the array + 1, and increment the
		 * stack pointer
		 */
		stack.size++;
		stack.pointer = nextElement(stack.pointer);
		buffer[stack.pointer] = value;
	}

	// 从第stackNum栈内弹出栈顶元素
	static int pop(int stackNum) throws Exception {
		StackData stack = stacks[stackNum];
		if (stack.size == 0) {
			throw new Exception("Trying to pop an empty stack.");
		}
		int value = buffer[stack.pointer];
		buffer[stack.pointer] = 0;
		stack.pointer = previousElement(stack.pointer);
		stack.size--;
		return value;
	}

	// 访问第stackNum个栈的栈顶元素
	static int peek(int stackNum) {
		StackData stack = stacks[stackNum];
		return buffer[stack.pointer];
	}

	// 判断第stackNum个栈是否为空
	static boolean isEmpty(int stackNum) {
		StackData stack = stacks[stackNum];
		return stack.size == 0;
	}

	static class StackData {
		public int start;			// 开始位置
		public int pointer;		// 指向当前栈顶元素
		public int size = 0;		// 实际装有元素个数
		public int capacity;		// 可装元素容量

		public StackData(int _start, int _capacity) {
			start = _start;
			pointer = _start - 1;
			capacity = _capacity;
		}

		public boolean isWithinStack(int index, int total_size) {
			// Note: if stack wraps, the head (right side) wraps around to the left.
			if (start <= index && index < start + capacity) {
				// non-wrapping, or "head" (right side) of wrapping case
				return true;
			} else if (start + capacity > total_size && index < (start + capacity) % total_size) {
				// tail (left side) of wrapping case
				return true;
			}
			return false;
		}
	}
}