＜Java＞手把手带你刷leetcode(栈和队列篇)

文章目录

一、栈

1.leetcode20.有效的括号

1.1.题目描述

1.2.思路分析

找反例
1.给定一个字符串，首先要把字符串转为字符数组一个个的判断
2.找到不满足闭合条件的反例即可
使用栈这个结构：
1.转为字符数组一个个的判断
2.碰到左括号就入栈
3.碰到右括号就把栈顶的左括号出栈，与右括号比较，查看是否匹配，若匹配则继续向下判断，若不匹配则找到反例，返回false；当整个字符串走完，且栈为空，则说明字符串是符合条件的

1.3.代码实现

public boolean isValid(String s){
        Stack<Character> stack =newStack<>();for(int i =0; i < s.length(); i++){
            char c = s.charAt(i);if(c =='('|| c =='['|| c =='{'){
                stack.push(c);}else{if(stack.isEmpty()){returnfalse;}
                char top = stack.pop();//找反例if(c ==')'&& top !='('){returnfalse;}if(c ==']'&& top !='['){returnfalse;}if(c =='}'&& top !='{'){returnfalse;}}}return stack.isEmpty();}

2.leetcode155.最小栈

2.1.题目描述

2.2.思路分析

题目需要我们在栈的基础上拓展一个getMin方法，可以立即取得当前栈的最小值，时间复杂度为O(1),
双栈思想：
我们可以使用两个栈，s1和s2，s1保存实际元素，s2永远保存最小元素

s1和s2同时入元素
整个操作的核心在于
当s2为空时，直接入栈
当s2栈顶的元素 > 当前元素，也是直接入栈
当s2栈顶的元素 < 当前元素，就把栈顶的元素在入一次栈（保证s2的元素个数和s1的元素个数保持一致）；如果不一致，同步出栈后，s2为空了，s1还有元素，就无法判断了，元素个数相同，入栈和出栈操作都是同步的，那么s2的栈顶就永远保存了当前数据的最小元素。
那么此时的s2的栈顶元素一定是最小元素，只用调用s2.peek();即可

2.3.代码实现

classMinStack{publicMinStack(){}//s1永远保存实际元素private Stack<Integer> s1 =newStack<>();//s2顶部永远保存最小元素private Stack<Integer> s2 =newStack<>();publicvoidpush(int val){
        s1.push(val);if(s2.isEmpty()){
            s2.push(val);}else{
            int peek = s2.peek();
            s2.push(Math.min(val,peek));}}publicvoidpop(){
        s1.pop();
        s2.pop();}public int top(){return s1.peek();}public int getMin(){return s2.peek();}}/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

二、队列

1.leetcode225.用队列实现栈

1.1.题目描述

1.2.思路分析

上一题采用了双栈思想，一个栈保存实际元素，另一个栈作为辅助作用，本题也可以采用相同的思路，其中一个队列q1永远都是实际存储元素的队列，栈的pop就是q1的poll,栈的peek就是q1的peek，栈的push就是q1的offer，保证q1和栈的操作保持一致
另外一个队列q2作为辅助

一定记住，q1永远是储存元素的队列，栈和队列的出队顺序刚好是相反的，先让新元素入q2，然后让q1的所有元素出队再入q2，然后我们只需要将q1和q2的引用交换一下即可，那么q1还是储存元素的队列

1.3.代码实现

classMyStack{publicMyStack(){}//queue永远是实际保存元素的队列private Queue<Integer> queue1 =newLinkedList<>();//queue作为辅助private Queue<Integer> queue2 =newLinkedList<>();publicvoidpush(int x){//新元素直接入队2
         queue2.offer(x);//将旧元素依次出队1，入队2while(!queue1.isEmpty()){
            queue2.offer(queue1.poll());}//交换queue1和queue2
        Queue<Integer> temp;
        temp = queue1;
        queue1 = queue2;
        queue2 = temp;}public int pop(){return queue1.poll();}public int top(){return queue1.peek();}public boolean empty(){return queue1.isEmpty();}}/**
 * 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();
 */

2.leetcode232.用栈实现队列

2.1题目描述

2.2.思路分析

同样的思路，双栈思路

s1永远是保存元素的栈
1.先将s1中的元素依次弹出放入s2中
2.将新元素放入s1中 – – > 此时这个元素就是s1的栈底(队尾元素)
3.再将s2中的元素依次弹回到s1（此时s1就是先进先出的队列）

2.3.代码实现

classMyQueue{publicMyQueue(){}//s1永远保存实际元素private Stack<Integer> s1 =newStack<>();private Stack<Integer> s2 =newStack<>();publicvoidpush(int x){while(!s1.isEmpty()){
            s2.push(s1.pop());}
        s1.push(x);while(!s2.isEmpty()){
            s1.push(s2.pop());}}public int pop(){return s1.pop();}public int peek(){return s1.peek();}public boolean empty(){return s1.isEmpty();}}/**
 * 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();
 */