栈与队列
基础入门
栈
常用操作
// 初始化栈
Stack stack = new Stack();
// 入栈操作
stack.push(10);
stack.push(20);
stack.push(30);
// 访问栈顶元素
System.out.println("栈顶元素: " + stack.peek()); // 输出 30
// 出栈操作
System.out.println("出栈元素: " + stack.pop()); // 输出 30
// 获取栈的长度
System.out.println("栈的长度: " + stack.size()); // 输出 2
// 判断栈是否为空
System.out.println("栈是否为空: " + stack.isEmpty()); // 输出 false栈的实现
基于链表实现
将链表的头节点视为栈顶，尾节点视为栈底
class Stack {
private ArrayList<Integer> items;
public Stack() {
items = new ArrayList<>();
}
public boolean isEmpty() {
"""检查栈是否为空"""
return items.isEmpty();
}
public void push(int item) {
"""入栈操作"""
items.add(item);
}
public int pop() {
"""出栈操作"""
if (isEmpty()) {
throw new IndexOutOfBoundsException("pop from an empty stack");
}
return items.remove(items.size() - 1);
}
public int peek() {
"""查看栈顶元素"""
if (isEmpty()) {
throw new IndexOutOfBoundsException("peek from an empty stack");
}
return items.get(items.size() - 1);
}
public int size() {
"""返回栈的大小"""
return items.size();
}
}
基于数组实现
将数组的尾部作为栈顶class ArrayStack {
private int[] stack; // 存储栈元素的数组
private int top; // 栈顶索引
private int capacity; // 栈的最大容量
// 构造函数，初始化栈
public ArrayStack(int capacity) {
this.capacity = capacity; // 设置栈的最大容量
stack = new int[capacity]; // 创建数组
top = -1; // 初始化栈顶索引为 -1，表示栈为空
}
// 检查栈是否为空
public boolean isEmpty() {
return top == -1;
}
// 检查栈是否已满
public boolean isFull() {
return top == capacity - 1;
}
// 入栈操作
public void push(int item) {
if (isFull()) {
throw new StackOverflowError("栈已满，无法入栈");
}
stack[++top] = item; // 将元素放入栈顶并更新栈顶索引
}
// 出栈操作
public int pop() {
if (isEmpty()) {
throw new IndexOutOfBoundsException("无法从空栈中出栈");
}
return stack[top--]; // 返回栈顶元素并更新栈顶索引
}
// 查看栈顶元素
public int peek() {
if (isEmpty()) {
throw new IndexOutOfBoundsException("无法查看空栈的栈顶元素");
}
return stack[top]; // 返回栈顶元素
}
// 获取栈的长度
public int size() {
return top + 1; // 栈的大小是栈顶索引 + 1
}
}队列
常用操作
// 初始化队列，最大容量为 5
ArrayQueue queue = new ArrayQueue(5);
// 元素入队
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
// 访问队首元素
System.out.println("队首元素: " + queue.peek()); // 输出 10
// 元素出队
System.out.println("出队元素: " + queue.dequeue()); // 输出 10
// 获取队列的长度
System.out.println("队列的长度: " + queue.size()); // 输出 2
// 判断队列是否为空
System.out.println("队列是否为空: " + queue.isEmpty()); // 输出 false队列的实现
基于链表实现
将链表的“头节点”和“尾节点”分别视为“队首”和“队尾”，规定队尾仅可添加 节点，队首仅可删除节点。class LinkedListQueue {
private Node front; // 队首指针
private Node rear; // 队尾指针
private int size; // 当前队列大小
// 构造函数，初始化队列
public LinkedListQueue() {
front = null; // 队首指针初始化为 null
rear = null; // 队尾指针初始化为 null
size = 0; // 当前队列大小初始化为 0
}
// 判断队列是否为空
public boolean isEmpty() {
return size == 0;
}
// 元素入队
public void enqueue(int item) {
Node newNode = new Node(item); // 创建新节点
if (isEmpty()) {
front = newNode; // 如果队列为空，front 和 rear 都指向新节点
} else {
rear.next = newNode; // 将当前队尾的 next 指向新节点
}
rear = newNode; // 更新队尾指针为新节点
size++; // 更新当前队列大小
}
// 访问队首元素
public int peek() {
if (isEmpty()) {
throw new IllegalStateException("无法查看空队列的队首元素");
}
return front.data; // 返回队首元素
}
// 元素出队
public int dequeue() {
if (isEmpty()) {
throw new IllegalStateException("无法从空队列中出队");
}
int item = front.data; // 获取队首元素
front = front.next; // 更新队首指针
size--; // 更新当前队列大小
if (isEmpty()) {
rear = null; // 如果队列为空，队尾指针也设置为 null
}
return item; // 返回出队元素
}
// 获取队列的长度
public int size() {
return size; // 返回当前队列大小
}
}基于数组实现
使用一个变量 front 指向队首元素的索引，并维护一个变量 size 用于记录队列长度。定义 rear = front + size ，这个公式计算出的 rear 指向队尾元素之后的下一个位置。class ArrayQueue {
private int[] queue; // 存储队列元素的数组
private int front; // 队首索引
private int rear; // 队尾索引
private int capacity; // 队列的最大容量
private int size; // 当前队列的大小
// 构造函数，初始化队列
public ArrayQueue(int capacity) {
this.capacity = capacity; // 设置队列的最大容量
queue = new int[capacity]; // 创建数组
front = 0; // 队首索引初始化为 0
rear = -1; // 队尾索引初始化为 -1
size = 0; // 当前队列大小初始化为 0
}
// 判断队列是否为空
public boolean isEmpty() {
return size == 0;
}
// 判断队列是否已满
public boolean isFull() {
return size == capacity;
}
// 元素入队
public void enqueue(int item) {
if (isFull()) {
throw new IllegalStateException("队列已满，无法入队");
}
rear = (rear + 1) % capacity; // 循环队列的方式更新队尾索引
queue[rear] = item; // 将元素放入队尾
size++; // 更新当前队列大小
}
// 访问队首元素
public int peek() {
if (isEmpty()) {
throw new IllegalStateException("无法查看空队列的队首元素");
}
return queue[front]; // 返回队首元素
}
// 元素出队
public int dequeue() {
if (isEmpty()) {
throw new IllegalStateException("无法从空队列中出队");
}
int item = queue[front]; // 获取队首元素
front = (front + 1) % capacity; // 循环队列的方式更新队首索引
size--; // 更新当前队列大小
return item; // 返回出队元素
}
// 获取队列的长度
public int size() {
return size; // 返回当前队列大小
}
}双向队列
常用操作
// 初始化双向队列
Deque deque = new Deque();
// 元素入队
deque.addRear(10);
deque.addRear(20);
deque.addFront(5);
deque.addFront(2);
// 访问队首和队尾元素
System.out.println("队首元素: " + deque.peekFront()); // 输出 2
System.out.println("队尾元素: " + deque.peekRear()); // 输出 20
// 元素出队
System.out.println("从队头出队元素: " + deque.removeFront()); // 输出 2
System.out.println("从队尾出队元素: " + deque.removeRear()); // 输出 20
// 获取队列的长度
System.out.println("当前队列的长度: " + deque.size()); // 输出 2双向队列的实现也是和实现队列类似的思想，但是入队和出队都有两个方向了。
重点知识
栈与队列的区别
插入与删除操作:栈只能在顶部进行插入和删除操作，而队列允许在两端进行操作，即在队尾插入元素，在队头删除元素。
顺序:栈中元素的顺序是后进先出，而队列中元素的顺序是先进先出。
使用场景:栈常用于需要反向操作的场景，而队列常用于需要按照添加顺序处理元素的场景。
怎么用两个队列去实现栈
保持一个队列为空，另一个队列用于模拟栈的操作。
class StackUsingTwoQueues {
private Queue<Integer> q1;
private Queue<Integer> q2;
// 构造函数，初始化两个队列
public StackUsingTwoQueues() {
q1 = new LinkedList<>();
q2 = new LinkedList<>();
}
// 入栈操作
public void push(int item) {
q1.add(item); // 将新元素入队到队列 q1
}
// 出栈操作
public int pop() {
if (q1.isEmpty()) {
throw new IllegalStateException("栈为空，无法出栈");
}
// 将 q1 中的元素全部出队到 q2，保留最后一个（即栈顶元素）
while (q1.size() > 1) {
q2.add(q1.remove());
}
// 此时 q1 中只剩下栈顶元素, 移除并保存它
int top = q1.remove();
// 交换 q1 和 q2 的角色
Queue<Integer> temp = q1;
q1 = q2;
q2 = temp;
return top; // 返回栈顶元素
}
// 查看栈顶元素
public int peek() {
if (q1.isEmpty()) {
throw new IllegalStateException("栈为空，无法查看栈顶元素");
}
// 将 q1 中的元素全部出队到 q2，保留最后一个（即栈顶元素）
while (q1.size() > 1) {
q2.add(q1.remove());
}
// 获取栈顶元素
int top = q1.peek();
// 将最后一个元素移入 q2
q2.add(q1.remove());
// 交换 q1 和 q2 的角色
Queue<Integer> temp = q1;
q1 = q2;
q2 = temp;
return top; // 返回栈顶元素
}
// 判断栈是否为空
public boolean isEmpty() {
return q1.isEmpty();
}
// 获取栈的大小
public int size() {
return q1.size();
}
}两个栈实现一个队列
1.一个栈用于入队操作，另一个栈用于出队操作。
2.当需要入队时，直接将元素压入入队栈。
当需要出队时，如果出队栈不为空，直接从出队栈弹出元素;如果出队栈为空，将入队栈中的元素依次弹出并。3.压入出队栈，然后再从出队栈中弹出元素。
class QueueUsingTwoStacks {
private Stack<Integer> stack1; // 用于入队操作的栈
private Stack<Integer> stack2; // 用于出队操作的栈
// 构造函数，初始化两个栈
public QueueUsingTwoStacks() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
// 元素入队
public void enqueue(int item) {
stack1.push(item); // 直接将元素推入 stack1
}
// 元素出队
public int dequeue() {
if (stack2.isEmpty()) {
if (stack1.isEmpty()) {
throw new IllegalStateException("队列为空，无法出队");
}
// 将 stack1 中的所有元素移动到 stack2
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop(); // 从 stack2 中弹出最先入队的元素
}
// 查看队首元素
public int peek() {
if (stack2.isEmpty()) {
if (stack1.isEmpty()) {
throw new IllegalStateException("队列为空，无法查看队首元素");
}
// 确保队首元素在 stack2 中
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.peek(); // 查看 stack2 的栈顶元素
}
// 判断队列是否为空
public boolean isEmpty() {
return stack1.isEmpty() && stack2.isEmpty();
}
// 获取队列的大小
public int size() {
return stack1.size() + stack2.size();
}
}相关题解
leetcode20.有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([])"
输出：true
法一：栈
// 方法01类，用于验证括号字符串的有效性
public class Method01 {
// 判断给定字符串s中的括号是否有效
public boolean isValid(String s) {
int n = s.length();
if (n % 2 == 1) {
return false;
}
// 保存括号对应关系的映射
Map<Character, Character> map = new HashMap<Character, Character>() {{
put(')', '(');
put(']', '[');
put('}', '{');
}};
Stack<Character> stack = new Stack<>();
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
if(!map.containsKey(c)){
stack.push(c);
}else{
if(stack.isEmpty() || stack.peek()!=map.get(c) ) {
return false;
}
stack.pop();
}
}
return stack.isEmpty();
}
}
leetcode155.最小栈
法一: 辅助栈
// 最小栈类，提供基本的栈操作以及获取最小值的功能
public class MinStack {
private Stack<Integer> stack; // 存储栈元素的栈
private Stack<Integer> minStack; // 存储当前最小值的栈
// 构造函数，初始化栈和最小值栈
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
minStack.push(Integer.MAX_VALUE);
}
// 向栈中添加元素，并更新最小值栈
public void push(int val) {
stack.push(val);
if (val < minStack.peek()) {
minStack.push(val);
} else {
minStack.push(minStack.peek());
}
}
// 移除栈顶元素，并同步更新最小值栈
public void pop() {
stack.pop();
minStack.pop();
}
// 获取栈顶元素
public int top() {
return stack.peek();
}
// 获取当前最小值
public int getMin() {
return minStack.peek();
}
}
leetcode232.用栈实现队列
法一: 双栈
// 定义一个队列类 MyQueue
public class MyQueue {
private Stack<Integer> inputStack; // 输入栈
private Stack<Integer> outputStack; // 输出栈
// 构造函数，初始化输入栈和输出栈
public MyQueue() {
inputStack = new Stack<>();
outputStack = new Stack<>();
}
// 将元素 x 推入队列中
public void push(int x) {
inputStack.push(x);
}
// 移除并返回队列的首元素
public int pop() {
if (outputStack.isEmpty()) {
while (!inputStack.isEmpty()) {
outputStack.push(inputStack.pop());
}
} else {
return outputStack.pop();
}
return outputStack.pop();
}
// 返回队列的首元素但不移除它
public int peek() {
if (outputStack.isEmpty()) {
while (!inputStack.isEmpty()) {
outputStack.push(inputStack.pop());
}
} else {
return outputStack.peek();
}
return outputStack.peek();
}
// 检查队列是否为空
public boolean empty() {
if (inputStack.isEmpty() && outputStack.isEmpty()) {
return true;
} else {
return false;
}
}
}
leetcode394.字符串解码
法一：辅助栈
// 该类包含解码字符串的方法
public class Method01 {
// 解码字符串的方法，根据特定格式进行解析
public String decodeString(String s) {
int num = 0;
StringBuilder sb = new StringBuilder();
Stack<String> stack_str= new Stack<>();
Stack<Integer> stack_num = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '[') {
stack_str.push(sb.toString());
stack_num.push(num);
sb = new StringBuilder();
num = 0;
} else if (c == ']') {
StringBuilder temp = new StringBuilder();
int count = stack_num.pop();
for (int i = 0; i < count; i++) {
temp.append(sb);
}
sb = new StringBuilder(stack_str.pop()+temp.toString());
} else if (c >= '0' && c <= '9') {
num = num * 10 + Integer.parseInt(c + "");
} else {
sb.append(c);
}
}
return sb.toString();
}
}
法二: 递归
// 定义一个用于解码字符串的类
public class Method02 {
// 解码字符串的方法，接收一个字符串并返回解码后的结果
public String decodeString(String s) {
return dfs(s, 0)[0];
}
// 深度优先搜索辅助方法，处理具体的解码逻辑
private String[] dfs(String s, int index) {
StringBuilder sb = new StringBuilder();
int beishu = 0;
while (index < s.length()) {
char c = s.charAt(index);
if (c >= '0' && c <= '9') {
beishu = beishu * 10 + Integer.parseInt(String.valueOf(c));
} else if (c == '[') {
String temp[] =dfs(s, index + 1);
index = Integer.parseInt(temp[1]);
while (beishu > 0){
sb.append(temp[0]);
beishu--;
}
} else if (c == ']') {
return new String[]{sb.toString(), String.valueOf(index)};
} else {
sb.append(c);
}
index++;
}
return new String[]{sb.toString()};
}
}