public class MyStack {
    public int[] elem;
    public int usedSize;

    public MyStack() {
        this.elem = new int[4];
    }

    // 放入元素
    public void push(int val) {
        if(isFull()) {
            // 如果放滿了，二倍擴容
            this.elem = Arrays.copyOf(elem,2 * elem.length);
        }
        this.elem[this.usedSize++] = val;
    }
    // 獲取棧頂元素并彈出
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("棧為空！");
        }
        usedSize--;
        return elem[usedSize];
    }
    // 獲取棧頂元素
    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("棧為空！");
        }
        return elem[usedSize-1];
    }
    // 是否為空
    public boolean isEmpty() {
        return usedSize == 0;
    }
    // 是否滿了
    public boolean isFull() {
        return elem.length == usedSize;
    }
}

// 普通隊列
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);// 隊尾入
int top = queue.peek();// 獲取隊頭元素
queue.poll();// 彈出隊尾元素并返回

// 雙端隊列
Deque<Integer> deque = new LinkedList<>();
deque.offer(1);// 默認隊尾入
deque.offerFirst(2);// 隊頭入
deque.offerLast(3);// 隊尾入

deque.peekFirst();// 獲取隊頭元素
deque.peekLast();// 獲取隊尾元素

deque.pollFirst();// 彈出隊頭元素并返回
deque.pollLast();// 彈出隊尾元素并返回

/**
 * 每個節(jié)點
 */
class Node{
    public int val;
    public Node next;

    public Node(int val) {
        this.val = val;
    }
}
public class MyQueue {
    public Node head;
    public Node tail;

    /**
     * 插入元素 -- 尾插法
     * @param val
     */
    public void offer(int val) {
        Node node = new Node(val);
        if (head == null) {
            head = node;
            tail = node;
        }else {
            tail.next = node;
            tail = tail.next;
        }
    }

    /**
     * 出隊列
     */
    public int poll() {
        if(isEmpty()) {
            throw new RuntimeException("隊列為空！");
        }
        int val = head.val;
        head = head.next;
        return val;
    }

    /**
     * 獲取隊頭元素
     */
    public int peek() {
        if(isEmpty()) {
            throw new RuntimeException("隊列為空！");
        }
        return head.val;
    }
    
    // 隊列是否為空
    public boolean isEmpty() {
        return head == null;
    }
}

public class MyCircularQueue {
    public int[] elem;
    public int front;// 隊頭下標
    public int rear;// 隊尾下標
    boolean flag = true;// 是否為空

    public MyCircularQueue(int k) {
        elem = new int[k];
    }

    // 向循環(huán)隊列插入一個元素。如果成功插入則返回真。
    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
//            throw new RuntimeException("隊列已滿!");
        }
        elem[rear] = value;
        rear = (rear + 1) % elem.length;
        flag = false;
        return true;
    }

    // 從循環(huán)隊列中刪除一個元素。如果成功刪除則返回真。
    public boolean deQueue() {
        if (isEmpty()) {
            return false;
//            throw new RuntimeException("隊列為空!");
        }
        front = (front + 1) % elem.length;
        flag = true;
        return true;
    }

    // 從隊首獲取元素。如果隊列為空，返回 -1 。
    public int Front() {
        if (isEmpty()) {
            return -1;
//            throw new RuntimeException("隊列為空!");
        }
        return elem[front];
    }
    // 獲取隊尾元素。如果隊列為空，返回 -1 。
    public int Rear() {
        if (isEmpty()) {
            return -1;
//            throw new RuntimeException("隊列為空!");
        }
        // 如果是0下標，拿最后一個元素
        if (rear == 0) {
            return elem[elem.length-1];
        }else {
            return elem[rear - 1];
        }
    }

    // 檢查循環(huán)隊列是否為空。
    public boolean isEmpty() {
        if (rear == front && flag){
            return true;
        }
        return false;
    }
    // 檢查循環(huán)隊列是否已滿。
    public boolean isFull() {
        if (rear == front && !flag){
            return true;
        }
        return false;
    }
}