栈&队列题目

7. 用两个栈实现队列

思路

1. 定义两个栈，push：将node放入stack1
2. pop: 将stack1 中node放入stack2，stack2首位则为要获取的node弹出，之后将stack2剩余node放回stack1

import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        stack1.push(node);
    }
    
    public int pop() {
        while(!stack1.isEmpty()){
            stack2.push(stack1.pop());
        }
        int first = stack2.pop();
        while(!stack2.isEmpty()){
            stack1.push(stack2.pop());
        }
        return first;
    }
}

---

21. 包含min函数的栈

描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
注意：保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法。

思路

用一个栈stack保存数据，用另外一个栈temp保存依次入栈最小的数。

stack中依次入栈 5, 3, 4, 10, 2, 12, 1, 8
则temp依次入栈 5, 3, 3，3, 2, 2, 1, 1

每次入栈的时候，如果入栈的元素比min中的栈顶元素小或等于则入栈，否则用最小元素入栈。

import java.util.*;

public class Solution {

    Stack<Integer> stack = new Stack();
    Stack<Integer> temp = new Stack();

    int min = Integer.MAX_VALUE;
    public void push(int node) {
        stack.push(node);
        if(node < min){
            temp.push(node);
            min = node;
        }
        else
            temp.push(min);
    }

    public void pop() {
        stack.pop();
        temp.pop();
    }

    public int top() {
        int t = stack.pop();
        stack.push(t);
        return t;
    }

    public int min() {
        int m = temp.pop();
        temp.push(m);
        return m;
    }
}

---

22. 栈的压入、弹出顺序

题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。

假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

思路

1. 模拟堆栈操作的过程，将原数列依次压栈。
2. 把栈顶元素与所给出栈队列相比，如果相同则出栈，如果不同则继续压栈，直到原数列中所有数字压栈完毕。
3. 检测栈中是否为空，若空，说明出栈队列可由原数列进行栈操作得到。否则，说明出栈队列不能由原数列进行栈操作得到。

public class Solution {
    public boolean IsPopOrder(int[] pushA, int[] popA) {
        Stack<Integer> stack = new Stack();

        int j = 0;
        for (int i = 0; i < pushA.length; i++) {
            // 1. 将原数列依次压栈
            stack.push(pushA[i]);
            // 2. 栈顶元素与所给出栈队列相比，如果相同则出栈，如果不同则继续压栈
            while (j < popA.length && stack.peek() == popA[j]) {
                stack.pop();
                j++;
            }
        }
        // 3. stack为空，栈队列可由原数列进行栈操作得到
        return stack.isEmpty();
    }
}

---

65. 滑动窗口最大值

描述

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。

例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

思路

用一个双端队列，队列第一个位置保存当前窗口的最大值的index，当窗口滑动一次
1.判断当前最大值是否过期
2.新增加的值从队尾开始比较，把所有比他小的值丢掉

public ArrayList<Integer> maxInWindows(int[] num, int size) {
        ArrayList<Integer> res = new ArrayList<>();
        LinkedList<Integer> deque = new LinkedList<>();
        if (num.length == 0 || size == 0)
            return res;
        for (int i = 0; i < num.length; i++) {
            // 判断是否过期
            if (!deque.isEmpty() && deque.peekFirst() <= i - size) {
                deque.poll();
            }
            // 丢掉比num[i]小的值的index
            while (!deque.isEmpty() && num[deque.peekLast()] < num[i]) {
                deque.removeLast();
            }
            deque.offerLast(i);
            // 完整窗口出现，放入deque中的首位index
            if (i + 1 >= size) {
                res.add(num[deque.peekFirst()]);
            }
        }
        return res;
    }

---