java实现“两个队列实现栈”
两个队列,inputQueue和outputQueue。其中inputQueue用于入栈操作时存放元素,outputQueue用于辅助出栈操作。
例如,入栈元素01234,在inputQueue中存放01234,出栈时,将0123转移到outputQueue,此时inputQueue只剩元素4,4出栈后,将outputQueue中的0123在转移到inputQueue中。
public class StackByTwoQueues<T> { /** * inputQueue:入栈所用队列,outputQueue:出栈用于转移先入栈的元素 */ private static Queue inputQueue = new Queue(); private static Queue outputQueue = new Queue(); /** * 入栈操作 * @param item 入栈元素 * @return 返回入栈的元素 */ private static int push(int item){ return inputQueue.offer(item); } /** * 栈顶元素出栈操作 * @return 返回栈顶元素 */ private static int pop(){ //栈中没有元素,抛出异常 if (inputQueue.size() == 0){ throw new IndexOutOfBoundsException("stack is empty"); } //除了最后入栈的元素,将其他元素转移到outputQueue outCopy(outputQueue,inputQueue); //获取最后入栈元素 int item = inputQueue.pop(); //将outputQueue中的所有元素转移到inputQueue中 inCopy(inputQueue,outputQueue); return item; } /** * 栈顶元素出栈时所做的转移操作, * 除了最后入栈的元素,将其他元素从inputQueue转移到outputQueue * @param dest outputQueue * @param src inputQueue */ private static void outCopy(Queue dest,Queue src){ while (src.size() > 1){ dest.offer(src.pop()); } } /** * 栈顶元素出栈后所做的转移操作,将所有元素从outputQueue转移到inputQueue * @param dest inputQueue * @param src outputQueue */ private static void inCopy(Queue dest,Queue src){ while (src.size() > 0){ dest.offer(src.pop()); } } private static int size(){ return inputQueue.size(); } public static void main(String[] args) { System.out.print("入栈元素:"); for (int i = 0;i<5;i++){ System.out.print(push(i)); } System.out.println(); System.out.println("出栈:"); System.out.println(pop()); System.out.println(pop()); System.out.println(pop()); System.out.println("入栈元素:" + push(20)); System.out.println("入栈元素:" + push(21)); System.out.println("遍历出栈:"); while (size() > 0){ System.out.println(pop()); } } }
运行效果
入栈元素:01234 出栈: 4 3 2 入栈元素:20 入栈元素:21 遍历出栈: 21 20 1 0
Queue类
public class Queue { private LinkedList<Integer> queue; public Queue() { this.queue = new LinkedList<>(); } public int offer(int item){ queue.offer(item); return item; } public int pop(){ return queue.pop(); } public int size(){ return queue.size(); } }