public static void main(String[] args) {
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(1);
    queue.offer(2);
    queue.offer(3);
    System.out.println(queue.peek()); //獲取對(duì)頭元素 -> 1
    System.out.println(queue.poll()); //出隊(duì)頭元素 -> 1
    System.out.println(queue.peek()); //獲取對(duì)頭元素 -> 2
    System.out.println(queue.isEmpty()); //判斷隊(duì)列是否為null -> false
    queue.clear(); //清空隊(duì)列
    System.out.println(queue.isEmpty()); //判斷隊(duì)列是否為null -> true
}

public class MyQueue { 
    private class Node { 
        private int val; //數(shù)據(jù)域 
        private Node next; //指針域名 
        private Node(int val) { 
            this.val = val; 
         } 
    } 
    //隊(duì)頭入，隊(duì)尾出 
    private Node head; //隊(duì)頭引用 
    private Node last; //隊(duì)尾引用 
    private int size; //隊(duì)列有效數(shù)據(jù)個(gè)數(shù)
    }

// 隊(duì)尾入隊(duì)列
public boolean offer(int val) { 
    Node newNode = new Node(val); 
    // 如果是第一次入隊(duì)列 
    if (this.head == null) { 
        this.head = newNode; 
        this.last = newNode;
    } else { 
        this.last.next = newNode; 
        this.last = this.last.next; 
    } 
    this.size++; 
    return true;
}

// 隊(duì)頭出隊(duì)列
public int poll() { 
    Node node = this.head;
    // 如果隊(duì)列為null 
    if (this.head == null) { 
        throw new MyQueueIsEmptyException("隊(duì)列為空！"); 
    } else { 
        this.head = this.head.next; 
    } 
    this.size--; 
    return node.val;
}

// 取隊(duì)頭元素
public int peek() { 
    // 如果隊(duì)列為null 
    if (this.head == null) { 
        throw new MyQueueIsEmptyException("隊(duì)列為空！"); 
    } 
    else { 
        return this.head.val;
    }
}

public class MyCircularQueue {
 
    private int array[]; //存放數(shù)據(jù)的數(shù)組
    private int front; // 隊(duì)頭下標(biāo)
    private int rear; // 隊(duì)尾下標(biāo)
 
    public MyCircularQueue(int k) {
        this.array = new int[k + 1]; //因?yàn)槲覀円速M(fèi)一個(gè)空間，所以需要多開辟一個(gè)空間
    }
 
    // 入隊(duì)列
    public boolean enQueue(int value) {
        // 如果隊(duì)列滿的情況
        if (isFull()) {
            return false;
        }
        // 沒有滿就往隊(duì)尾入元素
        this.array[this.rear] = value;
        // rear往前走一步，需要空出一個(gè)位置，所以當(dāng)rear走到length-1時(shí)，需要修正下rear
        this.rear = (this.rear + 1) % this.array.length;
        return true;
    }
 
    // 出隊(duì)列
    public boolean deQueue() {
        // 如果隊(duì)列為null的情況
        if (isEmpty()) {
            return false;
        }
        // 從隊(duì)頭出隊(duì)列，需要修正隊(duì)頭的位置
        this.front = (this.front + 1) % this.array.length;
        return true;
    }
    
    // 取隊(duì)頭元素
    public int Front() {
        // 如果隊(duì)列為null的情況
        if (isEmpty()) {
            return -1;
        }
        return this.array[this.front]; //返回隊(duì)頭元素
    }
 
    // 取隊(duì)尾元素
    public int Rear() {
        // 如果隊(duì)列為null的情況
        if (isEmpty()) {
            return -1;
        }
        // 如果rear為0的情況，我們需要特殊處理
        int index = this.rear == 0 ? this.array.length - 1 : this.rear - 1;
        return this.array[index]; //返回隊(duì)尾元素
    }
 
    // 判斷隊(duì)列是否為空
    public boolean isEmpty() {
        // 當(dāng)front和rear相遇了，則表示隊(duì)列中沒有元素
        return this.front == this.rear;
    }
 
    // 判斷隊(duì)列是否滿了
    public boolean isFull() {
        // 因?yàn)槲覀儠?huì)浪費(fèi)一個(gè)空間，所以rear+1等于front就滿了
        // 但是我們要rear防止越界，所以要進(jìn)行修正：(this.rear + 1) % this.array.length
        return (this.rear + 1) % this.array.length == this.front;
    }
}

class MyStack {
    private Queue<Integer> qu1;
    private Queue<Integer> qu2;
 
    public MyStack() {
        this.qu1 = new LinkedList<>();
        this.qu2 = new LinkedList<>();
    }
    
