算法跟练第九弹—

文章目录

part01 用栈实现队列
part02 用队列实现栈
part03 有效的括号
part04 删除字符串中的所有相邻重复项
归纳
- 栈
- 队列

跟着代码随想录刷题的第九天。

代码随想录链接：代码随想录

part01 用栈实现队列

题目链接：232.用栈实现队列

代码：

java">class MyQueue {Stack<Integer> sIn = new Stack<>();Stack<Integer> sOut = new Stack<>();public MyQueue() {}public void push(int x) {sIn.push(x);}public int pop() {if(sOut.empty()){while(!sIn.empty()){sOut.push(sIn.pop());}}int result = sOut.pop();return result;}public int peek() {if(sOut.empty()){while(!sIn.empty()){sOut.push(sIn.pop());}}int result = sOut.peek();return result;}public boolean empty() {if(sIn.empty()&&sOut.empty())return true;return false;}
}

题解：本题的关键在于队列是先进先出，栈是先进后出，要用栈来实现队列的功能就需要用两个栈，一个正常存入数据，另一个存入第一个栈出来的数据，这样就能实现队列的功能。值得注意的是，只有当第二个数组为空时，第一个数组的数值再存入到第二个数组当中

part02 用队列实现栈

题目链接：225. 用队列实现栈

代码：

java">class MyStack {Queue<Integer> q1 = new LinkedList<>();Queue<Integer> q2 = new LinkedList<>();public MyStack() {}public void push(int x) {q2.add(x);while(!q1.isEmpty()){q2.add(q1.poll());}Queue<Integer> tmpq = q1;q1 = q2;q2 = tmpq;}public int pop() {return q1.poll();}public int top() {return q1.peek();}public boolean empty() {return q1.isEmpty();}
}

题解：队列实现栈有一个问题，在于把第一个队列的数值输出到另个队列之后，结果还是先进先出，没有任何改变。所以本题就把push进来的值放到队列2中，再把队列1中的值放到队列2中，这样就实现了后进先出

part03 有效的括号

题目链接：20. 有效的括号

代码：

java">class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for(int i = 0;i<s.length();i++){if(s.charAt(i)==')'||s.charAt(i)=='}'||s.charAt(i)==']'){   if(stack.empty())return false;if(stack.peek()==makenew(s.charAt(i))){stack.pop();continue;}return false;}stack.push(s.charAt(i));}if(stack.empty())return true;elsereturn false;}public char makenew(char a){char b= ' ';switch(a){case ')':b =  '(';break;case'}':b =  '{';break;case']':b =  '[';}return b;}}

题解：本题采用的是栈来实现。由于所有的括号都是一一对应的输入，所以，当遇到右括号的时候，比较栈顶元素是不是左括号，如果是的话，就弹出，否则就返回false。

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

题目链接：1047. 删除字符串中的所有相邻重复项

代码：

java">class Solution {public String removeDuplicates(String s) {Stack<Character> stack = new Stack<>();for(int i = 0;i<s.length();i++){if(!stack.empty()&&s.charAt(i)==stack.peek()){stack.pop();continue;}stack.push(s.charAt(i));}StringBuilder a = new StringBuilder();while(!stack.empty())a.append(stack.pop());a.reverse();return new String(a);}
}

题解：本题和上题解题思路基本一致，用栈来求解。当遇到和当前字符相同的，就出栈，反之就进栈，继续比较。

归纳

栈

参考来源：https://blog.csdn.net/2201_75437633/article/details/135733411

定义栈的方法

1、数组

java">public class ArrayStack {private int[] stack;private int top;public ArrayStack(int capacity) {stack = new int[capacity];top = -1;}public void push(int item) {if (top == stack.length - 1) {throw new IllegalStateException("Stack is full");}stack[++top] = item;}public int pop() {if (isEmpty()) {throw new IllegalStateException("Stack is empty");}return stack[top--];}public int peek() {if (isEmpty()) {throw new IllegalStateException("Stack is empty");}return stack[top];}public boolean isEmpty() {return top == -1;}
}

2、链表

java">public class LinkedListStack {private Node top;private class Node {int data;Node next;public Node(int data) {this.data = data;this.next = null;}}public LinkedListStack() {top = null;}public void push(int item) {Node newNode = new Node(item);if (isEmpty()) {top = newNode;} else {newNode.next = top;top = newNode;}}public int pop() {if (isEmpty()) {throw new IllegalStateException("Stack is empty");}int item = top.data;top = top.next;return item;}public int peek() {if (isEmpty()) {throw new IllegalStateException("Stack is empty");}return top.data;}public boolean isEmpty() {return top == null;}
}

3、栈，可以直接调用下面的函数

java">Stack<Object> stack = new Stack<>();

栈常用的函数：

入栈：push()
出栈：pop()//会返回栈顶元素
获取栈顶元素：peek()
判断栈是否为空：empty()
查找元素在栈中的位置，由栈底到栈顶：serch(Object o)
对当前栈进行清空：clear()

队列

参考来源：https://blog.csdn.net/2201_75437633/article/details/135823215

定义队列的三种方法

LinkedList是Java中常用的双向链表实现，它同时实现了List接口和Queue接口，因此可以被用作队列来进行元素的添加和移除操作。

Queue queue = new LinkedList<>();

ArrayDeque是一种基于数组的双端队列实现，它同样实现了Queue接口，并且在尾部添加和移除元素的操作具有较低的时间复杂度。

Queue queue = new ArrayDeque<>();

PriorityQueue是一个基于优先级堆的无界优先级队列实现，它可以确保每次出队的元素都是队列中优先级最高的元素。

Queue queue = new PriorityQueue<>();

优先级队列的例子：

java">Queue<Integer> queue = new PriorityQueue<>();
queue.offer(5); // 入队
queue.offer(3);
int element = queue.poll(); // 出队
System.out.println(element); // 输出：3