算法--栈和队列互相实现

1栈与队列的区别

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

2 栈和队列方法概要

Java语言。

2.1 栈（Stack）方法概要

方法	作用	返回值
empty()	测试堆栈是否为空	boolean
peek()	查看堆栈顶部的对象，但不从堆栈中移除它。	E
pop()	移除堆栈顶部的对象，并作为此函数的值返回该对象。	E
push(E item)	把项压入堆栈顶部。	E
search(Object o)	返回对象在堆栈中的位置，以 1 为基数。使用 equals 方法比较 o 与堆栈中的项。	int

2.2 队列（Queue）方法概要

方法	作用	返回值
offer(E e)	将指定的元素插入此队列（如果立即可行且不会违反容量限制），当使用有容量限制的队列时，此方法通常要优于add(E)，后者可能无法插入元素，而只是抛出一个异常。	boolean
poll()	获取并移除此队列的头，如果此队列为空，则返回 null	E
peek()	获取但不移除此队列的头；如果此队列为空，则返回 null。	E
add(E e)	将指定的元素插入此队列（如果立即可行且不会违反容量限制），在成功时返回 true，如果当前没有可用的空间，则抛出 IllegalStateException。	boolean
element()	获取，但是不移除此队列的头	E
remove()	获取并移除此队列的头。	E

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();
    }
}

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面试题含答案--适合中高级（下）
算法之美：栈和队列