? ? ? ? 自己做了一遍，不熟悉Java自带的Stack，自己用链表，和虚拟栈顶指针解决了，思路就是用两个栈：一个in栈（负责模拟入队），一个out栈（负责模拟出队，需要把in栈里的数据先进入out栈中，在出栈）。关键在于当out栈为空时，就把in栈里的全部元素加入到out栈中去，不为空则什么也不干，这里我封装了一个setTopOut方法（也是代码随想录里提到的“抽象出一个方法”），负责判断：当out栈为空时，将in栈的全部元素入栈到out栈中。
class MyQueue {
Node topIn;
Node topOut;
public MyQueue() { // 定义一个入栈(in)的栈顶和出栈(out)的栈顶
topIn = new Node(-1);
topOut = new Node(-1);
}
public void push(int x) {
Node p = new Node(x);
p.next = topIn.next;
topIn.next = p;
}
public int pop() {
setTopOut();
// 经过setTopOut方法之后，out栈一定有元素可出，除非输入数据无效
Node p = topOut.next;
topOut.next = topOut.next.next;
return p.val;
}
public int peek() {
setTopOut();
// 返回out栈顶元素值即可
return topOut.next.val;
}
public boolean empty() {
if(topOut.next == null && topIn.next == null){
return true;
}else{
return false;
}
}
class Node {
int val;
Node next;
public Node(int val) {
this.val = val;
}
}
public void setTopOut(){
if(topOut.next == null) {// 如果出栈为空，那么，应该先让入栈里的所有元素进入到出栈当中去
while(topIn.next != null){
Node p = topIn.next;
topIn.next = topIn.next.next; // 入栈中元素出栈
p.next = topOut.next; // 进入到 出栈 中
topOut.next = p;
}
}
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/
push(E e): 将元素压入栈顶。pop(): 移除并返回栈顶的元素。如果栈为空，则抛出EmptyStackException。peek(): 返回栈顶元素，但不移除它。如果栈为空，则返回null。empty(): 判断栈是否为空。size(): 返回栈中元素的数量。clear(): 清空栈中的所有元素。
import java.util.Stack;
public class StackDemo {
public static void main(String[] args) {
// 创建一个新的栈
Stack<Integer> stack = new Stack<>();
// 使用push方法添加元素到栈中
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
// 输出栈的大小
System.out.println("Stack size: " + stack.size()); // 输出: Stack size: 5
// 使用pop方法移除并返回栈顶的元素
System.out.println("Popped element: " + stack.pop()); // 输出: Popped element: 5
// 使用peek方法查看栈顶元素，但不移除它
System.out.println("Top element: " + stack.peek()); // 输出: Top element: 4
// 使用clear方法清空栈
stack.clear();
System.out.println("Stack size after clear: " + stack.size()); // 输出: Stack size after clear: 0
}
}? ? ? ? 自己尝试用一个队列Queue实现栈的操作，就是在入队时，让size - 1个数出队后再入队，这样就能保证后进队的数，出现在队头，后续的操作正常调用Queue的方法即可。
class MyStack {
Queue<Integer> queue;
public MyStack() {
queue = new LinkedList<>();
}
public void push(int x) {// 用一个Queue实现栈，需要在入队的时候，每进入一个就把size-1个数出队入队，这样，后进队的，将会在对首
queue.add(x);
setQueue(); // setQueue是自己封装的一个方法，实现“出队进队”，让后进来的数字始终在对首
}
public int pop() {
return queue.remove(); // 再次出队则是原先最后一个元素，即满足“后进先出”
}
public int top() {
return queue.peek();
}
public boolean empty() {
if(queue.isEmpty()){
return true;
}else{
return false;
}
}
public void setQueue(){
if(!queue.isEmpty()){
for(int i = 0; i < queue.size() - 1; i++) { // 循环size-1次，即，把队列里的size-1个出队入队
int temp = queue.remove();
queue.add(temp);
check = true;
}
}
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/看到代码随想录里有用到Deque（双端队列），还有Queue，下面总结一下Java内部实现的这两种数据结构：
add(E e): 将元素添加到队列的末尾。remove(): 移除并返回队列的头部元素。如果队列为空，则抛出NoSuchElementException。element(): 返回队列的头部元素，但不移除它。如果队列为空，则返回null。peek(): 与element()方法相同，返回队列的头部元素，但不移除它。如果队列为空，则返回null。size(): 返回队列中元素的数量。isEmpty(): 判断队列是否为空。clear(): 清空队列中的所有元素。
import java.util.Queue;
import java.util.LinkedList;
public class QueueDemo {
public static void main(String[] args) {
// 创建一个新的队列
Queue<Integer> queue = new LinkedList<>();
// 使用add方法添加元素到队列中
queue.add(1);
queue.add(2);
queue.add(3);
queue.add(4);
queue.add(5);
// 输出队列的大小
System.out.println("Queue size: " + queue.size()); // 输出: Queue size: 5
// 使用remove方法移除并返回队列的头部元素
System.out.println("Removed element: " + queue.remove()); // 输出: Removed element: 1
// 使用element方法查看队列的头部元素，但不移除它
System.out.println("Head element: " + queue.element()); // 输出: Head element: 2
// 使用peek方法查看队列的头部元素，但不移除它
System.out.println("Peeked element: " + queue.peek()); // 输出: Peeked element: 2
// 使用clear方法清空队列
queue.clear();
System.out.println("Queue size after clear: " + queue.size()); // 输出: Queue size after clear: 0
}
}?注意：?Queue?是个接口，在实例化时必须实例化?LinkedList?的对象，因为?LinkedList?实现了?Queue?接口。即，创建时，必须用??new LinkedList<>();
addFirst(E e): 在队列的头部添加一个元素。addLast(E e): 在队列的尾部添加一个元素。removeFirst(): 移除并返回队列的头部元素。如果队列为空，则抛出NoSuchElementException。removeLast(): 移除并返回队列的尾部元素。如果队列为空，则抛出NoSuchElementException。getFirst(): 返回队列的头部元素，但不移除它。如果队列为空，则返回null。getLast(): 返回队列的尾部元素，但不移除它。如果队列为空，则返回null。peekFirst(): 与getFirst()方法相同，返回队列的头部元素，但不移除它。如果队列为空，则返回null。peekLast(): 与getLast()方法相同，返回队列的尾部元素，但不移除它。如果队列为空，则返回null。size(): 返回队列中元素的数量。isEmpty(): 判断队列是否为空。clear(): 清空队列中的所有元素。
import java.util.Deque;
import java.util.LinkedList;
public class DequeDemo {
public static void main(String[] args) {
// 创建一个新的双端队列
Deque<Integer> deque = new LinkedList<>();
// 使用addFirst方法在队列头部添加元素
deque.addFirst(1);
deque.addFirst(2);
deque.addFirst(3);
// 使用addLast方法在队列尾部添加元素
deque.addLast(4);
deque.addLast(5);
deque.addLast(6);
// 输出队列的大小
System.out.println("Deque size: " + deque.size()); // 输出: Deque size: 6
// 使用removeFirst方法移除并返回队列头部的元素
System.out.println("Removed first element: " + deque.removeFirst()); // 输出: Removed first element: 3
// 使用getFirst方法获取队列头部的元素（不移除）
System.out.println("First element: " + deque.getFirst()); // 输出: First element: 2
// 使用removeLast方法移除并返回队列尾部的元素
System.out.println("Removed last element: " + deque.removeLast()); // 输出: Removed last element: 6
// 使用getLast方法获取队列尾部的元素（不移除）
System.out.println("Last element: " + deque.getLast()); // 输出: Last element: 5
}
}?注意：同样，Deque是继承至Queue的一个接口，所以在创建对象时，也必须用
new LinkedList<>();
- push(E e)：在栈顶添加一个元素。在Deque中相当于
addFirst(E e)。- pop()：移除并返回栈顶元素。在Deque中相当于
removeFirst()。- peek()：返回栈顶元素，但不移除它。在Deque中相当于
getFirst()。
- add(E e)：在队列的尾部添加一个元素。相当于Deque的
addLast(E e)方法。- remove()：移除并返回队列的头部元素。如果队列为空，则抛出NoSuchElementException。相当于Deque的
removeFirst()方法。- element()：返回队列的头部元素，但不移除它。如果队列为空，则返回null。相当于Deque的
getFirst()方法。- peek()：返回队列的头部元素，但不移除它。如果队列为空，则返回null。相当于Deque的
peekFirst()方法。
所以，有的时候，想要用双端队列实现栈或者队列的一些操作时，可以直接调用同名方法，使得代码更容易理解。