提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
文章目录
- 前言
- 一、力扣232. 用栈实现队列
- 二、力扣225. 用队列实现栈
- 三、力扣20. 有效的括号
- 四、力扣1047. 删除字符串中的所有相邻重复项
- 五、力扣150. 逆波兰表达式求值
- 六、力扣239. 滑动窗口最大值
- 七、力扣前 K 个高频元素
前言
在栈与队列系列中，我们强调栈与队列的基础，也是很多同学容易忽视的点。 使用抽象程度越高的语言，越容易忽视其底层实现，而C++相对来说是比较接近底层的语言。 我们用栈实现队列，用队列实现栈来掌握的栈与队列的基本操作。
一、力扣232. 用栈实现队列
class MyQueue {
private Deque<Integer> d1;
private Deque<Integer> d2;
public MyQueue() {
this.d1 = new LinkedList<>();
this.d2 = new LinkedList<>();
}
public void push(int x) {
d1.offerLast(x);
}
public int pop() {
if(!d2.isEmpty()){
return d2.pollLast();
}
while(!d1.isEmpty()){
d2.offerLast(d1.pollLast());
}
return d2.pollLast();
}
public int peek() {
if(!d2.isEmpty()){
return d2.peekLast();
}
while(!d1.isEmpty()){
d2.offerLast(d1.pollLast());
}
return d2.peekLast();
}
public boolean empty() {
return d1.isEmpty() && d2.isEmpty();
}
}
二、力扣225. 用队列实现栈
class MyStack {
Deque<Integer> d1 = new LinkedList<>();
Deque<Integer> d2 = new LinkedList<>();
public MyStack() {
}
public void push(int x) {
d1.offerLast(x);
}
public int pop() {
if(!d1.isEmpty()){
while(d1.size() > 1){
d2.offerLast(d1.pollFirst());
}
return d1.pollFirst();
}
while(d2.size() > 1){
d1.offerLast(d2.pollFirst());
}
return d2.pollFirst();
}
public int top() {
if(!d1.isEmpty()){
while(d1.size() > 1){
d2.offerLast(d1.pollFirst());
}
return d1.peekFirst();
}
while(d2.size() > 1){
d1.offerLast(d2.pollFirst());
}
int res = d2.pollFirst();
d1.offerLast(res);
return res;
}
public boolean empty() {
return d1.isEmpty() && d2.isEmpty();
}
}
三、力扣20. 有效的括号
class Solution {
public boolean isValid(String s) {
Deque<Character> deq = new LinkedList<>();
for(char c : s.toCharArray()){
if(c == '[' || c == '(' || c == '{'){
deq.offerLast(c);
}else{
if(deq.isEmpty()){
return false;
}
char t = deq.pollLast();
if(c == ')' && t != '('){
return false;
}
if(c == ']' && t != '['){
return false;
}
if(c == '}' && t != '{'){
return false;
}
}
}
return deq.isEmpty();
}
}
四、力扣1047. 删除字符串中的所有相邻重复项
class Solution {
public String removeDuplicates(String s) {
Deque<Character> deq = new LinkedList<>();
for(char c : s.toCharArray()){
if(deq.isEmpty()){
deq.offerLast(c);
continue;
}
if(deq.peekLast() == c){
deq.pollLast();
continue;
}
deq.offerLast(c);
}
StringBuilder sb = new StringBuilder();
while(!deq.isEmpty()){
sb.append(deq.pollFirst());
}
return sb.toString();
}
}
五、力扣150. 逆波兰表达式求值
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> deq = new LinkedList<>();
int l = 0, r = 0;
for(String s : tokens){
if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")){
r = deq.pollLast();
l = deq.pollLast();
switch (s){
case "+" : deq.offerLast(l + r);break;
case "-" : deq.offerLast(l - r);break;
case "*" : deq.offerLast(l * r);break;
case "/" : deq.offerLast(l / r);break;
}
}else{
System.out.println(s);
deq.offerLast(Integer.parseInt(s));
}
}
return deq.pollLast();
}
}
六、力扣239. 滑动窗口最大值
滑动窗口中的最大值，首先维护一个单调队列，这题要求最大值，所以维护的是一个出队方向最大的一个单调队列，对于每一个元素来说，轮到他时，就要判断一下，队列头的元素是不是在窗口内的，不是的要抛出，然后就是维护队列的逻辑，判断队列是否非空，空的话直接加入，非空的话，从队尾方向，把小于当前元素的都抛出，最后把自己维护进去，然后是收集逻辑，因为是窗口的最大值，所以一开始，当前元素未移动到窗口的最后一个，不做收集
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> deq = new LinkedList<>();
List<Integer> res = new ArrayList<>();
for(int i = 0; i < nums.length; i ++){
if(!deq.isEmpty() && deq.peekFirst() <= i-k){
deq.pollFirst();
}
if(deq.isEmpty()){
deq.offerLast(i);
}else{
while(!deq.isEmpty() && nums[i] > nums[deq.peekLast()]){
deq.pollLast();
}
deq.offerLast(i);
}
if(i >= k-1){
res.add(nums[deq.peekFirst()]);
}
}
int[] array = res.stream().mapToInt(Integer::intValue).toArray();
return array;
}
}
七、力扣前 K 个高频元素
获取前K个高频元素，可以先用map收集各个元素的频率，然后使用优先级队列，大根堆进行收集，最后抛出前K个元素
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>();
int[] res = new int[k];
for(int n : nums){
map.put(n, map.getOrDefault(n,0) + 1);
}
PriorityQueue<int[]> pq = new PriorityQueue<>((x1,x2) -> x2[1] - x1[1]);
for(Map.Entry<Integer,Integer> entry : map.entrySet()){
pq.add(new int[]{entry.getKey(),entry.getValue()});
}
for(int i = 0; i < k; i ++){
res[i] = pq.poll()[0];
}
return res;
}
}