    public void push(int x) {
        // 兩個(gè)隊(duì)列都為null的情況
        if (this.qu1.isEmpty() && this.qu2.isEmpty()) {
            this.qu1.offer(x);
            return;
        }
 
        // 哪個(gè)隊(duì)列不為null往哪個(gè)隊(duì)列中入元素
        if (!this.qu1.isEmpty()) {
            this.qu1.offer(x);
        } else {
            this.qu2.offer(x);
        }
    }
    
    public int pop() {
        // 如果兩個(gè)隊(duì)列都為空的情況下，就不能出隊(duì)操作
        if (empty()) {
            return -1;
        }
        // 先將不為空的隊(duì)列的size-1個(gè)元素全部放到為空的隊(duì)列中
        if (!this.qu1.isEmpty()) {
            while (qu1.size() - 1 != 0) {
                qu2.offer(qu1.poll());
            }
            return qu1.poll(); //返回最后一個(gè)元素
        } else {
            while (qu2.size() - 1 != 0) {
                qu1.offer(qu2.poll());
            }
            return qu2.poll(); //返回最后一個(gè)元素
        }
    }
    
    public int top() {
        // 如果隊(duì)列為null
        if (empty()) {
            return -1;
        }
        int ret = 0; //保留剩余最后一個(gè)棧頂元素的變量
        // 先將不為空的隊(duì)列的size-1個(gè)元素全部放到為空的隊(duì)列中
        if (!this.qu1.isEmpty()) {
            while (qu1.size() - 1 != 0) {
                qu2.offer(qu1.poll());
            }
            ret = qu1.peek();
            qu2.offer(qu1.poll());
        } else {
            while (qu2.size() - 1 != 0) {
                qu1.offer(qu2.poll());
            }
            ret = qu2.peek();
            qu1.offer(qu2.poll()); //取棧頂元素不能刪除掉，還得入另一個(gè)隊(duì)列中去
        }
        return ret;
    }
    
    public boolean empty() {
        return this.qu1.isEmpty() && this.qu2.isEmpty(); //兩個(gè)隊(duì)列都為空，棧才為空
    }
}

class MyQueue {
    private Stack<Integer> pushStack;
    private Stack<Integer> popStack;
    public MyQueue() {
        this.pushStack = new Stack<>();
        this.popStack = new Stack<>();
    }
    
    public void push(int x) {
        // 入隊(duì)列都在pushStack中
        this.pushStack.push(x);
    }
    
    public int pop() {
        // 出隊(duì)列都從popStack出
        if (popStack.empty()) {
            // 把pushStack棧中的元素都放到popStack棧中
            while (!pushStack.empty()) {
                popStack.push(pushStack.pop());
            }
        }
        if (!popStack.empty()) {
            return popStack.pop();
        } else {
            return -1;
        }
    }
    
    public int peek() {
        // 取隊(duì)頭元素都從popStack中取
        if (popStack.empty()) {
            // 把pushStack棧中的元素都放到popStack棧中
            while (!pushStack.empty()) {
                popStack.push(pushStack.pop());
            }
        }
        if (!popStack.empty()) {
            return popStack.peek();
        } else {
            return -1;
        }
    }
    
    public boolean empty() {
        return pushStack.empty() && popStack.empty();
    }
}

public class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;
    public MinStack() {
        this.stack = new Stack<>();
        this.minStack = new Stack<>();
    }
    
    public void push(int val) {
        // 如果stack為null，表示第一次入棧，
        // 此時(shí)入棧的元素也是此時(shí)棧中最小值，也要入minStack棧
        if (this.stack.isEmpty()) {
            this.stack.push(val);
            this.minStack.push(val);
            return;
        }
        this.stack.push(val);
        // 如果stack棧頂元素小于等于minStack棧頂元素，則也需要入minStack棧中
        if (this.stack.peek() <= this.minStack.peek()) {
            this.minStack.push(val);
        }
    }
 
    // 出棧
    public void pop() {
        if (this.stack.isEmpty()) {
            return;
        }
        // 如果出棧元素與minStack元素相等，minStack也要出棧
        if (this.stack.pop().equals(this.minStack.peek())) {
            this.minStack.pop();
        }
    }
 
    // 取棧頂元素
    public int top() {
        if (this.stack.isEmpty()) {
            return -1;
        } else {
            return this.stack.peek();
        }
    }
 
    // 取棧中最小元素
    public int getMin() {
        if (this.stack.isEmpty()) {
            return -1;
        } else {
            return this.minStack.peek();
        }
    }
}