2019-08-16 队列与堆栈的相互实现

今天看到了关于队列与栈的算法相关的一篇文章，就动手实现了下，留文以记之

基本知识

• 我们都知道，队列是先入先出（FIFO），而堆栈是先入后出（FILO）。但是如果某些情况下，需要用队列实现堆栈，或者是使用堆栈实现队列，又该怎么去做呢？

使用堆栈实现队列

• 对于队列来说，使用poll方式是从队首取出一个元素；对于堆栈，使用pop方式是从栈顶取出一个元素——两者次序刚好相反。要想使用堆栈来实现堆栈，我们是否可以这样去想：将堆栈的元素压入另一个堆栈，然后再将其元素出栈，这样就出队的顺序就是和出栈的顺序一致了。
  
  由图我们不难想到：用两个栈，将元素先压入栈A，所有元素都压进栈A之后，将元素从A出栈，再压入栈B，入栈完毕之后，再出栈——整个过程就是相当于队列的出队，也就由堆栈实现了队列。

• 但是，上面只是一种最简单的情况，也就是等待所有元素入队之后再出队，中间过程没有元素出队。如果，在入队的过程中，也有元素出队，这两个栈又该怎么处理才能满足队列的先入先出原则呢？
  比如，要使用栈实现的队列实现，1、2、3先入队，然后1出队，之后4、5入队

  
  
  

  实际上，只要满足两点就可以：

  • 无论什么时候，只要StackA要往StackB中压入元素，那么必须选择一次性全部压入；
  • 无论什么时候从队列中取元素，必须保证元素是从 StackB 中 pop 出的，也就是说，当 StackB 不为空的时候绝不能再次向 StackB 中压入元素。

必须要满足以上两点，否则，在StackB出栈的时候，出栈次序就不满足队列的先入先出原则！

• 实现代码

import java.util.Stack;

/**
 * @Classname TwoStackQueue
 * @Description 用两个栈实现队列
 * @Date 2019/8/16 10:51
 */
public class TwoStackQueue<E> {
    
    private Stack<E> stackA;
    private Stack<E> stackB;


    public TwoStackQueue() {
        stackA = new Stack<>();
        stackB = new Stack<>();
    }

    /**
     *@Description: 实现向队列添加元素的操作
     * 向栈中压入元素，这里只是简单的遵循Queue的习惯
     *@Param: [e]是要添加的元素
     *@Throws:
     *@return: boolean
     *@date: 2019/8/16-10:53
     */
    public boolean add(E e){
        stackA.push(e);
        return true;
    }

    /**
     *@Description: 实现元素出队列的操作
     * 将A栈元素全部压入B栈
     * 去除元素的时候需要判断两个地方，StackA & StackB 是否都为空
     * StackB 为空的时候讲StackA中的元素全部依次压入 StackB
     *@Param: []
     *@Throws:
     *@return: E  返回队列中的元素 如果队列为空返回 null
     *@date: 2019/8/16-10:57
     */
    public E poll(){
        //如果队列中没有元素则直接返回空，也可以选择抛出异常
        if (stackB.isEmpty()&&stackA.isEmpty()){
            return null;
        }
        //只有当B栈为空的时候，才将A栈的元素压入B栈；否则不允许压入
        if (stackB.isEmpty()){
            while (!stackA.isEmpty()){
                stackB.add(stackA.pop());
            }
        }
        return stackB.pop();
    }


    /**
     *@Description: peek 操作不取出元素，只返回队列头部的元素值
     *@Param: []
     *@Throws:
     *@return: E 队列头部的元素值
     *@date: 2019/8/16-11:07
     */
    public E peek(){
        if (stackB.isEmpty()&&stackA.isEmpty()){
            return null;
        }
        
        if (stackB.isEmpty()){
            while (!stackA.isEmpty()){
                stackB.add(stackA.pop());
            }
        }
        return stackB.peek();
    }

