public class DemoStack1 {
    public static void main(String[] args) {

        String str = "123456789";
        String reStr = reStr(str);
        System.out.println(reStr);

    }

    // 棧先進(jìn)后出
    public static String reStr(String str){
        MyArrayStack<Character> stack = new MyArrayStack<>();

        for (int i = 0; i < str.length(); i++) {
            stack.push(str.charAt(i));
        }

        StringBuffer buffer = new StringBuffer();

        // 1 2 3 4 5 6 7 8 9
        while (!stack.isEmpty()){
            Character pop = stack.pop();
            buffer.append(pop);
        }

        return buffer.toString();
    }
}

public class DemoStack2 {
    public static void main(String[] args) {

        String str = "public class) DemoStack2 {public static void main(String[] args) {}}";

        boolean bool = judgeBracket(str);
        System.out.println(bool);

    }

    public static  boolean judgeBracket(String str){
        MyArrayStack<Character> stack = new MyArrayStack<>();

        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            // 判斷c 是left括號(hào), 然后入棧

            if (c == '{'){
                stack.push('}');
            } else if (c == '['){
                stack.push(']');
            }else if (c == '('){
                stack.push(')');
            } else if (c == '}' || c == ')' || c == ']'){
                Character pop = stack.pop();
                if (c != pop){// 不匹配
                    return false;
                }
            }
        }

        return stack.isEmpty();
    }
}

/**
 * 用數(shù)組實(shí)現(xiàn)一個(gè)隊(duì)列
 * 集合類角度: 數(shù)據(jù)容器
 * 底層: 數(shù)組
 * 表示: 隊(duì)列
 */
public class MyArrayQueue <T> {

    private final int MAX_CAPACITY = Integer.MAX_VALUE - 8;
    private final int INIT_CAPACITY = 16;

    private Object[] objs;
    private int size;
    private int head;// 頭的下標(biāo)
    private int end;// 尾的下標(biāo)


    public MyArrayQueue(){
        objs = new Object[INIT_CAPACITY];
    }
    public MyArrayQueue(int initCapcity){
        if (initCapcity <= 0 || initCapcity > MAX_CAPACITY) throw new IllegalArgumentException("" + initCapcity);

        objs = new Object[initCapcity];
    }

    public boolean offer(T t){
        // 如果數(shù)組滿了
        if (size == objs.length){
            int newLen = getLen();
            grow(newLen);
        }

        // 可以添加
        if (isEmpty()){
            // 沒有任何元素存儲(chǔ): 新添加的元素就是唯一的元素
            objs[head] = t;
            end = head;
            size++;
            return true;
        } else {
            // 原本存儲(chǔ)就有內(nèi)容

            // 尾后移一位
            end = (end + 1) % objs.length;
            objs[end] = t;
            size++;
            return true;
        }
    }

    private void grow(int newLen) {
        Object[] newArr = new Object[newLen];
        for (int i = 0; i < objs.length; i++) {
            int index = (head + i) % objs.length;

            newArr[i] = objs[index];
        }
        objs = newArr;
        head = 0;
        end = size - 1;
    }

    private int getLen() {
        int oldLen = objs.length;
        int newLen = oldLen << 1;
        // 判斷新長度是否溢出
        if (newLen <= 0 || newLen > MAX_CAPACITY){
            newLen = MAX_CAPACITY;
        }
        // 如果新長度和舊長度一樣
        if (newLen == oldLen)throw  new RuntimeException("stack can not add");

        return newLen;
    }


    public T poll(){
        if (isEmpty()) throw new RuntimeException("queue is empty");

        if (size == 1){
            // 原隊(duì)列中只剩一個(gè)元素
            T oldValue = (T)objs[head];
            head = 0;
            end = 0;
            size--;
            return oldValue;
        } else {
            // 隊(duì)列中超過一個(gè)元素
            T oldValue = (T)objs[head];
            head = (head + 1) % objs.length;
            size--;
            return oldValue;
        }
    }

    public T peek(){
        if (isEmpty()) throw new RuntimeException("queue is empty");
        return (T)objs[head];
    }

    public int size() {
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }
}

public class MyLinkedQueue <T> {

    private Node head;// 隊(duì)頭
    private Node end; // 隊(duì)尾
    private int size;

    // 添加 offer
    // 刪除 poll
    // 查看隊(duì)頭元素 peek

    public  boolean offer(T t){

        // 如果原隊(duì)列為空
        if (isEmpty()){// 原隊(duì)列空
            // 讓頭尾都指向這個(gè)新加的結(jié)點(diǎn)
            head = new Node(t, null);
            end = head;
            size++;
            return true;
        }

        // 原隊(duì)列不空
        // 把這個(gè)元素添加到隊(duì)尾
        end.next = new Node(t, null);
        end = end.next;// end后移
        size++;
        return true;
    }

    public T poll(){
        if (isEmpty()) throw  new RuntimeException("queue is empty");

        if (size == 1){
            // 代表著, 鏈表中只有一個(gè)元素
            T oldVlaue = head.value;
            head = null;
            end = null;
            size--;
            return  oldVlaue;
        }else {
            T oldVlaue = head.value;
            head = head.next;
            size--;
            return oldVlaue;
        }
    }

    public T peek(){
        if (isEmpty()) throw  new RuntimeException("queue is empty");
        return head.value;
    }


    public boolean isEmpty(){
        return size == 0;
    }
    public int size(){
        return size;
    }




    class Node{
        T value;
        Node next;

        public Node(T value, Node next) {
            this.value = value;
            this.next = next;
        }
    }
}