当前位置：首页 > news >正文

给自己复盘用的随想录笔记-栈与队列

news 来源：原创 2024/9/21 5:50:43

用栈实现队列

难在出去

232. 用栈实现队列 - 力扣（LeetCode）

class MyQueue {private Stack<Integer> A;private Stack<Integer> B;public MyQueue() {A=new Stack<>();B=new Stack<>();}public void push(int x) {A.push(x);}public int pop() {int peek=peek();B.pop();return peek;}public int peek() {if(!B.isEmpty()) return B.peek();if(A.isEmpty()) return -1;while(!A.isEmpty()){B.push(A.pop());}return B.peek();}public boolean empty() {return A.isEmpty()&&B.isEmpty();}
}

用队列实现栈

难在进入

225. 用队列实现栈 - 力扣（LeetCode）

class MyStack {Queue<Integer> A;Queue<Integer> B;public MyStack() {A=new LinkedList<Integer>();B=new LinkedList<Integer>();}public void push(int x) {B.offer(x);while(!A.isEmpty()){B.offer(A.poll());}Queue<Integer> C=A;A=B;B=C;}public int pop() {return A.poll();}public int top() {return A.peek();}public boolean empty() {return A.isEmpty();}
}

1.
在Java中，Queue 是一个接口，而 LinkedList 是实现了 Queue 接口的一个具体类。
所以
queue1 = new LinkedList<Integer>();
queue2 = new LinkedList<Integer>();

   这点和前面的栈不同

   2.
   栈和队列的方法
   这里是 Queue 和 Stack 接口中一些常用方法的对比：

Queue 接口:

boolean offer(E e): 将元素插入队列，如果成功则返回 true，如果队列满则返回 false。
E poll(): 移除并返回队列头部的元素，如果队列为空则返回 null。
E remove(): 移除并返回队列头部的元素，如果队列为空则抛出 NoSuchElementException。
   peek()
   在Java中，peek() 方法是 Queue 接口的一部分，它用于获取队列头部的元素，但不从队列中移除它。这个方法通常用于查看队列的第一个元素而不改变队列的状态。

Stack 接口 (继承自 Vector 类):

E push(E item): 将元素压入栈顶。
E pop(): 移除并返回栈顶元素。
E peek(): 返回栈顶元素，但不移除它。

有效的括号

！！！！！！

这个题目看了好久，还是迷糊

特别是对占位符？的理解

例如出现

（））的情况的时候，如果没有占位符在栈中，就是报出异常

20. 有效的括号 - 力扣（LeetCode）

class Solution {private static final Map<Character,Character> map = new HashMap<Character,Character>(){{put('{','}'); put('[',']'); put('(',')'); put('?','?');}};public boolean isValid(String s) {if(s.length() > 0 && !map.containsKey(s.charAt(0))) return false;LinkedList<Character> stack = new LinkedList<Character>() {{ add('?'); }};for(Character c : s.toCharArray()){if(map.containsKey(c)) stack.addLast(c);else if(map.get(stack.removeLast()) != c) return false;}return stack.size() == 1;}
}

20. 有效的括号 - 力扣（LeetCode）

这个题解没有用到?占位符

解法一

class Solution {public boolean isValid(String s) {if(s.length()%2!=0){return false;}Map<Character,Character> map=new HashMap<>();map.put('(',')');map.put('{','}');map.put('[',']');LinkedList<Character> stack=new LinkedList<Character>();for(char c:s.toCharArray()){if(map.containsKey(c)) stack.add(map.get(c));else if(stack.isEmpty()||stack.removeLast()!=c)return false;}return stack.isEmpty();}
}

解法二

class Solution {public boolean isValid(String s) {if(s.length()%2!=0){return false;}Map<Character,Character> map=new HashMap<>();map.put(')','(');map.put('}','{');map.put(']','[');LinkedList<Character> stack=new LinkedList<Character>();for(char c:s.toCharArray()){if(!map.containsKey(c)) stack.add(c);else if(stack.isEmpty()||stack.removeLast()!=map.get(c))return false;}return stack.isEmpty();}
}

总结：其实不管map里面谁是键，谁是值，对于栈的思路就是先入栈再出栈，因为出现左括号才会入栈，因为出现右括号才会出栈！

坚持这个思路

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

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

