栈:
java.util.Stack：使用动态数组实现。java.util.Deque：可以使用链表或动态数组实现。
队列:
java.util.LinkedList：使用链表实现。java.util.ArrayDeque：使用动态数组实现。java.util.PriorityQueue：使用堆（数组实现的二叉堆）实现。
1、用栈实现队列
https://leetcode.cn/problems/implement-stack-using-queues/description/
两个栈即可。
class MyQueue {
public Stack<Integer> in;
public Stack<Integer> out;
public MyQueue() {
in = new Stack<Integer>();
out = new Stack<Integer>();
}
public void inpushput(){
if(out.empty()){
while(!in.empty())
out.push(in.pop());
}
}
public void push(int x) {
in.push(x);
inpushput();
}
public int pop() {
inpushput();
return out.pop();
}
public int peek() {
inpushput();
return out.peek();
}
public boolean empty() {
if(in.empty()&&out.empty())
{
return true;
}
return false;
}
}
/**
* 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();
*/2、队列实现栈
https://leetcode.cn/problems/implement-stack-using-queues/description/
class MyStack {
Queue<Integer> queue1;
Queue<Integer> queue2;
/** Initialize your data structure here. */
public MyStack() {
queue1 = new LinkedList<Integer>();
queue2 = new LinkedList<Integer>();
}
/** Push element x onto stack. */
public void push(int x) {
queue2.offer(x);
while (!queue1.isEmpty()) {
queue2.offer(queue1.poll());
}
Queue<Integer> temp = queue1;
queue1 = queue2;
queue2 = temp;
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return queue1.poll();
}
/** Get the top element. */
public int top() {
return queue1.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue1.isEmpty();
}
}3、有效的括号
https://leetcode.cn/problems/valid-parentheses/description/
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
int n=s.length();
if(n%2!=0)
return false;
for(int i=0;i<n;i++){
if(stack.size()>0){
if(s.charAt(i)==')'){
if(stack.peek()=='(') {
stack.pop();
continue;
}
}
else if(s.charAt(i)==']'){
if(stack.peek()=='['){
stack.pop();
continue;}
}
else if(s.charAt(i)=='}'){
if(stack.peek()=='{'){
stack.pop();continue;}
}
}
stack.push(s.charAt(i));
}
return stack.isEmpty();
}
}4、删除重复
①堆栈
class Solution {
public String removeDuplicates(String s) {
Stack<Character> stack = new Stack<>();
for(int i=0;i<s.length();i++){
if(stack.size()>0){
if(s.charAt(i)==stack.peek()){
stack.pop();
continue;
}
}
stack.push(s.charAt(i));
}
StringBuilder sb=new StringBuilder();
int size = stack.size();
for(int i=0;i<size;i++){
sb.append(stack.peek());
stack.pop();
}
sb.reverse();
return sb.toString();}
}②用StringBuilder来代替堆栈
class Solution {
public String removeDuplicates(String s) {
StringBuilder stringBuilder=new StringBuilder();
int count=-1;
for(int i=0;i<s.length();i++){
if(count>=0&& stringBuilder.charAt(count)==s.charAt(i)){
stringBuilder.deleteCharAt(count--);
}
else {
stringBuilder.append(s.charAt(i));
count++;
}
}
return stringBuilder.toString();
}
}③双指针
class Solution {
public String removeDuplicates(String s) {
char[] c = s.toCharArray();
int slow=0;
int fast=0;
for (int i = 0; i <s.length() ; i++) {
c[slow]=c[fast];
if(slow>0&&c[slow]==c[slow-1]){
slow--;
}
else {
slow++;
}
fast++;
}
return new String(c,0,slow);
}
}5、逆波兰表达式
https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/
注意字符串要用equals进行对比，用==进行比较的是内存地址，而不是具体的值
Integer.valueOf 把 字符串转为int类型。class Solution {
public int evalRPN(String[] tokens) {
int n = tokens.length;
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; i++) {
if (tokens[i].equals("+") || tokens[i].equals("-")
|| tokens[i].equals("*") || tokens[i].equals("/")) {
int s2 = stack.pop(); // 从栈中弹出第一个操作数
int s1 = stack.pop(); // 从栈中弹出第二个操作数
if (tokens[i].equals("+"))
stack.push(s1 + s2);
if (tokens[i].equals("-"))
stack.push(s1 - s2);
if (tokens[i].equals("*"))
stack.push(s1 * s2);
if (tokens[i].equals("/"))
stack.push(s1 / s2);
} else {
stack.push(Integer.parseInt(tokens[i])); // 将数字压入栈中
}
}
return stack.pop(); // 返回最后栈中的结果
}
}
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new LinkedList();
for (String s : tokens) {
if ("+".equals(s)) { // leetcode 内置jdk的问题，不能使用==判断字符串是否相等
stack.push(stack.pop() + stack.pop()); // 注意 - 和/ 需要特殊处理
} else if ("-".equals(s)) {
stack.push(-stack.pop() + stack.pop());
} else if ("*".equals(s)) {
stack.push(stack.pop() * stack.pop());
} else if ("/".equals(s)) {
int temp1 = stack.pop();
int temp2 = stack.pop();
stack.push(temp2 / temp1);
} else {
stack.push(Integer.valueOf(s));
}
}
return stack.pop();
}
}6、前k个高频元素
优先级队列 大顶堆小顶堆
https://leetcode.cn/problems/top-k-frequent-elements/description/
class Solution {
public int[] topKFrequent(int[] nums, int k) {
//遍历数组，存放num 和其对应的次数
Map<Integer,Integer> map=new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num,0)+1);
}
//小顶堆
PriorityQueue<int[]> pq=new PriorityQueue<>((pair1,pair2)->(pair1[1]-pair2[1]));
//遍历map 维护大小为k的小顶堆
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if(pq.size()<k)
pq.add(new int[]{entry.getKey(),entry.getValue()});
else{
//只有cnt大于当前小顶堆的栈顶时 才添加
if(entry.getValue()> pq.peek()[1]){
pq.poll();
pq.add(new int[]{entry.getKey(),entry.getValue()});
}
}
}
int[] res=new int[k];
for(int i=0;i<k;i++){
res[i]=pq.poll()[0];
}
return res;
}
}7.滑动窗口最大值
单调队列
https://leetcode.cn/problems/sliding-window-maximum/description/
class MyQueue {
Deque<Integer> deque = new LinkedList<>();
//弹出元素时，比较当前要弹出的数值是否等于队列出口的数值，如果相等则弹出
//同时判断队列当前是否为空
void poll(int val) {
if (!deque.isEmpty() && val == deque.peek()) {
deque.poll();
}
}
//添加元素时，如果要添加的元素大于入口处的元素，就将入口元素弹出
//保证队列元素单调递减
//比如此时队列元素3,1，2将要入队，比1大，所以1弹出，此时队列：3,2
void add(int val) {
while (!deque.isEmpty() && val > deque.getLast()) {
deque.removeLast();
}
deque.add(val);
}
//队列队顶元素始终为最大值
int peek() {
return deque.peek();
}
}
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length == 1) {
return nums;
}
int len = nums.length - k + 1;
//存放结果元素的数组
int[] res = new int[len];
int num = 0;
//自定义队列
MyQueue myQueue = new MyQueue();
//先将前k的元素放入队列
for (int i = 0; i < k; i++) {
myQueue.add(nums[i]);
}
res[num++] = myQueue.peek();
for (int i = k; i < nums.length; i++) {
//滑动窗口移除最前面的元素，移除是判断该元素是否放入队列
myQueue.poll(nums[i - k]);
//滑动窗口加入最后面的元素
myQueue.add(nums[i]);
//记录对应的最大值
res[num++] = myQueue.peek();
}
return res;
}
}