用数组结构实现大小固定的对列和栈。
设置start和end变量，初始都指向0位置。size变量约束start和end的行为。用户要设置队列的长度initialSize。
size是随着数的加入和弹出动态增减的~初始是0。只要不超过数组的initialSize（不小于0）就可以不断增（减）队列中的数，否则报错。
end：如果新加一个数，填到的位置。只要size小于initialSize，就可以将新加的数放到end所在位置。end=initialSize-1时，会跳回0位置。否则end++，size+1。
start：如果要取一个数，从哪个位置取。只要size大于0，就可以将start所在位置的数返回给用户。start=initialSize-1时，会跳回0位置。否则start++，size-1。
size为栈的大小。设置一个index表示当前所在位置。
压栈数存到index当前位置且index++。
出栈取出index当前位置的数且index--。
如果index=size表示栈满，再压栈会报错。
如果index=0表示栈空，再出栈会报错。
1 package class_03; 2 3 public class Code_01_Array_To_Stack_Queue { 4 5 public static class ArrayStack { 6 private Integer[] arr; 7 private Integer size; 8 9 public ArrayStack(int initSize) { 10 if (initSize < 0) { 11 throw new IllegalArgumentException("The init size is less than 0"); 12 } 13 arr = new Integer[initSize]; 14 size = 0; 15 } 16 17 public Integer peek() { 18 if (size == 0) { 19 return null; 20 } 21 return arr[size - 1]; 22 } 23 24 public void push(int obj) { 25 if (size == arr.length) { 26 throw new ArrayIndexOutOfBoundsException("The queue is full"); 27 } 28 arr[size++] = obj; 29 } 30 31 public Integer pop() { 32 if (size == 0) { 33 throw new ArrayIndexOutOfBoundsException("The queue is empty"); 34 } 35 return arr[--size]; 36 } 37 } 38 39 public static class ArrayQueue { 40 private Integer[] arr; 41 private Integer size; 42 private Integer first; 43 private Integer last; 44 45 public ArrayQueue(int initSize) { 46 if (initSize < 0) { 47 throw new IllegalArgumentException("The init size is less than 0"); 48 } 49 arr = new Integer[initSize]; 50 size = 0; 51 first = 0; 52 last = 0; 53 } 54 55 public Integer peek() { 56 if (size == 0) { 57 return null; 58 } 59 return arr[first]; 60 } 61 62 public void push(int obj) { 63 if (size == arr.length) { 64 throw new ArrayIndexOutOfBoundsException("The queue is full"); 65 } 66 size++; 67 arr[last] = obj; 68 last = last == arr.length - 1 ? 0 : last + 1; 69 } 70 71 public Integer poll() { 72 if (size == 0) { 73 throw new ArrayIndexOutOfBoundsException("The queue is empty"); 74 } 75 size--; 76 int tmp = first; 77 first = first == arr.length - 1 ? 0 : first + 1; 78 return arr[tmp]; 79 } 80 } 81 82 public static void main(String[] args) { 83 84 } 85 86 }
准备两个栈，一个Data栈，一个min栈。
第一个数开始进Data栈时，同时压入min栈。
第二个数进Data栈时，将Data栈顶元素d与min栈顶元素m比较，如果Data栈顶元素d小，则在min栈中压入d，如果min栈顶元素m小，则在min栈中压入m，···以此类推，min栈栈顶元素就是当前Data栈中最小元素。
Data栈中的元素要出栈时，min栈中对应位置的元素也出栈。
?? 
1 package class_03; 2 3 import java.util.Stack; 4 5 public class Code_02_GetMinStack { 6 public static class MyStack1 { 7 private Stack<Integer> stackData; 8 private Stack<Integer> stackMin; 9 10 public MyStack1() { 11 this.stackData = new Stack<Integer>(); 12 this.stackMin = new Stack<Integer>(); 13 } 14 15 public void push(int newNum) { 16 if (this.stackMin.isEmpty()) { 17 this.stackMin.push(newNum); 18 } else if (newNum <= this.getmin()) { 19 this.stackMin.push(newNum); 20 } 21 this.stackData.push(newNum); 22 } 23 24 public int pop() { 25 if (this.stackData.isEmpty()) { 26 throw new RuntimeException("Your stack is empty."); 27 } 28 int value = this.stackData.pop(); 29 if (value == this.getmin()) { 30 this.stackMin.pop(); 31 } 32 return value; 33 } 34 35 public int getmin() { 36 if (this.stackMin.isEmpty()) { 37 throw new RuntimeException("Your stack is empty."); 38 } 39 return this.stackMin.peek(); 40 } 41 } 42 43 public static class MyStack2 { 44 private Stack<Integer> stackData; 45 private Stack<Integer> stackMin; 46 47 public MyStack2() { 48 this.stackData = new Stack<Integer>(); 49 this.stackMin = new Stack<Integer>(); 50 } 51 52 public void push(int newNum) { 53 if (this.stackMin.isEmpty()) { 54 this.stackMin.push(newNum); 55 } else if (newNum < this.getmin()) { 56 this.stackMin.push(newNum); 57 } else { 58 int newMin = this.stackMin.peek(); 59 this.stackMin.push(newMin); 60 } 61 this.stackData.push(newNum); 62 } 63 64 public int pop() { 65 if (this.stackData.isEmpty()) { 66 throw new RuntimeException("Your stack is empty."); 67 } 68 this.stackMin.pop(); 69 return this.stackData.pop(); 70 } 71 72 public int getmin() { 73 if (this.stackMin.isEmpty()) { 74 throw new RuntimeException("Your stack is empty."); 75 } 76 return this.stackMin.peek(); 77 } 78 } 79 80 public static void main(String[] args) { 81 MyStack1 stack1 = new MyStack1(); 82 stack1.push(3); 83 System.out.println(stack1.getmin()); 84 stack1.push(4); 85 System.out.println(stack1.getmin()); 86 stack1.push(1); 87 System.out.println(stack1.getmin()); 88 System.out.println(stack1.pop()); 89 System.out.println(stack1.getmin()); 90 91 System.out.println("============="); 92 93 MyStack1 stack2 = new MyStack1(); 94 stack2.push(3); 95 System.out.println(stack2.getmin()); 96 stack2.push(4); 97 System.out.println(stack2.getmin()); 98 stack2.push(1); 99 System.out.println(stack2.getmin()); 100 System.out.println(stack2.pop()); 101 System.out.println(stack2.getmin()); 102 } 103 104 }
工程上不会这么写，但考试会考。
准备两个队列，来回倒。
进队的时候都进入第一个队列。
想出队时，两个队列来回倒，出几个就倒几次，每次倒完两个队列要换一下引用，
第一个队列中先进的前n-1个数，放入第二的队列中，第一个队列中剩下的一个数返回给用户，
第二个队列中先进的前n-1个数，放入第一的队列中，第二个队列中剩下的一个数返回给用户，
·····以此类推
准备两个栈结构，一个push栈，一个pop栈。
用户新给的数永远进push栈，用户想取一个数永远从pop栈中拿。
将push栈中的数依次压入pop栈，从pop栈中拿数。
向pop栈压栈的时候有两个限制：
①如果push决定要向pop中倒数，一次要全部倒完！
②如果pop栈里有东西，push栈不能向pop栈里倒数！
?? 
1 package class_03; 2 3 import java.util.LinkedList; 4 import java.util.Queue; 5 import java.util.Stack; 6 7 public class Code_03_StackAndQueueConvert { 8 9 public static class TwoStacksQueue { 10 private Stack<Integer> stackPush; 11 private Stack<Integer> stackPop; 12 13 public TwoStacksQueue() { 14 stackPush = new Stack<Integer>(); 15 stackPop = new Stack<Integer>(); 16 } 17 18 public void push(int pushInt) { 19 stackPush.push(pushInt); 20 } 21 22 public int poll() { 23 if (stackPop.empty() && stackPush.empty()) { 24 throw new RuntimeException("Queue is empty!"); 25 } else if (stackPop.empty()) { 26 while (!stackPush.empty()) { 27 stackPop.push(stackPush.pop()); 28 } 29 } 30 return stackPop.pop(); 31 } 32 33 public int peek() { 34 if (stackPop.empty() && stackPush.empty()) { 35 throw new RuntimeException("Queue is empty!"); 36 } else if (stackPop.empty()) { 37 while (!stackPush.empty()) { 38 stackPop.push(stackPush.pop()); 39 } 40 } 41 return stackPop.peek(); 42 } 43 } 44 45 public static class TwoQueuesStack { 46 private Queue<Integer> queue; 47 private Queue<Integer> help; 48 49 public TwoQueuesStack() { 50 queue = new LinkedList<Integer>(); 51 help = new LinkedList<Integer>(); 52 } 53 54 public void push(int pushInt) { 55 queue.add(pushInt); 56 } 57 58 public int peek() { 59 if (queue.isEmpty()) { 60 throw new RuntimeException("Stack is empty!"); 61 } 62 while (queue.size() != 1) { 63 help.add(queue.poll()); 64 } 65 int res = queue.poll(); 66 help.add(res); 67 swap(); 68 return res; 69 } 70 71 public int pop() { 72 if (queue.isEmpty()) { 73 throw new RuntimeException("Stack is empty!"); 74 } 75 while (queue.size() > 1) { 76 help.add(queue.poll()); 77 } 78 int res = queue.poll(); 79 swap(); 80 return res; 81 } 82 83 private void swap() { 84 Queue<Integer> tmp = help; 85 help = queue; 86 queue = tmp; 87 } 88 89 } 90 91 }
原文：https://www.cnblogs.com/superjishere/p/12295140.html