用栈实现队列
栈的特性：先进后出
队列特性：先进先出
因此利用两个栈实现一个队列，一个为输入栈，另一个为输出栈
push的时候就直接进入输入栈
pop的时候若输出栈为空则需先把进栈数据全部输入来，然后再出栈；若输出栈非空，则直接出栈；
当两个栈均为空时证明队列已空
import java.util.Stack;
public class MyQueue {
// 输入栈
Stack<Integer> stackIn;
// 输出栈
Stack<Integer> stackOut;
public MyQueue() {
stackIn = new Stack<>();
stackOut = new Stack<>();
}
// 输入栈直接push
public void push(int x) {
stackIn.push(x);
}
// 队列头元素出列并移除
public int pop() {
// 输出栈为空
if(stackOut.isEmpty()) {
// 把输入栈中的全部数据导入输出栈中
while (!stackIn.isEmpty()) {
stackOut.push(stackIn.pop());
}
}
// 返回输出栈中的顶部元素即队头元素
return stackOut.pop();
}
// 只获取队列头元素值，并不移除
public int peek() {
if(stackOut.isEmpty()) {
while (!stackIn.isEmpty()) {
stackOut.push(stackIn.pop());
}
}
return stackOut.peek();
}
public boolean empty() {
return stackIn.isEmpty() && stackOut.isEmpty();
}
}
用队列实现栈
- 双队列实现栈
import java.util.LinkedList;
import java.util.Queue;
public class MyStack {
// queue1模仿栈
Queue<Integer> queue1;
// queue2 做辅助队列
Queue<Integer> queue2;
public MyStack() {
queue1 = new LinkedList<Integer>();
queue2 = new LinkedList<Integer>();
}
public void push(int x) {
// 新元素先放入辅助队列中
queue2.offer(x);
// 当queue1中存在元素时，全部出队加入queue2中
while (!queue1.isEmpty()) {
queue2.offer(queue1.poll());
}
// 交换两队列，确保queue2每次开始都是空队列，而queue1的队头刚好就是栈顶元素
Queue<Integer> temp = queue1;
queue1 = queue2;
queue2 = temp;
}
// 此后每次出栈，获取栈顶元素或判空都只需要操作queue1即可
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();
*/- 单队列实现栈
import java.util.LinkedList;
import java.util.Queue;
public class MyStack {
Queue<Integer> queue;
public MyStack() {
queue = new LinkedList<Integer>();
}
public void push(int x) {
// 每次都获取当前队列的长度
int size = queue.size();
// 新元素入队
queue.offer(x);
// 然后除队尾的新元素外，所有元素出队再入队，重新排列，这样队头就是栈顶元素
while (size > 1) {
queue.offer(queue.poll());
size--;
}
}
public int pop() {
return queue.poll();
}
public int top() {
return queue.peek();
}
public boolean empty() {
return queue.isEmpty();
}
}有效的括号
三种可能不匹配的情况：
- 左方向有多余括号
- 右方向有多余括号
- 括号类型不匹配
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
char[] eachChar = s.toCharArray();
for (int i = 0; i < s.length(); i++) {
// 遍历到左括号，把相应右括号入栈
if (eachChar[i] == '(') {
stack.push(')');
} else if (eachChar[i] == '{') {
stack.push('}');
} else if (eachChar[i] == '[') {
stack.push(']');
}
// 当字符串尚未被遍历完而栈为空时，说明右方向有多余括号
// 当栈顶元素与当前遍历字符不等时，说明有括号类型不匹配
else if (stack.isEmpty() || stack.peek() != eachChar[i]) {
return false;
} else {
// 匹配到相应的左括号，相应的右括号出栈
stack.pop();
}
}
// 遍历完毕后，栈也应该为空
return stack.isEmpty();
}删除字符串中的所有相邻重复项
解题思想：利用栈先入后出的特性
当栈为空或栈顶元素和当前遍历的字符不相等时，则入栈
当栈顶元素和当前遍历的字符相等时，则出栈
最后栈中所剩元素即删除相邻重复项后所剩下的字符串
public String removeDuplicates(String s) {
Stack<Character> stack = new Stack<>();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
// 栈空或不等，入栈
if (stack.isEmpty() || s.charAt(i) != stack.peek()) {
stack.push(s.charAt(i));
} else {
// 相邻元素相同，出栈，往后走
stack.pop();
}
}
// 栈中所剩则所求
while (!stack.isEmpty()) {
sb.append(stack.pop());
}
return sb.reverse().toString();
}逆波兰表达式求值
class Solution {
public int evalRPN(String[] tokens) {
// 利用栈的特性
Stack<String> stack = new Stack<>();
// 循环遍历数组内容
for (String token : tokens) {
// 当栈为空或数组元素是数字时，入栈
if (stack.isEmpty() || !"+-*/".contains(token)) {
stack.push(token);
}
// 数组元素是运算符时，栈中数字出栈，结合运算符进行运算，结果入栈
else if ("+-*/".contains(token)) {
int first = Integer.parseInt(stack.pop());
int second = Integer.parseInt(stack.pop());
int result = Integer.MAX_VALUE;
switch (token) {
case "+":
result = second + first;
break;
case "-":
result = second - first;
break;
case "*":
result = second * first;
break;
case "/":
result = second / first;
break;
}
stack.push(String.valueOf(result));
}
}
// 最后栈中所剩即结果
return Integer.parseInt(stack.pop());
}
}滑动窗口最大值
注意队列中存储的是下标值，利用双端队列，两边都可进出的特性
思路参考：
遍历给定数组中的元素，如果队列不为空且当前考察元素大于等于队尾元素，则将队尾元素移除。直到，队列为空或当前考察元素小于新的队尾元素；
当队首元素的下标小于滑动窗口左侧边界left时，表示队首元素已经不在滑动窗口内，因此将其从队首移除。
由于数组下标从0开始，因此当窗口右边界right+1大于等于窗口大小k时，意味着窗口形成。此时，队首元素就是该窗口内的最大值。
import java.util.LinkedList;
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
// 滑动窗口的个数
int[] res = new int[nums.length - k + 1];
// 双端队列
LinkedList<Integer> queue = new LinkedList<>();
// 右边界遍历
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;
// 说明队头元素不在滑动窗口内了，元素出队
if(queue.peekFirst() < left) {
queue.removeFirst();
}
// 右边界到达位置，说明窗口形成，此时队头索引对应的元素即窗口内最大值
if (right + 1 >= k) {
res[left] = nums[queue.peekFirst()];
}
}
return res;
}
}前 K 个高频元素
利用优先级队列实现
补充知识：
优先级队列，其实就是一个披着队列外衣的堆，其底层实现就是利用了堆的数据结构
关于
Comparator接口说明: * 返回负数，形参中第一个参数排在前面；返回正数，形参中第二个参数排在前面 * 对于队列：排在前面意味着往队头靠 * 对于堆（使用PriorityQueue实现）：从队头到队尾按从小到大排就是最小堆（小顶堆）， * 从队头到队尾按从大到小排就是最大堆（大顶堆）--->队头元素相当于堆的根节点
import java.util.HashMap;
import java.util.PriorityQueue;
class Solution {
public int[] topKFrequent(int[] nums, int k) {
// 建立map用于存储每个数的频率次数，key为数组中的值，value为对应出现的次数（即频率）
HashMap<Integer, Integer> map = new HashMap<>();
for(int num : nums) {
if(map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}
}
// 优先级队列，默认是小根堆
// 此处优先队列默认排序的是key（因为自己存进去的是key），因此需要重写确定自己需要的排序依据，此处重写后排序的是value
PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> map.get(o1) - map.get(o2));
// 建堆操作
for (Integer key : map.keySet()) {
// 当队列长度小于指定的k个数时，可以继续入队（即可以加入堆中）
if (queue.size() < k) {
queue.add(key);
}
// 当对应的频率次数大于队列的队头元素（即堆顶元素）时，堆顶元素弹出，新元素入队
else if(map.get(key) > map.get(queue.peek())) {
queue.remove();
queue.add(key);
}
}
// 最终队列中所剩的就是频率最大的前k个
int[] result = new int[queue.size()];
for (int i = 0; i < result.length; i++) {
result[i] = queue.poll();
}
return result;
}
}
