对于以下的专栏来源于：代码随想录 - 栈与队列
关于栈和队列的知识可看我之前的文章
【数据结构】栈和队列详细分析（全）
以及高级的数据结构
java中的PriorityQueue底层和实现原理深入源码探究
关于栈也可用
LinkedList<Integer> A = new LinkedList<Integer>();
A.addLast(value);
int a = A.removeLast();
Deque stack = new LinkedList<>(); ，push，popArrayDeque stack= new ArrayDeque<>(); ，ArrayDeque会比LinkedList在除了删除元素这一点外会快一点Deque deque = new LinkedList<>(); ，offerLast，peekLast，pollLast等// 使用数组格式进行优先队列
PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>(){
public int compare(int[] a, int[] b){
// 降序，大根堆
// 对于value进行排序
return a[1] - b[1];
}
});
map.put(nums[i],map.getOrDefault(nums[i],0) + 1);哈希集合的遍历：
for(Map.Entry<Integer,Integer> entry:map.entrySet()){
int num = entry.getKey(), count = entry.getValue();
// 如果遍历，key或者value：
for(Integer key:map.keySet())
字符转换为数字：Integer.valueOf(s)
数字转换为字符：String.valueOf(n)
思路如下：
要实现队列的功能，将所有【入栈】的数据放到【出栈】中，输出【出栈】pop即可
class MyQueue {
//创建两个【出栈】【入栈】
Stack<Integer>stkin;
Stack<Integer>stkout;
//通过初始化构造参数，建立对象
public MyQueue() {
stkin=new Stack<>();
stkout=new Stack<>();
}
//【入栈】函数专门放入栈的数据
public void push(int x) {
stkin.push(x);
}
//要实现队列的功能，将所有【入栈】的数据放到【出栈】中，输出【出栈】pop即可
public int pop() {
//判断【出栈】有无数据
//如果【出栈】有数据，直接返回【出栈】的pop即可
//如果【出栈】无数据，则继续将【入栈】的数据都放到【出栈】，最后返回【出栈】数据即可
if(stkout.isEmpty()){
while(!stkin.isEmpty()){
stkout.push(stkin.pop());
}
}
return stkout.pop();
}
//因为数据可能没有【出栈】就要查询队列的头节点，所以这部分数据，也要进行入栈出栈的操作
public int peek() {
//判断【出栈】有无数据
//如果【出栈】有数据，直接返回【出栈】的pop即可
//如果【出栈】无数据，则继续将【入栈】的数据都放到【出栈】，最后返回【出栈】数据即可
if(stkout.isEmpty()){
while(!stkin.isEmpty()){
stkout.push(stkin.pop());
}
}
return stkout.peek();
}
//为空的条件是两个栈都为空，函数为isEmpty()
public boolean empty() {
return stkin.isEmpty()&stkout.isEmpty();
}
}
另一道题目：
剑指 Offer 09. 用两个栈实现队列
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
下面的的代码模块中多一个判断条件
class CQueue {
Deque<Integer> stack1;
Deque<Integer> stack2;
public CQueue() {
stack1 = new LinkedList<Integer>();
stack2 = new LinkedList<Integer>();
}
public void appendTail(int value) {
stack1.push(value);
}
public int deleteHead() {
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
//因为源源不断的数据，如果2还是为空，没有添加进去，则返回为-1
if(stack2.isEmpty()){
return -1;
}else return stack2.pop();
}
}
使用两个队列的思想：
// 队列1用来操作，之后队列1与2进行对换，队列2 来判断栈顶 栈元素，以及出栈
class MyStack {
// 队列的初始化
Queue<Integer>queue1;
Queue<Integer>queue2;
public MyStack() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
}
public void push(int x) {
queue1.offer(x);
while(!queue2.isEmpty()){
queue1.offer(queue2.poll());
}
// 之后1与2进行交换
Queue<Integer> temp = queue1;
queue1 = queue2;
queue2 = temp;
}
public int pop() {
return queue2.poll();
}
public int top() {
return queue2.peek();
}
public boolean empty() {
return queue2.isEmpty();
}
}
使用一个队列实现栈：
class MyStack {
// 队列的初始化
Queue<Integer>queue;
public MyStack() {
queue = new LinkedList<>();
}
public void push(int x) {
// 此n为 在入栈之前 都要将其重新出入一遍
int n = queue.size();
queue.offer(x);
for(int i = 0;i < n;i++){
// 队列的出栈 为poll
queue.offer(queue.poll());
}
}
public int pop() {
return queue.poll();
}
public int top() {
return queue.peek();
}
public boolean empty() {
return queue.isEmpty();
}
}
class Solution {
public boolean isValid(String s) {
Map<Character,Character> map = new HashMap<>();
map.put(')','(');
map.put('}','{');
map.put(']','[');
Deque<Character> stack = new LinkedList<>();
for(int i = 0; i < s.length();i++){
//如果包含这个有括号，则要相应的把左括号去除，判断是否跟peek相等
if(map.containsKey(s.charAt(i))){
if(stack.isEmpty() || map.get(s.charAt(i)) != stack.peek()){
return false;
}
stack.pop();
}else{
//如果没有包含这个右括号，则要把左括号进栈，相对应的当前的符号 也就是左括号
stack.push(s.charAt(i));
}
}
//如果stack还有东西，说明不是有效的括号
return stack.isEmpty();
}
}
以下不使用map结构，直接进行比较：
class Solution {
public boolean isValid(String s) {
// 不使用map结构，直接进行比较
Deque<Character> stack = new LinkedList<>();
for(int i = 0; i < s.length();i++){
// 单个字符 无法使用equals进行比较判断
if(s.charAt(i) == '('){
stack.push(')');
}else if(s.charAt(i) == '{'){
stack.push('}');
}else if(s.charAt(i) == '['){
stack.push(']');
// 如果栈为空，或者对应的peek 不相等，则直接返回false
}else if (stack.isEmpty() || stack.peek() != s.charAt(i) ){
return false;
}else {
// 右边的括号配对成功，就会将其右括号出栈
stack.pop();
}
}
return stack.isEmpty();
}
}
题目：leetcode：1047. 删除字符串中的所有相邻重复项
直接用栈的格式进行输出：
class Solution {
public String removeDuplicates(String s) {
Deque<Character> deque = new LinkedList<>();
for(int i = 0 ;i < s.length();i++){
if(!deque.isEmpty() && deque.peek() == s.charAt(i)){
deque.pop();
}else {
deque.push(s.charAt(i));
}
}
String str = "";
while(!deque.isEmpty()){
// 加上之前的str ，对应进行输出
str = deque.pop() + str;
}
return str;
}
}
使用字符串 做类似栈的功能：
class Solution {
public String removeDuplicates(String s) {
StringBuffer sb = new StringBuffer();
// 定义top 模仿数组的下标元素 或者是 栈的top指针
int top = -1;
for(int i = 0 ;i < s.length();i++){
char c = s.charAt(i);
// 如果top大于等于0 而且两者相等，则对应进行出栈！
if(top >= 0 && sb.charAt(top) == c){
// 此处删除的是字符串最后的一个元素
sb.deleteCharAt(top);
top--;
}else {
sb.append(c);
top++;
}
}
// 返回的类型为toString
return sb.toString();
}
}
栈的思想，中序遍历
class Solution {
public int evalRPN(String[] tokens) {
// 栈
Deque<Integer> stack = new LinkedList<>();
// 遍历的形式 对应模拟算法判断
for(String s: tokens){
if("+".equals(s)){
stack.push(stack.pop() + stack.pop());
}else if("-".equals(s)){
stack.push(-stack.pop() + stack.pop());
}else if("*".equals(s)){
stack.push(stack.pop() * stack.pop());
}else if("/".equals(s)){
int temp1 = stack.pop();
int temp2 = stack.pop();
stack.push(temp2 / temp1);
}else{
// 需要将其字符转换为数字
stack.push(Integer.valueOf(s));
}
}
return stack.pop();
}
}
使用优先队列存储滑动窗口的值，但窗口会移动，对应窗口滑动需要对应判断最大值（将最大值在区间外的对应删除即可）
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
PriorityQueue<int []> queue = new PriorityQueue<>(new Comparator<>(){
public int compare(int []a,int b[]){
if(a[0] == b[0]){
// 相等的时候，是最新的i排在前面
return b[1] - a[1];
}
// 不相等的时候 是降序排列
return b[0] - a[0];
}
});
for(int i = 0;i < k;i++){
queue.add(new int[]{nums[i],i});
}
int[] res = new int [nums.length - k +1];
// 存入第一个窗口的最大值
res[0] = queue.peek()[0];
// 遍历后续窗口的最大值，从k开始
for(int i = k;i < nums.length;i++){
queue.add(new int[]{nums[i],i});
// 判断最大值是否在区间外，如果是区间外，则进行出栈
while(queue.peek()[1] <= i - k ){
queue.poll();
}
// 对应的华东窗口最左边的值 赋值
res[i - k + 1] = queue.peek()[0];
}
return res;
}
}
维护一个单调队列，而且是滑动窗口
双端队列的思想：
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
Deque<Integer> deque = new LinkedList<>();
for(int i = 0 ; i < k ;i++){
// 每次有新的元素之后 如果大于，就把新的队尾元素给剔除
while(!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]){
deque.pollLast();
}
// 否则进入到队尾元素
deque.offerLast(i);
}
int[] res = new int [n - k + 1];
// 存储队头元素，因为队头元素一定最大 （一开始进入的时候就只有大于才能进入，否则会被剔除）
res[0] = nums[deque.peekFirst()];
for(int i = k;i < n;i++){
while(!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]){
deque.pollLast();
}
deque.offerLast(i);
// 将其队头元素最大 且在区间外的，都把队头元素剔除
while(deque.peekFirst() <= i - k){
deque.pollFirst();
}
res[i - k + 1] = nums[deque.peekFirst()];
}
return res;
}
}
不用堆的逻辑模拟算法：
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0;i < nums.length;i++){
// 查看是否存在，通过map.containsKey
if(!map.containsKey(nums[i])){
map.put(nums[i],1);
}else{
map.put(nums[i],map.get(nums[i]) + 1);
}
}
int max = Integer.MIN_VALUE;
// 注意hashmap的遍历
for(Map.Entry<Integer,Integer> entry:map.entrySet()){
if(entry.getValue() > max){
max = entry.getValue();
}
}
int []res = new int[k];
while(k > 0){
for(Map.Entry<Integer,Integer> entry:map.entrySet()){
if(entry.getValue() == max){
// 此处数组 为k-1
res[k - 1] = entry.getKey();
k--;
}
}
// 最大的数值往下降的判断
max--;
}
return res;
}
}
增加map集合的判断
还可以使用如下方式：getOrDefault
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
另外一种思路写法，使用优先队列（本身就有堆的思想）
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0 ; i < nums.length; i++){
map.put(nums[i],map.getOrDefault(nums[i],0) + 1);
}
// 这个用法记住
PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>(){
public int compare(Integer a, Integer b){
// 降序，大根堆
return map.get(a) - map.get(b);
}
});
for(Integer key:map.keySet()){
if(queue.size() < k){
queue.add(key);
}else if (map.get(key) > map.get(queue.peek())){
queue.poll();
queue.add(key);
}
}
int []res = new int[k];
int index = 0;
while(!queue.isEmpty()){
res[index++] = queue.poll();
}
return res;
}
}
另外一种更加简易的写法：
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0 ; i < nums.length; i++){
map.put(nums[i],map.getOrDefault(nums[i],0) + 1);
}
// 对应的优先队列只设置value即可
PriorityQueue<Integer> queue = new PriorityQueue<>((o1,o2)->map.get(o2)-map.get(o1));
// 直接把所有值都存，弹出优先队列的前k个即可
for(Integer Key:map.keySet()){
queue.add(Key);
}
int[] res = new int[k];
for (int i = k - 1; i >= 0; i--) {
res[i] = queue.poll();
}
return res;
}
}
和上面的代码思路差不多，但有所差别：
存入优先队列上面代码的思路是只有value
下面的思路是key以及value的数组
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>();
for(int i = 0 ; i < nums.length; i++){
map.put(nums[i],map.getOrDefault(nums[i],0) + 1);
}
// 使用数组格式进行优先队列
PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>(){
public int compare(int[] a, int[] b){
// 降序，大根堆
// 对于value进行排序
return a[1] - b[1];
}
});
// map集合遍历
for(Map.Entry<Integer,Integer> entry:map.entrySet()){
int num = entry.getKey(), count = entry.getValue();
if(queue.size() < k){
queue.add(new int[]{num, count});
// 如果当前值的value小于 优先队列的peek的value（本身存进优先队列就是key value）
}else if (count > queue.peek()[1]){
queue.poll();
queue.add(new int[]{num, count});
}
}
int []res = new int[k];
int index = 0;
while(!queue.isEmpty()){
res[index++] = queue.poll()[0];
}
return res;
}
}