如何实现：双栈实现队列双队列实现栈

电玩女神 2022-07-14 11:17 260阅读 0赞

看代码就懂咯

package com.galaxy.fym.queueandstack;
    
    import java.util.Stack;
    
    /** * Created by fengyiming on 2016/12/7. */
    public class StackTest extends Stack<String> { 
    
        public StackTest(){
            super();
        }
    }

package com.galaxy.fym.queueandstack;
    
    import java.util.Queue;
    import java.util.concurrent.ArrayBlockingQueue;
    
    /** * Created by fengyiming on 2016/12/7. */
    public class TwoQueueToStack { 
    
        private Queue<String> queueTest1 = new ArrayBlockingQueue<String>(100);
    
        private Queue<String> queueTest2 = new ArrayBlockingQueue<String>(100);
    
        public void push(String value) {
            queueTest1.add(value);
        }
    
        /** * 寻找第一队列最后一个入队列的元素 * @return */
        public String pop() {
            String value = null;
            if (queueTest1.size() == 0) {
                return value;
            }
            //计算第一个队列的元素总量，用于第二个队列的元素回归-1条数据回第一个队列
            int i = 0;
            //将第一队列按顺序移入第二队列，记住第一队列的最后一个值
            while (queueTest1.size() != 0) {
                String value1 = queueTest1.remove();
                queueTest2.add(value1);
                value = value1;
                i++;
            }
            //这里其实第二个队列已经是第一队列所有的值了，将第二队列里前-1条元素移会第一个队列
            while (i - 1 > 0) {
                String value1 = queueTest2.remove();
                queueTest1.add(value1);
                i--;
            }
            //清空第二个队列里所有元素
            queueTest2.clear();
            return value;
        }
    
    }

package com.galaxy.fym.queueandstack;
    
    /** * Created by fengyiming on 2016/12/7. */
    public class TwoStackToQueue { 
    
        private StackTest stackTest1 = new StackTest();
    
        private StackTest stackTest2 = new StackTest();
    
    
        public void push(String value){
            stackTest1.push(value);
        }
    
        /** * 寻找第一个栈栈底 * @return */
        public String pop(){
            //本次出队列的值
            String value = null;
            if(stackTest1.size() == 0){
                return value;
            }
            //将第一个栈的数据全部按栈的方式压入第二个栈，这样第二个栈出栈就是入队列的顺序的
            while (stackTest1.size() != 0) {
                String value1 = stackTest1.pop();
                stackTest2.push(value1);
            }
            //第二个栈顶出，相当于队列出最先入的那个元素
            value = stackTest2.pop();
            //再把第二个栈全部压入一个栈
            while (stackTest2.size() != 0){
                String value2 = stackTest2.pop();
                stackTest1.push(value2);
            }
            return value;
        }
    
    }

package com.galaxy.fym.test;
    
    import com.galaxy.fym.queueandstack.TwoQueueToStack;
    import com.galaxy.fym.queueandstack.TwoStackToQueue;
    
    /** * Created by fengyiming on 2016/12/7. * 栈实现队列，队列实现栈 */
    public class Test3 {
    
        public static void main(String[] args){
            queue();
            stack();
        }
    
        private static void queue(){
            TwoStackToQueue twoStackToQueue = new TwoStackToQueue();
            for(int i = 1; i < 5; i++){
                String value = twoStackToQueue.pop();
                System.out.println("出队列：" + value);
            }
            for(int i = 0; i < 9; i++){
                System.out.println("入队列：" + i);
                twoStackToQueue.push(String.valueOf(i));
            }
            for(int i = 1; i < 5; i++){
                String value = twoStackToQueue.pop();
                System.out.println("出队列：" + value);
            }
            for(int i = 9; i < 19; i++){
                System.out.println("入队列：" + i);
                twoStackToQueue.push(String.valueOf(i));
            }
            for(int i = 5; i < 14; i++){
                String value = twoStackToQueue.pop();
                System.out.println("出队列：" + value);
            }
        }
    
        private static void stack(){
            TwoQueueToStack twoQueueToStack = new TwoQueueToStack();
            for(int i = 1; i < 5; i++){
                String value = twoQueueToStack.pop();
                System.out.println("出栈：" + value);
            }
            for(int i = 0; i < 9; i++){
                System.out.println("入栈：" + i);
                twoQueueToStack.push(String.valueOf(i));
            }
            for(int i = 1; i < 5; i++){
                String value = twoQueueToStack.pop();
                System.out.println("出栈：" + value);
            }
            for(int i = 9; i < 14; i++){
                System.out.println("入栈：" + i);
                twoQueueToStack.push(String.valueOf(i));
            }
            for(int i = 5; i < 20; i++){
                String value = twoQueueToStack.pop();
                System.out.println("出栈：" + value);
            }
        }
    }

执行结果：

com.intellij.rt.execution.application.AppMain com.galaxy.fym.test.Test3
    出队列：null
    出队列：null
    出队列：null
    出队列：null
    入队列：0
    入队列：1
    入队列：2
    入队列：3
    入队列：4
    入队列：5
    入队列：6
    入队列：7
    入队列：8
    出队列：0
    出队列：1
    出队列：2
    出队列：3
    入队列：9
    入队列：10
    入队列：11
    入队列：12
    入队列：13
    入队列：14
    入队列：15
    入队列：16
    入队列：17
    入队列：18
    出队列：4
    出队列：5
    出队列：6
    出队列：7
    出队列：8
    出队列：9
    出队列：10
    出队列：11
    出队列：12
    出栈：null
    出栈：null
    出栈：null
    出栈：null
    入栈：0
    入栈：1
    入栈：2
    入栈：3
    入栈：4
    入栈：5
    入栈：6
    入栈：7
    入栈：8
    出栈：8
    出栈：7
    出栈：6
    出栈：5
    入栈：9
    入栈：10
    入栈：11
    入栈：12
    入栈：13
    出栈：13
    出栈：12
    出栈：11
    出栈：10
    出栈：9
    出栈：4
    出栈：3
    出栈：2
    出栈：1
    出栈：0
    出栈：null
    出栈：null
    出栈：null
    出栈：null
    出栈：null