Java栈和队列的快速入门

一、栈 Stack

1、概念

在 Java 中，栈（Stack）是一种后进先出（LIFO）的数据结构，用于存储元素。在栈中，只有栈顶的元素是可见的和可访问的，其他元素都被隐藏起来，直到栈顶的元素被移除或弹出。Java 中的 java.util.Stack 类实现了这种栈的数据结构，并且是线程安全的，继承自 Vector 类。

压栈：栈的插入操作叫做进栈 / 压栈 / 入栈， 入数据在栈顶 。
出栈：栈的删除操作叫做出栈。 出数据在栈顶

2、基本操作

3、常用方法

方法	功能
Stack()	构造一个空的栈
E push(E e)	将e入栈，并返回
E pop()	将栈顶元素出栈并返回
E peek()	获取栈顶元素
int size()	获取栈中有效元素个数
boolean empty()	检测栈是否为空

4、举例

import java.util.Stack;public class StackExample {public static void main(String[] args) {Stack<String> stack = new Stack<>();// 压栈操作stack.push("Java");stack.push("Python");stack.push("C++");// 弹栈操作String topLanguage = stack.pop();System.out.println("弹出栈顶元素：" + topLanguage);// 查看栈顶元素String currentTop = stack.peek();System.out.println("当前栈顶元素：" + currentTop);// 判空操作if (stack.isEmpty()) {System.out.println("栈为空");} else {System.out.println("栈不为空");}}
}

5、分析

执行过程：

压栈操作：

stack.push("Java");：将 “Java” 压入栈中。
stack.push("Python");：将 “Python” 压入栈中。
stack.push("C++");：将 “C++” 压入栈中。

此时，栈中的元素从栈底到栈顶依次是：“Java” -> “Python” -> “C++”。

弹栈操作：

String topLanguage = stack.pop();：弹出栈顶元素 “C++”，并将其赋值给 topLanguage。
System.out.println("弹出栈顶元素：" + topLanguage);：打印出 “弹出栈顶元素：C++”。
此时，栈中的元素从栈底到栈顶依次是：“Java” -> “Python”。

查看栈顶元素：

String currentTop = stack.peek();：查看当前栈顶元素 “Python”，并将其赋值给 currentTop。
System.out.println("当前栈顶元素：" + currentTop);：打印出 “当前栈顶元素：Python”。

判空操作：

if (stack.isEmpty()) { ... } else { ... }：判断栈是否为空。
因为栈中还有 “Java” 和 “Python” 两个元素，所以 stack.isEmpty() 返回 false。
System.out.println("栈不为空");：打印出 “栈不为空”。

结果

弹出栈顶元素：C++
当前栈顶元素：Python
栈不为空

二、队列

1、概念

在 Java 中，队列（Queue）是一种先进先出（FIFO）的数据结构，用于存储元素。队列在 java.util 包中有多种实现，如 LinkedList、ArrayDeque 和 PriorityQueue。只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头（Head/Front）

2、常用方法

方法	功能
boolean offer(E e)	入队列
E poll()	将e入栈，并返回
E pop()	出队列
peek()	获取队头元素
int size()	获取队列中有效元素个数
boolean isEmpty()	检测队列是否为空

3、举例

注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。

public static void main(String[] args) {Queue<Integer> q = new LinkedList<>();q.offer(1);q.offer(2);q.offer(3);q.offer(4);q.offer(5); // 从队尾入队列System.out.println(q.size());System.out.println(q.peek()); // 获取队头元素q.poll();System.out.println(q.poll()); // 从队头出队列，并将删除的元素返回if(q.isEmpty()){System.out.println("队列空");}else{System.out.println(q.size());}
}

4、分析：

初始化队列并入队列：

Queue<Integer> q = new LinkedList<>();
q.offer(1);
q.offer(2);
q.offer(3);
q.offer(4);
q.offer(5); // 从队尾入队列

此时，队列中的元素从队头到队尾依次是：1 -> 2 -> 3 -> 4 -> 5。

获取队列的大小：

System.out.println(q.size());

队列中有 5 个元素，所以输出结果是：

5

获取队头元素：

System.out.println(q.peek()); // 获取队头元素

队头元素是 1，所以输出结果是：

1

从队头出队列：

q.poll();

从队头删除元素 1，此时队列中的元素从队头到队尾依次是：2 -> 3 -> 4 -> 5。

再次从队头出队列，并返回删除的元素：

System.out.println(q.poll());

从队头删除元素 2，并返回这个元素，所以输出结果是：

2

检查队列是否为空，并输出队列的大小：

if(q.isEmpty()){System.out.println("队列空");
}else{System.out.println(q.size());
}

此时队列中有 3 个元素（3, 4, 5），所以 q.isEmpty() 返回 false，输出队列的大小：

3

综上所述，代码的输出结果是：

5
1
2
3

三、力扣算法快速入门

232. 用栈实现队列

力扣题
图解：

代码：

class MyQueue {Stack<Integer> stackIn;Stack<Integer> stackOut;/** 初始化两个栈 stackIn 和 stackOut。stackIn 用于存放入队的元素，stackOut 用于存放出队的元素。 */public MyQueue() {stackIn = new Stack<>(); // 负责进栈stackOut = new Stack<>(); // 负责出栈}/**将元素 x 压入 stackIn 栈中。由于栈是先进后出的，所以 stackIn 中的元素顺序与队列的入队顺序一致 */public void push(int x) {stackIn.push(x);}/** 从队列的头部移除并返回元素。首先调用 dumpstackIn() 方法将 stackIn 中的所有元素转移到 stackOut 中（如果 stackOut 为空），然后从 stackOut 中弹出栈顶元素，这个元素就是队列的头部。 */public int pop() {    dumpstackIn();return stackOut.pop();}/** 返回队列的头部元素，但不移除它。首先调用 dumpstackIn() 方法确保 stackOut 中有元素，然后返回 stackOut 的栈顶元素。*/public int peek() {dumpstackIn();return stackOut.peek();}/** 检查队列是否为空。队列为空的条件是 stackIn 和 stackOut 都为空。 */public boolean empty() {return stackIn.isEmpty() && stackOut.isEmpty();}// 如果stackOut为空，那么将stackIn中的元素全部放到stackOut中private void dumpstackIn(){if (!stackOut.isEmpty()) return; while (!stackIn.isEmpty()){stackOut.push(stackIn.pop());}}
}

225. 用队列实现栈

力扣题

使用一个队列：

class MyStack {Queue<Integer> queue1; // 和栈中保持一样元素的队列Queue<Integer> queue2; // 辅助队列/** Initialize your data structure here. */public MyStack() {queue1 = new LinkedList<>();queue2 = new LinkedList<>();}/** Push element x onto stack. */public void push(int x) {queue2.offer(x); // 先放在辅助队列中while (!queue1.isEmpty()){queue2.offer(queue1.poll());}Queue<Integer> queueTemp;queueTemp = queue1;queue1 = queue2;queue2 = queueTemp; // 最后交换queue1和queue2，将元素都放到queue1中}/** Removes the element on top of the stack and returns that element. */public int pop() {return queue1.poll(); // 因为queue1中的元素和栈中的保持一致，所以这个和下面两个的操作只看queue1即可}/** Get the top element. */public int top() {return queue1.peek();}/** Returns whether the stack is empty. */public boolean empty() {return queue1.isEmpty();}
}

使用两个队列：

class MyStack {// Deque 接口继承了 Queue 接口// 所以 Queue 中的 add、poll、peek等效于 Deque 中的 addLast、pollFirst、peekFirstDeque<Integer> que1; // 和栈中保持一样元素的队列Deque<Integer> que2; // 辅助队列/** Initialize your data structure here. */public MyStack() {que1 = new ArrayDeque<>();que2 = new ArrayDeque<>();}/** Push element x onto stack. */public void push(int x) {que1.addLast(x);}/** Removes the element on top of the stack and returns that element. */public int pop() {int size = que1.size();size--;// 将 que1 导入 que2 ，但留下最后一个值while (size-- > 0) {que2.addLast(que1.peekFirst());que1.pollFirst();}int res = que1.pollFirst();// 将 que2 对象的引用赋给了 que1 ，此时 que1，que2 指向同一个队列que1 = que2;// 如果直接操作 que2，que1 也会受到影响，所以为 que2 分配一个新的空间que2 = new ArrayDeque<>();return res;}/** Get the top element. */public int top() {return que1.peekLast();}/** Returns whether the stack is empty. */public boolean empty() {return que1.isEmpty();}
}

感谢

感谢大佬Java 【数据结构】 栈(Stack)和队列(Queue)【神装】的教学，本文大多搬运自此文。
感谢代码随想录的部分图文。