Java栈和队列的快速入门
栈和队列
- 一、栈 Stack
- 1、概念
- 2、基本操作
- 3、常用方法
- 4、举例
- 5、分析
- 二、队列
- 1、概念
- 2、常用方法
- 3、举例
- 4、分析：
- 三、力扣算法快速入门
- 232. 用栈实现队列
- 225. 用队列实现栈
- 感谢
一、栈 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、peekFirst
Deque<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)【神装】的教学，本文大多搬运自此文。
感谢代码随想录的部分图文。