题目

思路

1.一种是用双端队列（Deque），直接就可以调用很多现成的方法，非常方便。

2.另一种是用普通的队列（Queue）,要实现栈的先入后出，可以将最后一个元素的前面所有元素出队，然后再重新入队到最后一个元素的后面，这样就实现了先入后出。

举例：入队是 1、2、3，出去我们要让3先出去，只能先让1、2出去，重新入队。这样才能让3先出去。

基础知识

queue的常用方法

Deque(双端队列)常用方法

Deque是一个双端队列接口，继承自Queue接口，Deque的实现类是LinkedList、ArrayDeque、LinkedBlockingDeque，其中LinkedList是最常用的。

补充：插入第一个元素还可以用push()方法。删除第一个元素还可以用pop()方法

//双端队列
import java.util.ArrayDeque;
import java.util.Deque;//leetcode submit region begin(Prohibit modification and deletion)
class MyStack {Deque<Integer> quel;public MyStack() {quel = new ArrayDeque<>();}public void push(int x) {quel.addLast(x);}public int pop() {return quel.removeLast();}public int top() {return quel.peekLast();}public boolean empty() {return quel.isEmpty();}
}

//使用一个普通队列
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;//leetcode submit region begin(Prohibit modification and deletion)
class MyStack {Queue<Integer> queue;public MyStack() {queue = new LinkedList<>();}public void push(int x) {queue.add(x);}public int pop() {int size = queue.size();while (size > 1) {queue.add(queue.poll());size--;}return queue.poll();}public int top() {int size = queue.size();while (size > 1) {queue.add(queue.poll());size--;}int res = queue.poll();queue.add(res);return res;}public boolean empty() {return queue.isEmpty();}
}