栈与队列
232. 用栈实现队列
- 思路
- 使用两个栈
- 一个栈负责队列的push存元素，将里面的元素pop后放在另外一个栈。此时，另外一个栈最上面的就是最先放入，可用来做队列的pop
- 代码
public MyQueue() {
pushSt = new Stack<>();
popSt = new Stack<>();
}
public void push(int x) {
pushSt.push(x);
}
public int pop() {
if(popSt.isEmpty()){ // 注意点一
while(!pushSt.isEmpty()){
popSt.push(pushSt.pop());
}
}
return popSt.pop();
}
public boolean empty() {
return pushSt.isEmpty() && popSt.isEmpty();
}
-
注意点
- 注意点一：只有负责pop的栈为空时，才需要从push的栈转移元素过来，这样才能保证pop栈最上面的元素是最先进入的
-
扩展
-
Queue接口API
-
Deque接口API
-
StackAPI和Deque API对比
-
-
官网推荐使用Deque、替代原有的Stack、Queue。
- 具体实现类有LinkedList、ArrayDeque
- LinkedList为链表实现 add、offer方法实现不同、ArrayDeque为数组实现，add、offer方法实现相同
-
参考博客
https://blog.csdn.net/ji_meng/article/details/126717159
https://blog.csdn.net/weixin_73077810/article/details/133667056
225. 用队列实现栈
-
思路
- 放入队列后，如果想找到最后插入的一个（后入先出），必现弹出之前插入的一批元素
- 借助一个辅助队列，弹出前面插入的数据后，先放到另外一个队列中
- 使用两个队列，始终有一个队列为空，用于弹出时做辅助
-
代码
public MyStack() {
q1 = new LinkedList<>();
q2 = new LinkedList<>();
}
public void push(int x) {
// 放进非空的那一个q
if(!q1.isEmpty()){
q1.offer(x);
}else{
q2.offer(x);
}
}
public int pop() {
// 转移非空的那个q到空的那个，最后一个元素就是最后进入的
Queue<Integer> emptyQueue = q1.isEmpty() ? q1 : q2;
Queue<Integer> noEmptyQueue = q1.isEmpty() ? q2 : q1;
while(noEmptyQueue.size() > 1){
emptyQueue.offer(noEmptyQueue.poll());
}
return noEmptyQueue.poll();
}
public int top() {
Queue<Integer> emptyQueue = q1.isEmpty() ? q1 : q2;
Queue<Integer> noEmptyQueue = q1.isEmpty() ? q2 : q1;
int last = 0;
while(noEmptyQueue.size() > 0){
last = noEmptyQueue.poll();
emptyQueue.offer(last);
}
return last;
}
-
扩展
- 一个队列也可以实现，循环使用。在poll之前记录下队列的长度n，poll后重新加入到队列，poll n次即可拿到最后的元素
Queue<Integer> q; public MyStack() { q = new LinkedList<>(); } public void push(int x) { q.add(x); } public int pop() { int size = q.size(); while(size-- > 1){ q.add(q.poll()); } return q.poll(); }
347. 前 K 个高频元素
- 思路
- 统计每个元素的次数，使用优先级队列进行排序。再弹出k个即可
- 代码
public int[] topKFrequent(int[] nums, int k) {
// 统计次数
Map<Integer,Integer> map = new HashMap<>();
for(int num : nums){
map.put(num,map.getOrDefault(num,0)+1);
}
// 使用优先级队列排序
PriorityQueue<Map.Entry<Integer,Integer>> queue =
new PriorityQueue<>((o1,o2) -> o2.getValue()-o1.getValue());
for(Map.Entry<Integer,Integer> entry : map.entrySet()){
queue.offer(entry);
}
// 取出前k位
int[] res = new int[k];
while(k -- > 0){
res[k] = queue.poll().getKey();
}
return res;
}
- 扩展
- 优先级队列可以换成桶排序
public int[] topKFrequent(int[] nums, int k) {
// 统计次数
Map<Integer,Integer> map = new HashMap<>();
for(int num : nums){
map.put(num,map.getOrDefault(num,0)+1);
}
// 用数组存储 index出现次数，value为
List<Integer>[] frelists = new List[nums.length + 1];
for(int key : map.keySet()){
int i = map.get(key);
if(frelists[i] == null){
frelists[i] = new ArrayList();
}
frelists[i].add(key);
}
// 取出前k位
int[] res = new int[k];
while(k -- > 0){
res[k] = queue.poll().getKey();
}
return res;
}
239. 滑动窗口最大值
- 思路
- 遍历全部元素，借助队列来存取得前k个中的最大值（窗口内的最大值）。每次遍历需要处理以下
- 更新队列。移除非窗口内的元素
- 移除队列中小于当前元素的，添加当前元素。因为是向右移动的，比当前小的元素在之后的窗口里不可能成为最大值
- 辅助队列会形成一个单调递减队列
- 取辅助队列的第一个元素即为当前窗口最大值
- 遍历全部元素，借助队列来存取得前k个中的最大值（窗口内的最大值）。每次遍历需要处理以下
- 代码
public int[] maxSlidingWindow(int[] nums, int k) {
int[] res = new int[nums.length - k + 1];
// 辅助队列，第一个元素为窗口当前最大值
Deque<Integer> dq = new LinkedList<>();
// 考虑[i-k+1,i]的窗口
for(int i = 0; i < nums.length; i++){
// 更新队列，不在窗口内的元素进行移除
if(!dq.isEmpty() && dq.peekFirst() < i - k + 1){
dq.pollFirst();
}
// 可以移除掉小于当前值的数
while(!dq.isEmpty() && nums[dq.peekLast()] < nums[i]){
dq.pollLast();
}
dq.offerLast(i);
// 填充最大值
if(i >= k - 1){
res[i-k+1] = nums[dq.peekFirst()];
}
}
return res;
}