一、用栈去实现队列
1.整理思路
栈的特点：先进后出
队列的特点：先进先出
我们要用栈的先进后出，来模拟实现队列的先进后出。我们需要借助两个栈去实现，分别叫做栈1和栈2。
栈1主要是用来存储数据的，我们将要插入的数据全部存放在栈1当中。
栈2主要是用来获取数据的:
首先判断栈2当中是否有数据，如果有，怎直接返回栈2的顶部元素。
如果没有，则将栈1当中的数据全部放入到栈2当中。
2.代码实现
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
//入栈函数
public void push(int num) {
stack1.push(num); //要往栈中压入什么就直接用栈的push方法就好了
}
//出栈函数
public Integer pop() {
Integer re=null;
if(!stack2.empty()){ // 如果栈2不是空的，那么把最上面那个取出来
re=stack2.pop();
}else{
//如果栈2是空的，就把栈1里的数一个个取出来，放到栈2里
while(!stack1.empty()){
re=stack1.pop();
stack2.push(re);
}
//栈2里有数之后，再次把里面的数取出来
if(!stack2.empty()){
re=stack2.pop();
}
}
return re;
}
public static void main(String[] args) {
Solution solution = new Solution();
solution.push(1);
solution.push(2);
solution.push(3);
solution.push(4);
System.out.println(solution.pop());
System.out.println(solution.pop());
System.out.println(solution.pop());
System.out.println(solution.pop());
}
}
二、用队列实现栈
1.整理思路
栈的特点：先进后出
队列的特点：先进先出
这里有两种实现方式：第一种是：用两个队列实现一个栈。第二种是用一个队列实现一个栈
2.两个队列实现一个栈
基本思路：使用两个队列，其中一个队列用来存放元素，另一个用来做辅助输出
1.入栈的时候，入到不为空的队列，刚开始都为空指定入到一个队列
2.入栈的时候，找到不为空的队列，出size-1个元素到另一个队列中，剩下的这个元素就是出栈的元素
public class QueueToStack<E> {
private Queue<E> que1 = new LinkedList<>(); // 存放栈的元素
private Queue<E> que2 = new LinkedList<>(); // 做一个辅助操作
public void push(E e) {
this.que1.offer(e);
}
public E pop() {
// 从que1出队，把最后一个出队的元素返回
E data = null;
/**
* 把que1里面的所有元素出队，放入que2里面，
* 然后把que1最后一个出队的元素直接返回，不用放入que2
*/
while (!que1.isEmpty()) {
data = que1.poll(); // poll() 从que1取出数据
// 当取值取到最后一个的时候，返回为空 ，while循环结束
if(que1.isEmpty()){
break;
}
que2.offer(data); //将取出来的数据放到que2当中
}
// 获取该出栈的元素以后，再把que2的元素再放入que1里面
while(!que2.isEmpty()){
que1.offer(que2.poll());
}
return data;
}
3.一个队列实现一个栈
基本思路：使用两个队列，其中一个队列用来存放元素，另一个用来做辅助输出
1.入栈的时候，入到不为空的队列，刚开始都为空指定入到一个队列
2.入栈的时候，找到不为空的队列，出size-1个元素到重新插入到队列当中，剩下的这个元素就是出栈的元素
public class Stack<E> {
private Queue<E> que1 = new LinkedList<>(); // 存放栈的元素
public void push(E e) {
this.que1.offer(e);
}
public E pop() {
int size = que1.size(); //获取队列当中的元素数量
size = size - 1;
while(size>0) {
que1.offer(que1.poll());
size--;
}
return que1.poll();
}
}
三、判断元素出栈入栈的合法性
1.题目描述
判断元素出栈，入栈顺序的合法性如：
入栈的序列（1,2,3,4,5），出栈序列为（4,5,3,2,1）是合法序列
入栈的序列（1,2,3,4,5），出栈序列为（1,5,3,2,4）是不合法序列
2.解题思路
1）我们可以用数组来进行存储入栈和出栈的序列，一个数组村的是入栈的序列另一个数组村的是出栈的序列。
2）用一个辅助栈，将入栈序列的第一个元素压栈，看是否和出栈序列的第一个元素相等。
3）如果相等则将辅助栈中的元素弹出去，继续比较入栈序列的下一个元素和出栈序列的下一个元素是否相等。
4）如果不相等继续将下一个入栈序列的元素压栈并且判断它是否与出栈序列中的当前元素匹配
若入栈序列遍历完毕，辅助栈为空 说明入栈序列中的元素和出栈序列中的元素匹配，返回true
若辅助栈不为空的话，说明不匹配，返回false
3.代码实现
public class QueueToStack{
public static boolean validateStackSequences(int[] pushed, int[] popped) {
Stack<Integer> stack = new Stack<>();
int i = 0;
for(int num : pushed) {
stack.push(num); // num 入栈
while(!stack.isEmpty() && stack.peek() == popped[i]) { // 循环判断与出栈
stack.pop();
i++;
}
}
return stack.isEmpty();
}
public static void main(String[] args) {
int[] pushed = new int[]{1,2,3,4,5};
int[] popped = new int[]{5,4,3,2,1};
System.out.println(QueueToStack.validateStackSequences(pushed,popped));
}
}
四、返回栈的最小值时间是O(1)
1.题目描述
实现一个栈，要求实现出栈，入栈，Min(返回最小值的操作)的时间复杂度为o(1)
2.解法分析
使用两个栈，一个栈s,保存push的值，另一个栈作为辅助栈，保存当前最小值
push : 栈s插入值push(data),辅助栈min，如果为空或者插入的值data小于等于辅助栈的栈顶元素，
辅助栈也插入data。
pop：栈s pop操作，辅助栈中的栈顶元素如果等于栈s的栈顶的话也执行pop操作。
3.代码实现
public class StackMin {
static Stack<Integer> num = new Stack<>();
static Stack<Integer> min = new Stack<>();
// 入栈
public static void push(Integer data){
// 首先数据栈入栈
num.push(data);
//入栈 -----》辅助栈为空，或者有更小的值，将其存入辅助栈
if (min.empty() || data<=min.peek()){
min.push(data);
}
}
// 出栈
public static int pop(){
//数据栈当前取出的元素是栈中最小的，则辅助栈也要弹出此元素
if (num.peek() == min.peek()){
min.pop();
}
return num.pop();
}
// 取出最小值
public static void min(){
//取当前最小元素
if (!min.empty()){
System.out.println(min.peek());
}
}
public static void main(String[] args) {
StackMin.push(4);
StackMin.push(3);
StackMin.push(5);
StackMin.push(2);
StackMin.min();
StackMin.pop();
StackMin.min();
}
}
五、用一个数组实现两个栈
1.题目描述
用一个数组实现两个栈
2.解法分析
1.初始化两个下标变量分别指向数组的左右两端
2.左边的下标指示第一个栈，右边的下标指示第二个栈
3.如果需要对第一个栈执行元素入栈操作，那么将元素赋值到左边下标变量指示的位置
4.如果需要对第二个栈执行元素入栈操作，那么将元素赋值到右边下标变量指示的位置
5.第一个栈向右增长，第二个栈向左增长
3.代码实现
**
* 使用一个数组实现两个栈
* 栈和数组综合考察
*/
public class ArrayWithTwoStacks {
/*
元数据数组
*/
private int[] dataArray;
/*
数组容量
*/
private int size;
/*
概念栈StackId=1的栈的指针
*/
private int topOne;
/*
概念栈StackId=1的栈的指针
*/
private int topTwo;
public ArrayWithTwoStacks(int size) {
//两个栈存在的边界条件size>=2
if (size < 2) {
throw new IllegalStateException("size < 2 is no persmissible");
}
dataArray = new int[size];
this.size = size;
topOne = -1;
topTwo = size;
}
/**
* 入栈操作
*
* @param stackId
* @param data
*/
public void push(int stackId, int data) {
//是否满栈
if (topOne + 1 == topTwo) {
throw new IllegalStateException("Array is full!");
//可以参入数组扩容操作，对当前数组现有元素进行重编，初始化栈指针
}
if (stackId == 1) {
dataArray[++topOne] = data;
} else if (stackId == 2) {
dataArray[--topTwo] = data;
} else {
return;
}
}
/**
* 出栈
*
* @param stackId
* @return
*/
public int pop(int stackId) {
if (stackId == 1) {
if (topOne == -1) {
throw new EmptyStackException();
}
return dataArray[topOne--];
} else {
if (topTwo == size) {
throw new EmptyStackException();
}
return dataArray[topTwo++];
}
}
/**
* 栈顶元素
*
* @param stackId
* @return
*/
public int top(int stackId) {
if (stackId == 1) {
if (topOne == 1) {
throw new EmptyStackException();
}
return dataArray[topOne];
} else {
if (topTwo == this.size) {
throw new EmptyStackException();
}
return dataArray[topTwo];
}
}
/**
* 栈非空
*
* @param stackId
* @return
*/
public boolean isEmpty(int stackId) {
if (stackId == 1) {
return topOne == -1;
} else if (stackId == 2) {
return topTwo == this.size;
} else {
return true;
}
}
}
六、有效的括号
1.题目要求
https://leetcode.cn/problems/valid-parentheses/
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 注意空字符串可被认为是有效字符串。
2.栈模拟三种不匹配的情况
①：第一种情况，字符串里左方向的括号多余了 ，所以不匹配。
已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false
②：第二种情况，括号没有多余，但是 括号的类型没有匹配上。
遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false
③：第三种情况，字符串里右方向的括号多余了，所以不匹配。
3.代码实现
class Solution {
public boolean isValid(String s) {
Deque<Character> deque = new LinkedList<>();
char ch;
for (int i = 0; i < s.length(); i++) {
ch = s.charAt(i);
//碰到左括号，就把相应的右括号入栈
if (ch == '(') {
deque.push(')');
}else if (ch == '{') {
deque.push('}');
}else if (ch == '[') {
deque.push(']');
} else if (deque.isEmpty() || deque.peek() != ch) {
return false;
}else {//如果是右括号判断是否和栈顶元素匹配
deque.pop();
}
}
//最后判断栈中元素是否匹配
return deque.isEmpty();
}
}
七、删除字符串中所有相邻的重复项
1.题目要求
https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/
2.解题思路
1.多组相邻重复项，我们无论先删除哪一项，都不会影响最终结果。
2.删除当前项是需要拿上一项出来对比的，所以我们需要用临时栈存放之前的内容。
3.当前项和栈顶一致，弹出栈顶抵消即可。若不一致，压入栈留存，供后续使用。
3.代码实现
public String removeDuplicates(String S) {
Stack<Character> st = new Stack<>();
for (int i = 0; i < S.length(); i++) {
if (!st.empty() && S.charAt(i) == st.peek()) {
st.pop();
} else {
st.add(S.charAt(i));
}
}
StringBuilder res = new StringBuilder();
for (Character c : st) {
res.append(c);
}
return res.toString();
}
八、逆波兰表达式求值
1.题目描述
https://leetcode.cn/problems/evaluate-reverse-polish-notation/
2.什么是逆波兰表达式
其实逆波兰表达式就是一种后缀表达式，后缀表达式是用来方便计算机来做运算的一种表达式。那我们首先先来了解一下逆波兰表达式！
首先来看一个正常的表达式：（1+2） * （3+4）
我们将其转换为二叉树的表现形式：
所谓的后缀表达式其实就是这颗二叉树的后序遍历，后序遍历的顺序是：左右中
那么既可以得出后缀表达式：12+34+*
而如果我们采用中序遍历：1+23+4 —》显然这样做我们需要加()，就成了（1+2） （3 +4）。
但是我们如果选择后序表达式就可以直接进行从前到后的遍历，不需要加括号。
因为计算机可以直接从前到后去遍历数据，所以计算机更加偏向于使用后缀表达式来进行计算。
三、如何使用栈计算
- 如果遇到操作数，则将操作数入栈；
- 如果遇到运算符，则将两个操作数出栈，其中先出栈的是右操作数，后出栈的是左操作数，使用运算符对两个操作数进行运算，将运算得到的新操作数入栈。
四、代码实现
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new LinkedList<Integer>();
int n = tokens.length;
for (int i = 0; i < n; i++) {
String token = tokens[i];
if (isNumber(token)) {
stack.push(Integer.parseInt(token));
} else {
int num2 = stack.pop();
int num1 = stack.pop();
switch (token) {
case "+":
stack.push(num1 + num2);
break;
case "-":
stack.push(num1 - num2);
break;
case "*":
stack.push(num1 * num2);
break;
case "/":
stack.push(num1 / num2);
break;
default:
}
}
}
return stack.pop();
}
public boolean isNumber(String token) {
return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
}
}
九、滑动窗口最大值
1.题目描述
https://leetcode.cn/problems/sliding-window-maximum/
2.解题思路
这道题不复杂，难点在于如何在 O(1)O(1) 时间算出每个「窗口」中的最大值，使得整个算法在线性时间完成这道题不复杂，难点在于如何在 O(1)时间算出每个「窗口」中的最大值，使得整个算法在线性时间完成。
1.遍历给定数组中的元素，如果队列不为空且当前考察元素大于等于队尾元素，则将队尾元素移除。直到，队列为空或当前考察元素小于新的队尾元素；
2.当队首元素的下标小于滑动窗口左侧边界left时，表示队首元素已经不再滑动窗口内，因此将其从队首移除。
3.由于数组下标从0开始，因此当窗口右边界right+1大于等于窗口大小k时，意味着窗口形成。此时，队首元素就是该窗口内的最大值。
三、代码实现
public int[] maxSlidingWindow(int[] nums, int k) {
// 窗口个数
int[] res = new int[nums.length - k + 1];
LinkedList<Integer> queue = new LinkedList<>();
// 遍历数组中元素，right表示滑动窗口右边界
for(int right = 0; right < nums.length; right++) {
// 如果队列不为空且当前考察元素大于等于队尾元素，则将队尾元素移除。
// 直到，队列为空或当前考察元素小于新的队尾元素
while (!queue.isEmpty() && nums[right] >= nums[queue.peekLast()]) {
queue.removeLast();
}
// 存储元素下标
queue.addLast(right);
// 计算窗口左侧边界
int left = right - k +1;
// 当队首元素的下标小于滑动窗口左侧边界left时
// 表示队首元素已经不再滑动窗口内，因此将其从队首移除
if (queue.peekFirst() < left) {
queue.removeFirst();
}
// 由于数组下标从0开始，因此当窗口右边界right+1大于等于窗口大小k时
// 意味着窗口形成。此时，队首元素就是该窗口内的最大值
if (right +1 >= k) {
res[left] = nums[queue.peekFirst()];
}
}
return res;
}
十、前k个高频元素
1.题目描述
https://www.bilibili.com/video/BV1Xg41167Lz/?spm_id_from=333.788&vd_source=8f6ce72f707c3f4e097b8deac48b496f
2.解题思路
首先遍历整个数组，并使用哈希表记录每个数字出现的次数，并形成一个「出现次数数组」。找出原数组的前 kk 个高频元素，就相当于找出「出现次数数组」的前 kk 大的值。
最简单的做法是给「出现次数数组」排序。但由于可能有 O(N)O(N) 个不同的出现次数（其中 NN 为原数组长度），故总的算法复杂度会达到 O(N\log N)O(NlogN)，不满足题目的要求。
在这里，我们可以利用堆的思想：建立一个小顶堆，然后遍历「出现次数数组」：
如果堆的元素个数小于 kk，就可以直接插入堆中。
如果堆的元素个数等于 kk，则检查堆顶与当前出现次数的大小。如果堆顶更大，说明至少有 kk 个数字的出现次数比当前值大，故舍弃当前值；否则，就弹出堆顶，并将当前值插入堆中。
遍历完成后，堆中的元素就代表了「出现次数数组」中前 kk 大的值。
3.代码实现
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();
for (int num : nums) {
occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
}
// int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] m, int[] n) {
return m[1] - n[1];
}
});
for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
int num = entry.getKey(), count = entry.getValue();
if (queue.size() == k) {
if (queue.peek()[1] < count) {
queue.poll();
queue.offer(new int[]{num, count});
}
} else {
queue.offer(new int[]{num, count});
}
}
int[] ret = new int[k];
for (int i = 0; i < k; ++i) {
ret[i] = queue.poll()[0];
}
return ret;
}
}
