LeetCode——栈和队列（Java）

栈和队列

• 简介
• [简单] 232. 用栈实现队列
• [简单] 225. 用队列实现栈
• [简单] 20. 有效的括号
• [简单] 1047. 删除字符串中的所有相邻重复项
• [中等] 150. 逆波兰表达式求值
• [困难] 239. 滑动窗口最大值
• [��等] 347. 前 K 个高频元素

  简介

  记录一下自己刷题的历程以及代码。写题过程中参考了 代码随想录。会附上一些个人的思路，如果有错误，可以在评论区提醒一下。

  涉及到：栈、队列、双端队列、map、优先队列、java装箱拆箱问题。

  [简单] 232. 用栈实现队列

  原题链接

  使用两个栈实现，stack1接受数据，每次要pop或者peek的时候，把stack1里的数据再出栈入栈 放置到stack2中，这样又对stack1中的数据做了一次转置。注意stack2中有元素时，stack1不能向stack2传入数据，否则会出现顺序错乱。

  class MyQueue {    //假设了所有操作都是有效的    public Stack stack1;    public Stack stack2;    public MyQueue() {        stack1 = new Stack();        stack2 = new Stack();    }    public void push(int x) {        stack1.push(x);    }    public int pop() {        reverse();        return stack2.pop();    }    public int peek() {        reverse();        return stack2.peek();    }    public boolean empty() {        if(stack2.empty() && stack1.empty()){            return true;        }        return false;    }    //stack2中没有元素时，把stack1中元素全部转置    private void reverse(){        if(stack2.empty()) {            while (!stack1.empty()) {                Integer temp = stack1.pop();                stack2.push(temp);            }        }    }}

  [简单] 225. 用队列实现栈

  原题链接

  使用两个队列实现，时刻保持只有一个队列A存放元素，另一个队列B用于pop或者top操作时接收A的数据，就可以对队列A队尾的元素进行操作。队列A和队列B是相对概念，两个队列某一时刻都可能是存放元素的那个队列。

  class MyStack {    Queue queue1;    Queue queue2;    public MyStack() {        queue1 = new LinkedList();        queue2 = new LinkedList();    }    public void push(int x) {        if(queue1.isEmpty()) queue2.add(x);        else queue1.add(x);    }    public int pop() {        if(queue1.isEmpty()) {            while(queue2.size() > 1){                queue1.add(queue2.poll());            }            return queue2.poll();        }        while(queue1.size() > 1){            queue2.add(queue1.poll());        }        return queue1.poll();    }    public int top() {        if(queue1.isEmpty()) {            while(queue2.size() > 1){                queue1.add(queue2.poll());            }            Integer temp =  queue2.peek();            queue1.add(queue2.poll());            return temp;        }        while(queue1.size() > 1){            queue2.add(queue1.poll());        }        Integer temp =  queue1.peek();        queue2.add(queue1.poll());        return temp;    }    public boolean empty() {        if(queue1.isEmpty() && queue2.isEmpty()){            return true;        }        return false;    }}

  [简单] 20. 有效的括号

  原题链接

  使用栈做符号匹配，碰到左括号压栈，碰到右括号，看目前栈顶是否与之匹配，若不匹配或空，则表示匹配错误。若循环结束栈不为空，表示有多余的左括号。

  class Solution {    public boolean isValid(String s) {        Stack stack = new Stack();        for(int i = 0; i  
  [简单] 1047. 删除字符串中的所有相邻重复项
   
  原题链接
   
  方法①：使用队列，每次入栈时如果与栈顶元素相同，则不入栈，并弹出栈顶元素。
   
  class Solution {    public String removeDuplicates(String s) {        ArrayDeque stack = new ArrayDeque();        for(int i = 0; i  
  方法②：快慢指针法指针法，就把[0-slow]范围内看作一个栈，栈顶是slow指针的位置，一旦出现c[slow] == c[slow - 1]，就回退一次，将栈顶弹出，否则就将当前fast遍历到的元素加进来。
   
  class Solution {    //快慢指针法    public String removeDuplicates(String s) {        //声明字符串数组用于修改，String类是静态变量        char[] c = s.toCharArray();        int slow = 0;        int fast = 0;        while(fast  0 && c[slow] == c[slow - 1]) {                slow--;            } else {                slow++;            }            fast++;        }        return new String(c, 0, slow);    }}
   
  [中等] 150. 逆波兰表达式求值
   
  原题链接
   
  token是数字，就做类型转换压入栈，如果是运算符，弹出栈顶两个数字做运算，记住减法和除法是有顺序的。
   
  class Solution {    public int evalRPN(String[] tokens) {        ArrayDeque stack = new ArrayDeque();        for(int i = 0; i  
  [困难] 239. 滑动窗口最大值
   
  原题链接
   
  原先pop方法和push方法都是Integer参数，一半示例无法通过，改成int之后顺利通过。
   
  涉及到装箱拆箱问题，==运算符可以应用与对象包装器对象，只不过检测的事对象是否指向同一个存储区域。比如Integer a = 1000；Integer b =1000；a==b 未必是true。
   
  缓存机制：Java 基本数据类型的包装类型的大部分都用到了缓存机制来提升性能。Byte,Short,Integer,Long 这 4 种包装类默认创建了数值 [-128，127] 的相应类型的缓存数据
   
  class MoQueue{    public ArrayDeque queue;    public MoQueue(){        queue = new ArrayDeque();    }    public void pop(int a){        if(!queue.isEmpty() && queue.peek() == a)            queue.pollFirst();        return;    }    public void push(int a){        while(!queue.isEmpty() && a > queue.getLast()){            queue.pollLast();        }        queue.addLast(a);    }    public Integer peek(){        return queue.peek();    }}class Solution {    public int[] maxSlidingWindow(int[] nums, int k) {        MoQueue moQueue = new MoQueue();        int[] answer = new int[nums.length - k + 1];        for(int i = 0; i  
  [中等] 347. 前 K 个高频元素
   
  原题链接
   
  使用map存储键值对记录每个数字出现的频次，再使用优先队列定义排序，获取前k个队头元素即可。
   
  class Solution {    public int[] topKFrequent(int[] nums, int k) {        Map map = new HashMap();//key为数组元素值,val为对应出现次数        for(int num:nums){            map.put(num,map.getOrDefault(num,0)+1);        }        PriorityQueue pq = new PriorityQueue(new Comparator() {            @Override            public int compare(Integer a, Integer b) {                return map.get(b) - map.get(a);            }        });        int[] ans = new int[k];        int i = 0;        for(Integer key : map.keySet()){            pq.add(key);        }        while(i