leetcode判断有效的括号；用队列实现栈；用栈实现队列；实现一个最小栈

1. 判断有效的括号

package tmr1012;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;


public class TestStackAndQueue {
    public boolean isVaild(String s) {
        //1.先创建一个栈，栈中保存字符类型即可
        Stack stack = new Stack<>();
        Map map = new HashMap<>();
        map.put('(',')');
        map.put('{','}');
        map.put('[',']');

        //2.循环遍历字符串中的每个字符
        for (int i= 0;i < s.length();i++) {
            char c = s.charAt(i);
            //3.判定c是否是左括号，如果是左括号，就入栈
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
                continue;//进入下一次循环，取出下一个字符
            }
            if (stack.empty()) {
                //如果发现当前字符不是左括号，并且栈又为空，此时也说明字符串非法
                //这种情况说明前头没有合适的左括号与当前括号匹配
                return false;
            }
            //4.判定top是否是右括号，如果是，就取出栈顶元素来对比一下
            char top = stack.pop();
           
            if (map.get(top) == c) {
                continue;
            }
            return false;
        }
        //遍历完字符串之后，还得看下栈是否为空
        if (stack.empty()) {
            return true;
        }
        return false;
    }
}

 2.用队列实现栈

package tmr1012;

import java.util.linkedList;
import java.util.Queue;


public class MyStackBy2Queue {
    private Queue A = new linkedList<>();
    private Queue B = new linkedList<>();

    public void push(int x) {
        //x往A中放入队列即可
        A.offer(x);
    }

    public Integer pop() {
        if (empty()) {
            return null;
        }

        //把A中元素往B中倒腾
        while(A.size() >1) {
            Integer front = A.poll();
            B.offer(front);
        }
        //当循环结束后，A中应该只有一个元素
        //这个元素就是应该被出栈的元素
        int ret = A.poll();
        swapAB();
        return ret;
    }

    private void swapAB() {
        Queue tmp = A;
        A = B;
        B = tmp;
    }
     public Integer top() {
         if (empty()) {
             return null;
         }

         //把A中元素往B中倒腾
         while(A.size() >1) {
             Integer front = A.poll();
             B.offer(front);
         }
         //当循环结束后，A中应该只有一个元素
         //这个元素就是应该被出栈的元素
         int ret = A.poll();
         B.offer(ret);//top和pop唯一的区别
         swapAB();
         return ret;
     }

     public boolean empty() {
        return A.isEmpty() && B.isEmpty();
     }

}

3. 用栈实现队列

package tmr1012;

import java.util.Stack;


public class MyQueueBy2Stack {
    private Stack A = new Stack<>();
    private Stack B = new Stack<>();

    public void push(int x) {
        //1.先把B中的元素倒腾到A中
        while(!B.isEmpty()) {
            int tmp = B.pop();
            A.push(tmp);
        }
        //2.把新元素入A即可
        A.push(x);
    }

    public Integer pop() {
        //1.如果为空直接返回
        if (empty()) {
            return null;
        }
        //2.把A中元素倒腾给B
        while(!A.isEmpty()) {
            int tmp = A.pop();
            B.push(tmp);
        }
        //3.针对B进行出栈
        return B.pop();
    }

    public Integer peek() {
        //1.如果为空直接返回
        if (empty()) {
            return null;
        }
        //2.把A中元素倒腾给B
        while(!A.isEmpty()) {
            int tmp = A.pop();
            B.push(tmp);
        }
        //3.直接取B的栈顶元素
        return B.peek();
    }

    public boolean empty() {
        return A.isEmpty() && B.isEmpty();
    }
}

 4.实现一个最小栈

package tmr1012;

import org.omg.CORBA.PUBLIC_MEMBER;

import java.util.Stack;


public class MinStack {
    private Stack A = new Stack<>();
    private Stack B = new Stack<>();

    public void push(int x) {
        A.push(x);
        if (B.isEmpty()) {
            B.push(x);
            return;
        }
        int min = B.peek();
        if (x < min) {
            min = x;
        }
        B.push(min);
    }

    public Integer pop() {
        if (A.isEmpty()) {
            return null;
        }
        B.pop();
        return A.pop();
    }

    public Integer top() {
        if (A.isEmpty()) {
            return null;
        }
        return A.peek();
    }
    public Integer getMin() {
        if (B.isEmpty()) {
            return null;
        }
        return B.peek();
    }
}