当前位置：首页 > ops >正文

【算法训练营Day09】栈与队列part1

ops 2025/7/15 2:13:31

文章目录

Java相关理论基础
用栈实现队列
用队列实现栈
有效的括号
删除字符串中的所有相邻重复项

Java相关理论基础

对于栈：在java中有直接对应的实现类Stack，但是已经过时，效率较低使用synchronized上锁保证线程安全。所以一般使用ArrayDeque或LinkedList来代替，对应的接口方法：
- push
- pop
- peak
- isEmpty
对于队列：在java中也可以使用LinkedList、ArrayDeque来实现，对应的接口方法有（返回特殊值就是操作失败时会返回 null 或者 false）：
在 Java 里，Deque是一个接口，其全称为 “Double Ended Queue”，也就是双端队列。它继承自Queue接口，支持在队列的两端（头部和尾部）进行元素的插入、删除和获取操作。与普通队列（遵循 FIFO 原则）不同，双端队列对元素的插入和删除没有位置限制，使用起来更加灵活。Deque接口常见的实现类有ArrayDeque和LinkedList。ArrayDeque基于动态数组实现，而LinkedList基于链表实现。
一句话说java中栈与队列都可以使用双端队列来实现

用栈实现队列

题目链接：232. 用栈实现队列

解题思路：

初始化两个栈
其中一个栈1，专门用来实现队列的进
另外一个栈2，用来实现队列的出
队列的进操作与判空只与栈1有关
而只要涉及到出队，返回队头元素操作，则将栈1全部弹出塞到栈2中，再对栈2进行对应的操作。执行完之后再全部弹回栈1

代码如下：

class MyQueue {private Deque<Integer> addDeque;private Deque<Integer> resultDeque;public MyQueue() {addDeque = new ArrayDeque();resultDeque = new ArrayDeque();}public void push(int x) {addDeque.push(x);}public int pop() {while(!addDeque.isEmpty()) resultDeque.push(addDeque.pop());int result = resultDeque.pop();while(!resultDeque.isEmpty()) addDeque.push(resultDeque.pop());return result;}public int peek() {while(!addDeque.isEmpty()) resultDeque.push(addDeque.pop());int result = resultDeque.peek();while(!resultDeque.isEmpty()) addDeque.push(resultDeque.pop());return result;}public boolean empty() {return addDeque.isEmpty();}
}

用队列实现栈

题目链接：225. 用队列实现栈

解题思路；

使用两个队列1、2来实现栈
添加元素直接往队列1中添加就行
而返回栈顶元素以及弹出栈顶元素操作的核心就在于控制队列1中唯一剩余的元素就是栈顶元素，其他的元素全部按顺序塞到队列2中去，完成对应操作之后再还原到队列1中

代码如下：

class MyStack {private Deque<Integer> addDeque;private Deque<Integer> resultDeque;public MyStack() {addDeque = new ArrayDeque();resultDeque = new ArrayDeque();}public void push(int x) {addDeque.add(x);}public int pop() {int count = 0;int bar = addDeque.size();while(!addDeque.isEmpty() && count++ !=  bar - 1) resultDeque.add(addDeque.remove());int result = addDeque.remove();while(!resultDeque.isEmpty()) addDeque.add(resultDeque.remove());return result;}public int top() {int count = 0;int bar = addDeque.size();while(!addDeque.isEmpty() && count++ !=  bar - 1) resultDeque.add(addDeque.remove());int result = addDeque.element();resultDeque.add(addDeque.remove());while(!resultDeque.isEmpty()) addDeque.add(resultDeque.remove());return result;}public boolean empty() {return addDeque.isEmpty();}
}

有效的括号

题目链接：20. 有效的括号

解题思路：

遍历字符串
将所有的左符号加入到栈中
如果遇到右括号，则查看栈顶元素
如果对应则弹出来，不对应则直接返回false
遍历完之后如果栈中为空则返回true
如果栈中仍有元素，则返回false

代码如下：

class Solution {public boolean isValid(String s) {Deque<Character> box = new ArrayDeque<>();for(int i = 0;i < s.length();i++) {char temp = s.charAt(i);if(temp == '(' || temp == '{' || temp == '[') box.push(temp);else if (box.isEmpty()) return false;else if (temp == ')') if(box.peek() == '(') box.pop();else return false;else if (temp == '}') if(box.peek() == '{') box.pop();else return false;else if (temp == ']') if(box.peek() == '[') box.pop();else return false;}return box.isEmpty();}
}

删除字符串中的所有相邻重复项

题目链接：1047. 删除字符串中的所有相邻重复项

解题逻辑：

遍历字符串，并尝试将字符添加到栈中
在将字符加入到栈中之前，先判断此时的栈顶元素是否与添加元素相同
如果相同则将栈顶元素弹出，并且该元素不添加
如果不同则将该元素添加到栈中
最后使用双端队列的特性将队尾元素一一拿出拼接得到最终答案

class Solution {public String removeDuplicates(String s) {Deque<Character> box = new ArrayDeque<>();for(int i = 0;i < s.length();i++) {char temp = s.charAt(i);if(!box.isEmpty() && temp == box.peek()) box.pop();else box.push(temp);}StringBuilder result = new StringBuilder();while (!box.isEmpty()) {result.append(box.pollLast());}return result.toString();}
}