- 232.用栈实现队列
-
- 用队列实现栈
-
- 有效的括号
-
- 删除字符串中的所有相邻重复项
-
- 逆波兰表达式求值
解决栈和队列的基本数据结构
Queue(队列)
在java中是一个接口。定义的方法:
//boolean add(E e): 将指定的元素插入此队列(如果立即可行且不会违反容量限制),在成功时返回 true,如果当前没有可用的空间,则抛出 IllegalStateException。
//E remove():获取并移除 此队列的 头 。
//E element() :获取 ,但是不移除此队列的 头 。//boolean offer(E e):将指定的元素 插入 此队列(如果立即可行且不会违反容量限制),当使用有容量限制的队列时,此方法通常要优于 add(E),后者可能无法插入元素,而只是抛出一个异常。
//E poll():获取并移除 此队列的头,如果此队列为空,则返回 null。
//E peek(): 获取但不移除此队列的头;如果此队列为空,则返回 null。
在极端情况下,两组API的表现不一致。极端情况指的是 一组是抛异常,一组是返回特殊值
- 插入的时候,队列满了
- 删除或者获取的时候,队列空了。
Deque
是个Queue的子接口,是java里面的双端队列。
Deque特点:
- Deque是Queue的子接口
- 数据结构表现:队列,栈,双端队列
- 存储元素有序
- 可存储重复元素
- 不能存储null(LinkedList除外)
Deque可以说非常的万能,能模拟很多数据结构,下面就是他能模拟的数据结构。
// ------------- 作为Queue的
// E peek(): 获取队头元素,但不移除它
// E poll():从队头移除元素
// boolean offer(E e): 添加一个元素到 队尾// ------------- 作为Stack的
// E pop(): 从此列表所表示的堆栈处弹出一个元素。
// void push(E e): 将元素推入此列表所表示的堆栈。// ------------- 作为双端队列
// boolean offerFirst(E e): 从 第一个位置 插入 指定元素
// boolean offerLast(E e): 从 最后一个位置 插入 指定元素
// E peekFirst(): 获取 但是不移除 第一个元素,如果列表为空,返回null
// E peekLast(): 获取 但是不移除 最后一个元素,如果列表为空,返回null
// E pollFirst(): 从 第一个位置 移除 元素
// E pollLast(): 从 最后一个位置 移除 元素,如果列表为空,返回null// -------------- 作为普通List的
// boolean add(E e):将指定元素添加到此列表的结尾。
// E remove():获取并移除此列表的头(第一个元素)。// void addFirst(E e): 将指定元素插入此列表的开头。
// void addLast(E e): 将指定元素添加到此列表的结尾。
// E getFirst(): 返回此列表的第一个元素。
// E getLast(): 返回此列表的最后一个元素。
// E removeFirst(): 移除并返回此列表的第一个元素。
// E removeLast(): 移除并返回此列表的最后一个元素。// 这个API,大家觉得应不应该出现在Deque这个接口里面。
// boolean removeFirstOccurrence(Object o): 从此列表中移除第一次出现的指定元素
// boolean removeLastOccurrence(Object o): 从列表中移除最后一次出现的指定元素
// Iterator<E> descendingIterator():获取一个倒序的迭代器
// E element():获取元素
他的特点:
实现类ArrayDeque
特点
- ArrayDeque是Deque的子实现
- 数据结构表现:队列,栈,双端队列
- 底层实现: 循环数组。要理解一下循环数组的好处。
- 存储元素有序
- 存储元素可重复
- 不可存储null
用法都是Deque的api。
现在解决栈和队列的问题基本上不会使用Stack而是推荐使用ArrayDeque。
主要原因:
1.性能问题,Stack继承Vector,而Vector是线程安全的,所以有额外的开销。
2.ArrayDeque提供更全面的功能,既能够用来作为栈,又可以作为队列使用
3.Stack现在被认为是过时了,现在一般用Deque来替代Stack。
实战中ArrayDeque怎么用
ArrayDeque 的主要方法:
添加元素:
addFirst(E e) / offerFirst(E e): 在前端添加元素
addLast(E e) / offerLast(E e): 在后端添加元素
add(E e) / offer(E e): 在后端添加元素(等同于 addLast/offerLast)
push(E e): 在前端添加元素(等同于 addFirst)
移除元素:
removeFirst() / pollFirst(): 移除并返回前端元素
removeLast() / pollLast(): 移除并返回后端元素
remove() / poll(): 移除并返回前端元素(等同于 removeFirst/pollFirst)
pop(): 移除并返回前端元素(等同于 removeFirst)
查看元素(不移除):
getFirst() / peekFirst(): 返回前端元素
getLast() / peekLast(): 返回后端元素
peek(): 返回前端元素(等同于 peekFirst)
其他操作:
size(): 返回元素数量
isEmpty(): 检查是否为空
clear(): 清空所有元素
contains(Object o): 检查是否包含特定元素
算法题中的推荐用法:
当用作栈时:
push(E e): 压栈
pop(): 出栈
peek(): 查看栈顶元素
isEmpty(): 检查栈是否为空
示例:
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
int top = stack.pop();
int peek = stack.peek();
当用作队列时:
offer(E e): 入队
poll(): 出队
peek(): 查看队首元素
isEmpty(): 检查队列是否为空
示例:
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1);
int front = queue.poll();
int peek = queue.peek();
当用作双端队列时:
offerFirst(E e) / offerLast(E e): 在前/后端添加元素
pollFirst() / pollLast(): 移除并返回前/后端元素
peekFirst() / peekLast(): 查看前/后端元素
isEmpty(): 检查是否为空
示例:
Deque<Integer> deque = new ArrayDeque<>();
deque.offerFirst(1);
deque.offerLast(2);
int front = deque.pollFirst();
int back = deque.pollLast();
推荐使用这些方法的原因:
它们在元素为 null 或双端队列为空时不会抛出异常,而是返回 null 或 false,这样可以简化错误处理。
这些方法名称清晰地表明了它们的用途和操作的位置(前端或后端)。
它们与 Queue 和 Stack 接口的方法名称保持一致,使代码更易读和理解。
所以说ArrayDeque非常万能,当你在做题的时候如果要用到相关的数据结构,就按上面的流程来走。可以模拟队列,栈,双端队列。
232.用栈实现队列
做题前注意:题目说了每个操作都是合法的,所以不要去做不合法的判断了
假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)。所以不用想这些极端情况。
题的本质:
用后进先出实现先进先出
凭我们对栈的理解,显然一个栈是不能完成这个任务的,所以解题思路是用两个栈来完成。
解题思路:
一个栈为入队栈,一个栈为出队栈。
出队的逻辑:
当出队栈存在内容时,出队栈的栈顶,即为第一个出队的元素。
如果出队栈内无元素,此时又需要出栈,那么入队栈的所有元素逐个弹出装入出队栈,然后弹出栈顶元素即可。
入队的逻辑:直接装入入队栈。
当两个栈都空了,就表示队空了。
下面是模拟的过程
来看具体解法
class MyQueue {//这是定义接口,然后初始化指定实现类的写法。一般比较推荐这种写法Deque<Integer> stOut,stIn;//指定实现类为ArrayDeque,因为比较万能//ArrayDeque可以用来模拟栈,由于需要两个栈,那就开两个ArrayDeque。public MyQueue() {stIn = new ArrayDeque<>();stOut = new ArrayDeque<>();}public void push(int x) {//push直接放入进队栈stIn.push(x);}public int pop() {//出队就从出队栈出,如果出队栈为空,那就要把入队栈中的元素依次弹出然后压入入队栈。自己模拟一下就懂了。if(stOut.isEmpty()){while(!stIn.isEmpty()){stOut.push(stIn.pop());}}return stOut.pop();}//直接用pop方法,接住了再放回去public int peek() {int res = this.pop();stOut.push(res);return res;}//出队栈和入队栈都没有元素,那就是空。public boolean empty() {return stIn.isEmpty() && stOut.isEmpty();}
}
225. 用队列实现栈
题意:用两个队列实现栈即,用两个前进迁出实现后进先出。
思路:
看完这个图就懂了
进栈逻辑:
就是直接入队1。
出栈逻辑:
把队1里面的元素全部倒出来,然后最后一个元素出队。然后倒出来的元素又逐个入队2。之后又把队2全部出队又进队1中。
class MyStack {Deque<Integer> que1; // 和栈中保持一样元素的队列Deque<Integer> que2; // 辅助队列public MyStack() {que1 = new ArrayDeque<>();que2 = new ArrayDeque<>();}public void push(int x) {que1.offerLast(x);}public int pop() {int size = que1.size();size--;while (size-- > 0) {que2.offerLast(que1.peekFirst());que1.pollFirst();}int res = que1.pollFirst();que1 = que2;que2 = new ArrayDeque<>();return res;}public int top() {return que1.peekLast();}public boolean empty() {return que1.isEmpty();}
}
本题总结:这个题不难,对于我来说难的是不知道这么多api用哪个比较好,混用有没有风险。
因此这里做个总结:
队列(Queue)风格操作: 添加:offer(E e) 删除:poll() 查看:peek()
这组方法适合当你想要实现一个标准的队列(先进先出)时使用。它们在操作失败时不会抛出异常,而是返回特殊值。
双端队列(Deque)风格操作: 添加:offerFirst(E e), offerLast(E e) 删除:pollFirst(), pollLast() 查看:peekFirst(), peekLast()
当你需要在队列的两端进行操作时,这组方法很有用。它们也不会在操作失败时抛出异常。
抛出异常的操作: 添加:addFirst(E e), addLast(E e), add(E e) 删除:removeFirst(), removeLast(), remove() 查看:getFirst(), getLast()
这组方法在操作失败时会抛出异常(如 NoSuchElementException)。如果你希望立即捕获和处理异常,可以使用这组方法。
List风格操作: 添加:add(E e), add(int index, E element) 删除:remove(int index), remove(Object o) 查看:get(int index)
虽然 ArrayDeque 不是 List,但这些方法使其在某些情况下可以像 List 一样使用。
栈(Stack)风格操作: 添加:push(E e) (等同于 addFirst(E e)) 删除:pop() (等同于 removeFirst()) 查看:peek() (等同于 peekFirst())
当你使用 ArrayDeque 实现栈时,这组方法最为合适。
推荐的使用方式:
如果你在实现一个标准队列,使用 offer(), poll(), peek()。
如果你需要双端队列功能,使用 offerFirst(), offerLast(), pollFirst(), pollLast(), peekFirst(), peekLast()。
如果你在实现一个栈,使用 push(), pop(), peek()。
如果你希望操作失败时抛出异常,使用 add…, remove…, get… 系列方法。
记住,保持一致性是关键。选择一组方法后,尽量在整个实现中坚持使用这组方法,这样可以使你的代码更加清晰和易于理解。
20. 有效的括号
我的非常直观的写法:
class Solution {public boolean isValid(String s) {Deque<Character> stack = new ArrayDeque<>();for (char c : s.toCharArray()) {if (c == '(' || c == '[' || c == '{') {// 如果是左括号,入栈stack.push(c);} else {// 如果是右括号if (stack.isEmpty()) {// 如果栈为空,说明没有匹配的左括号,返回 falsereturn false;}// 检查栈顶元素是否匹配char top = stack.pop();if (c == ')' && top != '(') return false;if (c == ']' && top != '[') return false;if (c == '}' && top != '{') return false;}}// 最后检查栈是否为空,如果为空说明所有括号都匹配了return stack.isEmpty();}
}
1047. 删除字符串中的所有相邻重复项
class Solution {public String removeDuplicates(String s) {char[] str = s.toCharArray();Deque<Character> st = new ArrayDeque<>();for(int i = 0;i<str.length;i++){if(st.isEmpty()){st.push(str[i]);}else{char top = st.peek();if(str[i]==top){st.pop();}else{st.push(str[i]);}}}StringBuilder res = new StringBuilder();while(!st.isEmpty()){char c = st.pollLast();res.append(c);}return res.toString();}
}
今天做题刚总结的,也是我恶心了好久的问题:
ArrayDeque模拟这些结构的时候,光知道api有啥用还不够,方向更是恶心人。
重点
对于 ArrayDeque:双端队列
左边是队首(First)
右边是队尾(Last)
这意味着:
当用作队列时:
左边是队首,右边是队尾
从右边(队尾)添加元素:offer(), add(), addLast()
从左边(队首)移除元素:poll(), remove(), removeFirst()
当用作栈时:
右边是栈底,左边是栈顶。
从左边(队首)添加和移除元素:push() (等同于 addFirst()), pop() (等同于 removeFirst())
查看栈顶元素:peek() 或 peekFirst()
当做双端队列时:
左边时队首,右边时队尾
左边(队首/First)对应的方法:
添加元素:
addFirst(e)
offerFirst(e)
push(e) (当用作栈时)
移除元素:
removeFirst()
pollFirst()
pop() (当用作栈时)
查看元素(不移除):
getFirst()
peekFirst()
peek() (当用作栈或队列时)
右边(队尾/Last)对应的方法:
添加元素:
addLast(e)
offerLast(e)
add(e) (当用作队列时)
offer(e) (当用作队列时)
移除元素:
removeLast()
pollLast()
查看元素(不移除):
getLast()
peekLast()
另一组方法:poll和offer
左边(队首/First)对应的方法:
添加元素:
offerFirst(e)
移除元素:
pollFirst()
查看元素(不移除):
peekFirst()
右边(队尾/Last)对应的方法:
添加元素:
offerLast(e)
offer(e) (当用作队列时,等同于 offerLast(e))
移除元素:
pollLast()
查看元素(不移除):
peekLast()