一文搞定栈与队列

栈与队列

基础入门

栈

常用操作

栈的实现

基于链表实现

基于数组实现

 队列

常用操作

队列的实现

基于链表实现

基于数组实现 

双向队列

常用操作

重点知识

栈与队列的区别

怎么用两个队列去实现栈

 两个栈实现一个队列

相关题解

leetcode20.有效的括号

法一：栈

leetcode155.最小栈

法一: 辅助栈

leetcode232.用栈实现队列

法一: 双栈

leetcode394.字符串解码

法一：辅助栈

法二: 递归

基础入门

栈

常用操作

        // 初始化栈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}
}

 队列

常用操作

        // 初始化队列，最大容量为 5ArrayQueue 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; // 队首指针初始化为 nullrear = null;  // 队尾指针初始化为 nullsize = 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; // 返回当前队列大小}
}

基于数组实现 

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;                  // 队首索引初始化为 0rear = -1;                  // 队尾索引初始化为 -1size = 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()); // 输出 2System.out.println("队尾元素: " + deque.peekRear());  // 输出 20// 元素出队System.out.println("从队头出队元素: " + deque.removeFront()); // 输出 2System.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();// 将最后一个元素移入 q2q2.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 中的所有元素移动到 stack2while (!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. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 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()};}}