栈与队列-Java【力扣】【算法学习day.7】

前言

我做这类文档一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？）我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！

共勉！！！

---

一.什么是栈和队列

1.队列

简单来说就是一种先进先出的线性数据结构，如下图：

---

2.栈

简单来说就是一种先进后出的线性数据结构，如下图：

---

二.在习题中掌握基本使用【力扣】

ps：下面1，2两题虽然要求使用栈和队列，这边我利用数组来实现栈和队列，方便各位理解原理和如何自我实现（我反倒觉得自己的是实现比java自带的要方便，但是部分可以省去很多麻烦）。

1.用栈实现队列

题目链接:232. 用栈实现队列 - 力扣（LeetCode）

题面:

基本分析: 可以利用数组模拟数据结构，然后抽象出两个指针模拟队列边界，那么进出等操作其实是指针的移动

class MyQueue {//利用数组模型模拟一个队列int[] arr = new int[200];//运用双指针模拟队列边界int l =0;int r = 0;public MyQueue() {}public void push(int x) {arr[r++] = x;}public int pop() {return arr[l++];}public int peek() {return arr[l];}public boolean empty() {return (l>=r);}
}/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj = new MyQueue();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.peek();* boolean param_4 = obj.empty();*/

---

2.用队列模拟栈

题目链接:225. 用队列实现栈 - 力扣（LeetCode）

题面：

基本分析：数组模拟，并用一个指针表示头

class MyStack {//利用数组模拟栈int[] arr = new int[200];//定义head表示头int head = 0;public MyStack() {}public void push(int x) {arr[++head] = x;}public int pop() {return arr[head--];}public int top() {return arr[head];}public boolean empty() {return head==0;}
}/*** Your MyStack object will be instantiated and called as such:* MyStack obj = new MyStack();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.top();* boolean param_4 = obj.empty();*/

---

3.有效的括号

题目链接：20. 有效的括号 - 力扣（LeetCode） 

题面:

基本分析：模拟一个栈，字符依次入栈，当栈头元素和要入栈的元素匹配时，头出栈而要入栈的元素不入栈

代码：

class Solution {public boolean isValid(String s) {int n = s.length();if(n%2==1)return false;int head = 0;char[] stack = new char[10005];for(char c:s.toCharArray()){if(stack[head]=='('&&c==')')head--;else if(stack[head]=='['&&c==']')head--;else if(stack[head]=='{'&&c=='}')head--;else stack[++head] = c;}return head==0;}
}

---

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

题目链接：1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode） 

题面:

 基本分析:这题和上一题思路一样

代码:

class Solution {public String removeDuplicates(String s) {char[] arr = new char[100005];int head=0;for(char c:s.toCharArray()){if(arr[head]==c)head--;else arr[++head]=c;}return new String(arr,1,head);}}

---

 5.逆波兰表达式求值

题目链接：150. 逆波兰表达式求值 - 力扣（LeetCode）

题面:

基本分析： 我们将得到的数字以此压入栈中，每次拿到运算符时，取两个数进行运算，然后把运算结果再次存入栈中

代码:

class Solution {public int evalRPN(String[] tokens) {long[] arr = new long[10005];int head = 0;int n = tokens.length-1;for(int i =0;i<=n;i++){long number = Integer.MAX_VALUE;char c = ' ';try {number = Integer.valueOf(tokens[i]);} catch (Exception e) {number = Integer.MAX_VALUE;c = tokens[i].toCharArray()[0];}if(number!=Integer.MAX_VALUE)arr[++head]=number;else{if(c=='+'){arr[head-1] = arr[head]+arr[head-1];}else if(c=='-'){arr[head-1] = arr[head-1]-arr[head];}else if(c=='*'){arr[head-1] = arr[head-1]*arr[head];}else{arr[head-1] = arr[head-1]/arr[head];}head--;}}return (int)arr[1];}
}

---

6.滑动窗口最大值

题目链接:239. 滑动窗口最大值 - 力扣（LeetCode） 

题面：

基本分析: 这题用到单调队列，队列元素不完全递减，每次加入新元素要判断队列头元素有没有过期，然后从右边删去所有小于新加入元素的元素，然后把新元素加入，每次窗口的最大值就是队列的最左边元素，当然，未形成窗口前要另外单独讨论，代码如下:

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length;int[] queue = new int[100010];int count = 0;int l =0;int r = 0;queue[0] = Integer.MIN_VALUE;int[] arr = new int[n-k+1];for(int i =-k+1,j=0;j<n;i++,j++){if(i<1){while(l<r&&queue[0]!=-100006&&queue[r-1]<nums[j])r--;queue[r++]=nums[j];if(i==0)arr[count++]=queue[l];}else{if(queue[l]==nums[i-1])l++;while(l<r&&queue[r-1]<nums[j])r--;queue[r++]=nums[j];arr[count++]=queue[l];}}return arr;}
}

---

7.前k个高频元素 

题目链接:347. 前 K 个高频元素 - 力扣（LeetCode）

题面:

基本分析： 因为涉及到排序，可以使用优先队列(如果你不懂这个数据结构可以去了解一下，简单来说就是你用这个可以把队列里的数据排好序，每次取都是队列里的最值)

代码:

class Solution {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<>((a,b)->b.getValue()-a.getValue());queue.addAll(map.entrySet());int[] result = new int[k];for(int i = 0;i<k;i++){result[i] = queue.poll().getKey();}return result;}
}

---

后言 

上面是栈与队列一些最经典的题目，以后碰到其他好题也会更新，希望有所帮助，一同进步，共勉！