    public static void main(String[] args) {
        TwoStackQueue<Integer> twoStackQueue = new TwoStackQueue<>();
        twoStackQueue.add(1);
        twoStackQueue.add(2);
        twoStackQueue.add(3);
        twoStackQueue.add(4);
        twoStackQueue.add(5);
        System.out.println(twoStackQueue.poll());
        twoStackQueue.add(6);
        twoStackQueue.add(7);
        System.out.println(twoStackQueue.poll());
        System.out.println(twoStackQueue.peek());
    }
}

使用队列实现堆栈

用队列来实现堆栈，不难发现，无论队列怎么出队，出队次序都不会逆序。因此，不能再套用上面堆栈实现队列的方式。但也有类似之处，我们可以知道，用队列实现堆栈，无非就是两个队列进行交替的入队出队操作即可。要做到的就是判断目前出队的值是否是按照放入元素顺序中与那个最后放入的元素值相等

上图，只是第一次的取出操作，但是要注意一个点——怎么样去判断那一次取出之后队列A为空？
可以利用队列大小这个属性，去判断队列中元素的个数——为0即为空队列。

• 同样的，和之前一样，对于堆栈，也有可能出栈和入栈同时进行，出栈之后入栈的元素又该怎么放置呢？
  应该先思考如果连续两次取出应该怎么操作，上面一次取出后 QueueA 空了，若按照相同的思路将 B 中的元素倒入 A 中，那么将会得到 2 ，这看起来没什么问题。那么如果下一步进行的 push 操作，是应该放入 QueueA 还是 QueueB 中才能保证元素先进后出的规则呢，很容易想到是放入 B 中。
  总结一下：
  • 任何时候两个队列总有一个是空的。
  • 添加元素总是向非空队列中 add 元素。

  • 取出元素的时候总是将元素除队尾最后一个元素外的其他元素，导入另一空队列中，最后一个元素出队。

    
    
• 实现代码

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Classname TwoQueueStack
 * @Description 两个队列实现一个栈
 * @Date 2019/8/16 11:16
 */
public class TwoQueueStack<E> {

    private Queue<E> queueA;
    private Queue<E> queueB;

    public TwoQueueStack() {
        queueA = new LinkedList<E>();
        queueB = new LinkedList<E>();
    }


    /**
     *@Description: 实现栈的入栈操作
     * 实际上是选择一个非空的队列进行入队
     *@Param: [e]
     *@Throws:
     *@return: E
     *@date: 2019/8/16-11:29
     */
    public E push(E e){
        if (queueB.size()!=0){
            System.out.println("从B队列入队:" + e);
            queueB.add(e);
        }else {
            System.out.println("从A队列入队:" + e);
            queueA.add(e);
        }
        return e;
    }


    /**
     *@Description: 实现栈的出栈操作
     *@Param: []
     *@Throws:
     *@return: E
     *@date: 2019/8/16-11:35
     */
    public E pop(){
        //两个队列都为空，无元素
        if (queueA.size()==0&&queueB.size()==0){
            return null;
        }
        E result = null;
        if (queueA.size()!=0){
            while (queueA.size()>0){
                result = queueA.poll();
                if (queueA.size()!=0){
                    System.out.println("从A队列出队并从B队列入队:" + result);
                    queueB.add(result);
                }
            }
            System.out.println("从A队列出队:" + result);
        }else {
            while (queueB.size()>0){
                result = queueB.poll();
                if (queueB.size()!=0){
                    System.out.println("从B队列出队并从A队列入队:" + result);
                    queueA.add(result);
                }
            }
            System.out.println("从B队列出队:" + result);
        }
        return result;
    }

    public static void main(String[] args) {
        TwoQueueStack<Integer> twoQueueStack = new TwoQueueStack<>();
        twoQueueStack.push(1);
        twoQueueStack.push(2);
        twoQueueStack.pop();
        twoQueueStack.push(3);
        twoQueueStack.push(4);
        twoQueueStack.pop();
        twoQueueStack.pop();
    }
}