题目:如何使用两个栈实现队列
思路:假设用来实现队列的两个栈分别为stack1和stack2,保证两个栈总有一个为空
入队算法:
如果stack2不为空,先将stack2中的元素弹出并压入stack1;
将元素压入stack1
出队算法:
如果stack2不为空,那么栈顶元素就是队首元素,直接弹出栈顶元素即可;
如果stack2为空,那么先将stack1中的元素弹出并压入stack2,弹出stack2的栈顶元素;

/**
 * 使用两个栈实现队列
 * @param <AnyType> 元素类型
 */
public class QueueWithTwoStacks<AnyType> {
   
     

    LinkedListStack<AnyType> stack1;
    LinkedListStack<AnyType> stack2;

    /**
     * 构造方法
     */
    public QueueWithTwoStacks() {
        stack1 = new LinkedListStack<AnyType>();
        stack2 = new LinkedListStack<AnyType>();
    }

    /**
     * 判断是否为空
     * @return true 为空 false 不为空
     */
    public boolean isEmpty() {
        if (stack1.isEmpty() && stack2.isEmpty()) {
            return true;
        }
        return false;
    }

    /**
     * 入队
     * @param data 入队元素值
     */
    public void enQueue(AnyType data) {
        // 如果stack2中有值,先将值弹出压入stack1
        while (!stack2.isEmpty()) {
            stack1.push(stack2.pop());
        }
        // 将元素值压入stack1
        stack1.push(data);
    }

    /**
     * 出队
     * @return 出队元素
     */
    public AnyType deQueue() {
        // 如果stack2不为空,说明元素都在stack2中,此时stack2的栈顶元素就是队首元素
        if (!stack2.isEmpty()) {
            return stack2.pop();
        } else {
            // 如果stack2为空,说明元素都在stack1中,所以先将元素从stack1弹出,并压入stack2中
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
            // 此时stack2的栈顶元素就是队首元素
            return stack2.pop();
        }
    }
}

测试代码,如下:

/**
 * 使用两个栈实现队列测试方法
 */
public static void queueWithTwoStacksTest() {
    QueueWithTwoStacks<Integer> queue = new QueueWithTwoStacks<Integer>();

    // 结果为true
    System.out.println(queue.isEmpty());

    queue.enQueue(9);
    queue.enQueue(8);
    queue.enQueue(7);
    queue.deQueue();
    queue.enQueue(6);
    queue.enQueue(5);

    // 结果为false
    System.out.println(queue.isEmpty());

    // 结果为 8 7 6 5 
    while (!queue.isEmpty()) {
        System.out.print(queue.deQueue() + " ");
    }
}
 题目:如何使用两个队列来实现一个栈
 思路:假设用来实现栈的两个队列分别为queue1和queue2,确保总有一个队列是空的
 入栈算法:
 如果queue1为空,则对queue2执行入队操作
 否则就对queue1执行如对操作
 出栈算法:
 从有元素的队列移动n-1个元素到另一个队列,删除当前队列的最后一个元素,即可完成出栈
 如果queue1非空,那么从queue1移动n-1个元素到queue2中,然后对queue1的最后一个元素执行出队操作;
 如果queue2非空,那么从queue2移动n-1个元素到queue1中,然后对queue2的最后一个元素执行出队操作;

/**
 * 使用两个队列来实现一个栈
 * @param <AnyType>
 */
public class StackWithTwoQueues<AnyType> {
   
     

    LinkListQueue<AnyType> queue1;
    LinkListQueue<AnyType> queue2;

    /**
     * 构造方法
     */
    public StackWithTwoQueues() {
        queue1 = new LinkListQueue<AnyType>();
        queue2 = new LinkListQueue<AnyType>();
    }

    /**
     * 判断栈是否为空
     * @return true 是空栈 false 不是空栈
     */
    public boolean isEmpty() {
        return (queue1.isEmpty() && queue2.isEmpty());
    }

    /**
     * 入栈
     * 向非空的队列添加数据
     * @param data 入栈元素
     */
    public void push(AnyType data) {
        if (queue1.isEmpty()) {
            queue2.enQueue(data);
        } else {
            queue1.enQueue(data);
        }
    }

    /**
     * 出栈
     * @return 出栈元素
     */
    public AnyType pop() {
        int size;
        int count;
        if (queue1.isEmpty()) {
            count = 0;
            size = queue2.getQueueSize();
            while (count < size - 1) {
                queue1.enQueue(queue2.deQueue());
                count++;
            }
            return queue2.deQueue();
        } else {
            count = 0;
            size = queue1.getQueueSize();
            while (count < size - 1) {
                queue2.enQueue(queue1.deQueue());
                count++;
            }
            return queue1.deQueue();
        }
    }
}

测试代码,如下:

/**
 * 使用两个队列来实现一个栈的测试类
 */
public static void stackWithTwoQueuesTest() {
    StackWithTwoQueues<Integer> stack = new StackWithTwoQueues<Integer>();

    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);
    stack.push(5);

    // 结果为 5 4 3 2 1 
    while (!stack.isEmpty()) {
        System.out.print(stack.pop() + " ");
    }
}