算法第九天|栈-队列-二叉树篇

232. 用栈实现队列

class MyQueue {

    Stack<Integer> stackIn;
    Stack<Integer> stackOut;
    
    public MyQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }

    public void push(int x) {
        stackIn.push(x);
    }

    public int pop() {
        dumpStackIn();
        return stackOut.pop();
    }

    public int peek() {
        dumpStackIn();
        return stackOut.peek();
    }

    private void dumpStackIn() {
        if (!stackOut.isEmpty()) return;
        while (!stackIn.isEmpty()) {
            stackOut.push(stackIn.pop());
        }
    }

    public boolean empty() {
        return stackIn.isEmpty() && stackOut.isEmpty();
    }
}

使用两个栈来实现队列，一个用于进栈，一个用于出栈。

225. 用队列实现栈

public class MyStack {

    private Queue<Integer> queue1;
    private Queue<Integer> queue2; // 备用

    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    public void push(int x) {
        while (!queue1.isEmpty()) {
            queue2.offer(queue1.poll()); // queue2中有了所有元素
        }
        // queue1加入最新元素,目前只有一个元素,意味着该元素是第一个加入的，也是第一个出去的
        queue1.offer(x);
        // 然后将所有元素加入到queue1中
        while (!queue2.isEmpty()) {
            queue1.offer(queue2.poll());
        }
    }

    public int pop() {
        return queue1.poll();
    }

    public int top() {
        return queue1.peek();
    }

    public boolean empty() {
        return queue1.isEmpty();
    }
}


public class MyStack02 {

    private Deque<Integer> deque;

    public MyStack02(){
        deque = new LinkedList<>();
    }

    public void push(int x) {
        deque.addLast(x);
    }

    public int pop() {
        return deque.pollLast();
    }

    public int top() {
        return deque.peekLast();
    }

    public boolean empty() {
        return deque.isEmpty();
    }
}

用栈实现队列方式有些不相同,在push中进行了改造，先将原始数据放置到另一个队列中，将新加入数据放入到队列1中
再将原始数据重新放入队列1中。
第二种方式是用双端队列来解决

20. 有效的括号

 public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (checkContains(stack, '(')) return false;
            } else if (s.charAt(i) == '}'){
                if (checkContains(stack, '{')) return false;
            } else if (s.charAt(i) == ']'){
                if (checkContains(stack, '[')) return false;
            } else {
                stack.push(s.charAt(i));
            }

        }
        if (stack.isEmpty()) {
            return true;
        }
        return false;
    }

    private static boolean checkContains(Stack<Character> stack, Character isFindChar) {
        boolean isFind = true;
        while (!stack.isEmpty()) {
            Character pop = stack.pop();
            if (pop.equals(isFindChar)){
                isFind = false;
                break; // 找到了就不管了
            } else {
                break;
            }
        }
     return isFind;
    }


    public boolean isValid2(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(')');
            } else if (c == '['){
                stack.push(']');
            } else if (c == '{') {
                stack.push('}');
            } else if (stack.isEmpty() || stack.peek() != c) {
                return false;
            } else {
                stack.pop();
            }
        }
        if (stack.isEmpty()) {
            return true;
        }
        return false;
    }

符号是成对出现的，需要注意的是：'['下一个符号不一定是']'，但是']'符号之前必然有一个符号是'[',
所以通常是根据之后的符号来确定，而不是前面的符号.

二叉树的前中后序----144. 二叉树的前序遍历 ----145. 二叉树的后序遍历---- 94. 二叉树的中序遍历

 List<Integer> list = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) {
            return list;
        }
        list.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return list;
    }

    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) {
            return list;
        }
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        list.add(root.val);
        return list;
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) {
            return list;
        }
        inorderTraversal(root.left);
        list.add(root.val);
        inorderTraversal(root.right);
        return list;
    }

二叉树的前中后序是最基础的操作