力扣 622 设计循环队列

题意：构建循环队列

思路：用一个双向node 构建循环队列

思想：双向链表

复杂度：时间O（1)，空间O(n)

class Node {
    Node pre = null;
    Node next = null;
    int val;
    public Node(int val) {
        this.val = val;
    }
}

class MyCircularQueue {
    int k;
    Node head = null;
    Node tail = null;
    /** Initialize your data structure here. Set the size of the queue to be k. */
    public MyCircularQueue(int k) {
        this.k = k;
    }
    
    /** Insert an element into the circular queue. Return true if the operation is successful. */
    public boolean enQueue(int value) {
        if(k == 0)
            return false;
        k--;
        Node temp = new Node(value);
        if(head == null) {
            head = temp;
            tail = head;
            return true;
        }
        temp.next = head;
        head.pre = temp;
        temp.pre = tail;
        tail.next = temp;
        tail = temp;
        return true;
    }
    
    /** Delete an element from the circular queue. Return true if the operation is successful. */
    public boolean deQueue() {
        if(head == null)
            return false;
        k++;
        if(head == tail) {
            head = null;
            tail = null;
            return true;
        }
        Node temp = head.next;
        temp.pre = tail;
        tail.next = temp;
        head.next = null;
        head.pre = null;
        head = temp;
        return true;
    }
    
    /** Get the front item from the queue. */
    public int Front() {
        if(head == null)
            return -1;
        return head.val;
    }
    
    /** Get the last item from the queue. */
    public int Rear() {
        if(tail == null)
            return -1;
        return tail.val;
    }
    
    /** Checks whether the circular queue is empty or not. */
    public boolean isEmpty() {
        return head == null;
    }
    
    /** Checks whether the circular queue is full or not. */
    public boolean isFull() {
        return k == 0;
    }
}