首页 > 代码库 > Cracking the Coding Interview Q3.1
Cracking the Coding Interview Q3.1
Describe how you could use a single array to implement three stacks.
思路1：fixed division
package Question3_1;import java.util.EmptyStackException;public class Question { static int stackSize = 10; static int [] buffer = new int [stackSize * 3]; // 3 stack pointers to keep track of the index of the top element static int [] stackPointer = {-1, -1, -1}; 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)); } static void push(int stackNum, int value) throws Exception { /* Check that we have space for the next element */ if (stackPointer[stackNum] + 1 >= stackSize) { throw new FullStackException(); } /* Increment stack pointer and then update top value*/ stackPointer[stackNum]++; buffer[absTopOfStack(stackNum)] = value; } static int pop(int stackNum) throws Exception { if (isEmpty(stackNum)) { throw new EmptyStackException(); } int value = http://www.mamicode.com/buffer[absTopOfStack(stackNum)]; // Get top buffer[absTopOfStack(stackNum)] = 0; // Clear index stackPointer[stackNum]--; // Decrement pointer return value; } static int peek(int stackNum) { if (isEmpty(stackNum)) { throw new EmptyStackException(); } return buffer[absTopOfStack(stackNum)]; } static boolean isEmpty(int stackNum) { return stackPointer[stackNum] == -1; } /* returns index of the top of the stack "stackNum", in absolute terms */ static int absTopOfStack(int stackNum) { return stackNum * stackSize + stackPointer[stackNum]; } }
思路2：
package Question3_1;import CtCILibrary.AssortedMethods;public class QuestionB { 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)); } public static int numberOfElements() { return stacks[0].size + stacks[1].size + stacks[2].size; } public static int nextElement(int index) { if (index + 1 == total_size) { return 0; } else { return index + 1; } } public static int previousElement(int index) { if (index == 0) { return total_size - 1; } else { return index - 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++; } for (int i = (stack.start + stack.capacity - 1) % total_size; // end of array 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); stacks[stackNum].capacity++; } 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; } 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 =http://www.mamicode.com/ buffer[stack.pointer]; buffer[stack.pointer] = 0; stack.pointer = previousElement(stack.pointer); stack.size--; return value; } static int peek(int stackNum) { StackData stack = stacks[stackNum]; return buffer[stack.pointer]; } static boolean isEmpty(int stackNum) { StackData stack = stacks[stackNum]; return stack.size == 0; }}package Question3_1;public 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; }}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。