数据结构与算法

1栈与队列的区别

1. 队列先进先出FIFO，栈先进后出FILO
2. 对插入和删除操作的”限定”。 栈是限定只能在表的一端进行插入和删除操作的线性表。 队列是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。
3. 遍历数据速度不同
4. java中：Stack是类继承Vector。Queue是一个接口实现了Collection,Iterable。

2 栈和队列方法概要

Java语言。

2.1 栈（Stack）方法概要

2.2 队列（Queue）方法概要

3 由两个栈实现一个队列 （✭✭✩✩✩）

实现一个队列主要是实现其方法。

3.1 分析

164c2a5b494d9d73.jpeg

3.2 撸码

public static class TwoStackQueue<E> {
    private Stack<E> stackA;
    private Stack<E> stackB;

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

    /**
     * 添加元素逻辑
     *
     * @param e 要添加的元素
     * @return 这里只是遵循 Queue 的习惯，这里简单处理返回 true 即可
     */
    public boolean add(E e) {
        stackA.push(e);
        return true;
    }

    /**
     * 去除元素的时候需要判断两个地方，StackA & StackB 是否都为空
     * StackB 为空的时候讲StackA中的元素全部依次压入 StackB
     *
     * @return 返回队列中的元素 如果队列为空返回 null
     */
    public E poll() {
        //如果队列中没有元素则直接返回空，也可以选择抛出异常
        if (stackB.isEmpty() && stackA.isEmpty()) {
            return null;
        }

        if (stackB.isEmpty()) {
            while (!stackA.isEmpty()) {
                stackB.add(stackA.pop());
            }
        }

        return stackB.pop();
    }

    /**
     * peek 操作不取出元素，只返回队列头部的元素值
     *
     * @return 队列头部的元素值
     */
    public E peek() {
        //如果队列中没有元素则直接返回空，也可以选择抛出异常
        if (stackB.isEmpty() && stackA.isEmpty()) {
            return null;
        }

        if (stackB.isEmpty()) {
            while (!stackA.isEmpty()) {
                stackB.add(stackA.pop());
            }
        }

        return stackB.peek();
    }
}

3.3用两个栈模拟实现一个队列，其最大容量是多少？

如果这两个堆栈的容量分别是m和n（m>n)，你的方法能保证队列的最大容量是多少？

分析：栈的特点是“后进先出(LIFO)”，而队列的特点是“先进先出(FIFO)”。用两个栈模拟实现一个队列的基本思路是：用一个栈作为存储空间，另一个栈作为输出缓冲区，入队时把元素按顺序压入两栈模拟的队列，出队时按入队的顺序出栈即可

如下图，用容量为m（较大的）的栈作为存储空间，容量为n的栈作为输出缓冲区，先将入队的前n个元素push进存储空间栈

20200307205856303.png

随后对存储空间栈中的每个元素进行出栈(pop)操作，继而压入(push)输出缓冲区栈，如下图所示

20200307205951587.png

对于剩余入队的前n+1个元素，将他们压入存储空间栈，两个栈的状态如下图：

20200307210024814.png

此时已经入队了2n+1个元素，若此时进行出队操作，先将输出缓冲区栈中的元素出栈(pop)并输出：Q1,Q2 ,……,Qn，再对存储空间栈中的n个元素进行出栈(pop)并压入输入缓冲区栈，状态图如下：

20200307210325571.png

然后对存储空间栈进行一次出栈(pop)操作并输出：Qn+1，最后再对输出缓冲区栈中的所有元素进行出栈(pop)操作并输出Qn+2,Qn+3,......,Q2n,Q2n+1这样两个栈 总的输出序列为

即在已经入队了2n+1个元素的情况下，还要继续向队列中添加更多的元素，将无法满足按入队的顺序出队。
综上所述，两个栈所模拟的队列的最大容量为2n+1。

4 两个队列实现一个栈 （✭✭✩✩✩）

4.1 解析

164c2a5b49e8e71b.jpeg

4.2 撸码

public static class TwoQueueStack<E> {
   private Queue<E> queueA;
   private Queue<E> queueB;

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

   /**
    * 选一个非空的队列入队
    *
    * @param e
    * @return
    */
   public E push(E e) {
       if (queueA.size() != 0) {
           System.out.println("从 queueA 入队 " + e);
           queueA.add(e);
       } else if (queueB.size() != 0) {
           System.out.println("从 queueB 入队 " + e);
           queueB.add(e);
       } else {
           System.out.println("从 queueA 入队 " + e);
           queueA.add(e);
       }
       return e;
   }

   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("从 queueA 出队 并 queueB 入队 " + result);
                   queueB.add(result);
               }
           }
           System.out.println("从 queueA 出队 " + result);

       } else {
           while (queueB.size() > 0) {
               result = queueB.poll();
               if (queueB.size() != 0) {
                   System.out.println("从 queueB 出队 并 queueA 入队 " + result);
                   queueA.add(result);
               }
           }
           System.out.println("从 queueB 出队" + result);
       }
       return result;
   }
}

参考

2018年Android面试题含答案--适合中高级（下）
算法之美：栈和队列