leetcode刷题：栈与队列02（用队列实现栈）

225. 用队列实现栈

力扣题目链接

使用队列实现栈的下列操作：

• push(x) – 元素 x 入栈
• pop() – 移除栈顶元素
• top() – 获取栈顶元素
• empty() – 返回栈是否为空

注意:

• 你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
• 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
• 你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

对于这题，首先要知道几个方法

• pop 栈尾出元素
• push 栈尾入元素
• peek 查看栈首元素
• offer 队尾入元素
• poll 队头出元素
• peek 查看队列元素

我用的是ArrayDeque模拟的。其实查看API这个类有很多重复的方法。
boolean add(E e)
将指定元素插入此双端队列的末尾。
void addFirst(E e)
将指定元素插入此双端队列的开头。
void addLast(E e)
将指定元素插入此双端队列的末尾。
void clear()
从此双端队列中移除所有元素。
ArrayDeque clone()
返回此双端队列的副本。
boolean contains(Object o)
如果此双端队列包含指定元素，则返回 true。
Iterator descendingIterator()
返回以逆向顺序在此双端队列的元素上进行迭代的迭代器。
E element()
获取，但不移除此双端队列所表示的队列的头。
E getFirst()
获取，但不移除此双端队列的第一个元素。
E getLast()
获取，但不移除此双端队列的最后一个元素。
boolean isEmpty()
如果此双端队列未包含任何元素，则返回 true。
Iterator iterator()
返回在此双端队列的元素上进行迭代的迭代器。
boolean offer(E e)
将指定元素插入此双端队列的末尾。
boolean offerFirst(E e)
将指定元素插入此双端队列的开头。
boolean offerLast(E e)
将指定元素插入此双端队列的末尾。
E peek()
获取，但不移除此双端队列所表示的队列的头；如果此双端队列为空，则返回 null。
E peekFirst()
获取，但不移除此双端队列的第一个元素；如果此双端队列为空，则返回 null。
E peekLast()
获取，但不移除此双端队列的最后一个元素；如果此双端队列为空，则返回 null。
E poll()
获取并移除此双端队列所表示的队列的头（换句话说，此双端队列的第一个元素）；如果此双端队列为空，则返回 null。
E pollFirst()
获取并移除此双端队列的第一个元素；如果此双端队列为空，则返回 null。
E pollLast()
获取并移除此双端队列的最后一个元素；如果此双端队列为空，则返回 null。
E pop()
从此双端队列所表示的堆栈中弹出一个元素。
void push(E e)
将元素推入此双端队列所表示的堆栈。
E remove()
获取并移除此双端队列所表示的队列的头。
boolean remove(Object o)
从此双端队列中移除指定元素的单个实例。
E removeFirst()
获取并移除此双端队列第一个元素。
boolean removeFirstOccurrence(Object o)
移除此双端队列中第一次出现的指定元素（当从头部到尾部遍历双端队列时）。
E removeLast()
获取并移除此双端队列的最后一个元素。
boolean removeLastOccurrence(Object o)
移除此双端队列中最后一次出现的指定元素（当从头部到尾部遍历双端队列时）。
int size()
返回此双端队列中的元素数。
Object[] toArray()
返回一个以恰当顺序包含此双端队列所有元素的数组（从第一个元素到最后一个元素）。
T[]
toArray(T[] a)
返回一个以恰当顺序包含此双端队列所有元素的数组（从第一个元素到最后一个元素）；返回数组的运行时类型是指定数组的运行时类型。

package com.programmercarl.stacks_queues;


import java.util.ArrayDeque;
/** * @ClassName MyStack * @Descriotion TODO * @Author nitaotao * @Date 2022/6/29 12:10 * @Version 1.0 * https://leetcode.cn/problems/implement-stack-using-queues/ * 225. 用队列实现栈 * 思路： * 栈 先进后出 只能A端进，A端出 * 队列 先进先出 只能A端进，B端出 * pop 栈尾出元素 * push 栈尾入元素 * peek 查看栈首元素 * * offer 队尾入元素 * poll 队头出元素 * peek 查看队列元素 * * **/
public class MyStack {
    
    //源队列
    private ArrayDeque queueOrigin;
    //复制队列
    private ArrayDeque queueCopy;
    public MyStack() {
    
        queueOrigin = new ArrayDeque();
        queueCopy = new ArrayDeque();
    }

    /** * 推入一个元素 * @param x */
    public void push(int x) {
    
        //源队列尾部推入数据
        queueOrigin.offer(x);
    }

    /** * 推出一个元素 * @return */
    public int pop() {
    
        /** * 源队列把除了 最后一个元素，其余所有元素推入复制队列 */
        int lenOrigin = queueOrigin.size();
        while (lenOrigin > 1) {
    
            queueCopy.offer(queueOrigin.poll());
            lenOrigin--;
        }
        //获取要推出的值
        int result = (int) queueOrigin.poll();
        /** * 复制队列再把所有元素推入原队列 */
        int lenCopy = queueCopy.size();
        while (lenCopy > 0) {
    
            queueOrigin.offer(queueCopy.poll());
            lenCopy--;
        }
        return result;
    }

    /** * 查看顶部元素 * @return */
    public int top() {
    
        /** * 源队列把除了 最后一个元素，其余所有元素推入复制队列 */
        int lenOrigin = queueOrigin.size();
        while (lenOrigin > 1) {
    
            queueCopy.offer(queueOrigin.poll());
            lenOrigin--;
        }
        //获取要推出的值
        int result = (int) queueOrigin.peek();
        queueCopy.offer(queueOrigin.poll());
        /** * 复制队列再把所有元素推入原队列 */
        int lenCopy = queueCopy.size();
        while (lenCopy > 0) {
    
            queueOrigin.offer(queueCopy.poll());
            lenCopy--;
        }
        return result;
    }

    /** * 判空 * @return */
    public boolean empty() {
    
        return queueOrigin.size() == 0;
    }
}

思路其实不太好想到，毕竟每次用元素都要重新把所有元素放到另一个地方 ，再取这个元素。这种低效率且属于脱裤子放屁的事现实中没必要这么用。代码不难，都有注释，自己看看就好了。