class Solution{public String removeDuplicates(String s) {StringBuilder str=new StringBuilder();for(char c:s.toCharArray()){if(str.length()!=0&&str.charAt(str.length()-1)==c){str.deleteCharAt(str.length()-1);}else{str.append(c);}}return str.toString();}
}

StringBuffer 是 Java 中的一个类，它代表了一个可变的字符序列。虽然它的名字中有 "Buffer" 这个词，但它并不是一个栈结构。StringBuffer 提供了线程安全的操作，可以被多个线程同时使用而不会出现线程安全问题。

StringBuffer 的底层结构实际上是一个可变大小的字符数组，它提供了多种方法来操作这个字符数组，比如 append、insert、delete、replace 等。这些方法允许你在 StringBuffer 对象中添加、插入、删除或替换字符。

2.
StringBuilder 是 Java 中的一个类，它用于创建可变的字符串。与 StringBuffer 类似，StringBuilder 也提供了一个可变大小的字符序列，允许你通过各种方法来修改字符串，如 append、insert、delete、replace 等。

不过，与 StringBuffer 的主要区别在于 StringBuilder 不是线程安全的。这意味着它在单线程环境中性能更好，因为它不需要处理同步操作。如果你确定你的代码只会在单线程环境中使用，或者你可以自己管理同步，那么 StringBuilder 通常是更好的选择。

StringBuilder 的底层结构也是一个可变大小的字符数组，但它不像 StringBuffer 那样提供线程安全的保证。在多线程环境中使用 StringBuilder 可能会导致不可预知的结果，因为多个线程可能会同时修改同一个 StringBuilder 实例。

所以本题目中用哪一个都一样

逆波兰表达式求值

这个题目就是看着吓人

150. 逆波兰表达式求值 - 力扣（LeetCode）

class Solution {public int evalRPN(String[] tokens) {Stack<Integer> num=new Stack<>();Integer p1,p2;for(String c:tokens){switch(c){case "+":p2=num.pop();p1=num.pop();num.push(p1+p2);break;case "-":p2=num.pop();p1=num.pop();num.push(p1-p2);break; case "*":p2=num.pop();p1=num.pop();num.push(p1*p2);break;    case "/":p2=num.pop();p1=num.pop();num.push(p1/p2);break;  default:num.push(Integer.valueOf(c));break;}}return num.pop();}
}

最小栈

155. 最小栈 - 力扣（LeetCode）

class MinStack {Stack<Integer> stack;Stack<Integer> min_stack;public MinStack() {stack=new Stack<>();min_stack=new Stack<>();}public void push(int val) {stack.push(val);if(min_stack.isEmpty()|| min_stack.peek()>=val){min_stack.push(val);}}public void pop() {if(stack.pop().equals(min_stack.peek())){min_stack.pop();}}public int top() {return stack.peek();}public int getMin() {
return min_stack.peek();}
}

滑动窗口最大值

队列和双指针问题结合到一起

239. 滑动窗口最大值 - 力扣（LeetCode）

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {
if(nums.length==0 ||k==0)
return new int[0];
int[] res=new int[nums.length-k+1];
Deque<Integer> deque=new LinkedList<>();
for(int l=1-k,r=0;r<nums.length;l++,r++){if(l>0&&deque.peekFirst()==nums[l-1])
deque.removeFirst();while(!deque.isEmpty()&&deque.peekLast()<nums[r])
deque.removeLast();deque.addLast(nums[r]);if(l>=0){res[l]=deque.peekFirst();
}
}
return res;}
}

前K个高频元素

347. 前 K 个高频元素 - 力扣（LeetCode）

看这个题解的思路，不用看代码，代码和代码注释都有问题

class Solution {public int[] topKFrequent(int[] nums, int k) {// 使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值HashMap<Integer,Integer> map = new HashMap();for(int num : nums){map.put(num,map.getOrDefault(num,0) + 1);}// 遍历map，用大根保存频率最大的k个元素PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {@Overridepublic int compare(Integer a, Integer b) {return map.get(a) - map.get(b);}});for (Integer key : map.keySet()) {if (pq.size() < k) {pq.add(key);} else if (map.get(key) > map.get(pq.peek())) {pq.remove();pq.add(key);}}// 取出大根堆中的元素int[] res=new int[k];int index=0;while (!pq.isEmpty()) {res[index++]=pq.remove();}return res;}
}