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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

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