LeetCode 622. 设计循环队列

622. 设计循环队列

【数组】用一个一维数组来实现，front指向头，rear指向尾的下一个（这样做是为了区分空和满，如果都指向同一个元素，那么front==rear可能是空也可能是绕了一圈的满）因为要存k个元素，所以要开k+1的空间。这样，判空就是(front + 1) % (k + 1) == rear，判满就是(rear + 1) % (k + 1) == front，添加元素为arr[rear] = val, rear = (rear + k + 1) % (k + 1)，删除元素为front = (front + 1) % (k + 1)，取队首元素就是arr[front]，队尾元素为arr[

class MyCircularQueue {

    int[] arr;
    int k, front = 0, rear = 0;

    public MyCircularQueue(int k) {
        this.k = k;
        arr = new int[k + 1];
    }
    
    public boolean enQueue(int value) {
        if (isFull()) return false;
        arr[rear] = value;
        rear = (rear + 1) % (k + 1);
        return true;
    }
    
    public boolean deQueue() {
        if (isEmpty()) return false;
        front = (front + 1) % (k + 1);
        return true;
    }
    
    public int Front() {
        if (isEmpty()) return -1;
        return arr[front];
    }
    
    public int Rear() {
        if (isEmpty()) return -1;
        return arr[(rear + k) % (k + 1)];
    }
    
    public boolean isEmpty() {
        return front == rear;
    }
    
    public boolean isFull() {
        return (rear + 1) % (k + 1) == front;
    }
}

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue obj = new MyCircularQueue(k);
 * boolean param_1 = obj.enQueue(value);
 * boolean param_2 = obj.deQueue();
 * int param_3 = obj.Front();
 * int param_4 = obj.Rear();
 * boolean param_5 = obj.isEmpty();
 * boolean param_6 = obj.isFull();
 */

class MyCircularQueue {

// 9:55.20

public:

    int* arr;
    int k, front = 0, rear = 0;

    MyCircularQueue(int k) {
        this -> k = k;
        arr = (int*)malloc(sizeof(int) * (k + 1));
    }
    
    bool enQueue(int value) {
        if (isFull()) return false;
        arr[rear] = value;
        rear = (rear + 1) % (k + 1);
        return true;
    }
    
    bool deQueue() {
        if (isEmpty()) return false;
        front = (front + 1) % (k + 1);
        return true;
    }
    
    int Front() {
        if (isEmpty()) return -1;
        return arr[front];
    }
    
    int Rear() {
        if (isEmpty()) return -1;
        return arr[(rear + k) % (k + 1)];
    }
    
    bool isEmpty() {
        return front == rear;
    }
    
    bool isFull() {
        return (rear + 1) % (k + 1) == front;
    }
};

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue* obj = new MyCircularQueue(k);
 * bool param_1 = obj->enQueue(value);
 * bool param_2 = obj->deQueue();
 * int param_3 = obj->Front();
 * int param_4 = obj->Rear();
 * bool param_5 = obj->isEmpty();
 * bool param_6 = obj->isFull();
 */

【手写链表】

class MyCircularQueue {

    class Node {
        int val;
        Node next;
        Node(int value) {
            this.val = value;
        }
    }

    Node front = null, rear = null;
    int k, n = 0;

    public MyCircularQueue(int k) {
        this.k = k;
    }
    
    public boolean enQueue(int value) {
        if (isFull()) return false;
        n++;
        Node node = new Node(value);
        if (isEmpty()) {
            front = node;
            rear = node;
            return true;
        }
        rear.next = node;
        rear = node;
        return true;
    }
    
    public boolean deQueue() {
        if (isEmpty()) return false;
        n--;
        front = front.next;
        return true;
    }
    
    public int Front() {
        if (isEmpty()) return -1;
        return front.val;
    }
    
    public int Rear() {
        if (isEmpty()) return -1;
        return rear.val;
    }
    
    public boolean isEmpty() {
        return front == null;
    }
    
    public boolean isFull() {
        return n == k;
    }
}

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue obj = new MyCircularQueue(k);
 * boolean param_1 = obj.enQueue(value);
 * boolean param_2 = obj.deQueue();
 * int param_3 = obj.Front();
 * int param_4 = obj.Rear();
 * boolean param_5 = obj.isEmpty();
 * boolean param_6 = obj.isFull();
 */

class Node {
public:
    int val;
    Node* next;
    Node(int val) {
        this -> val = val;
    }
};

class MyCircularQueue {
public:

    // 2:45 20

    Node* front;
    Node* rear;
    int k = 0, n; 
    
    MyCircularQueue(int k) {
        n = k;
    }
    
    bool enQueue(int value) {
        if (isFull()) return false;
        Node* node = new Node(value);
        if (isEmpty()) {
            front = node;
            rear = node;
        } else {
            rear -> next = node;
            rear = node;
        }
        k++;
        return true;
    }
    
    bool deQueue() {
        if (isEmpty()) return false;
        k--;
        front = front -> next;
        return true;
    }
    
    int Front() {
        if (isEmpty()) return -1;
        return front -> val;
    }
    
    int Rear() {
        if (isEmpty()) return -1;
        return rear -> val;
    }
    
    bool isEmpty() {
        return k == 0;
    }
    
    bool isFull() {
        return k == n;
    }
};

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue* obj = new MyCircularQueue(k);
 * bool param_1 = obj->enQueue(value);
 * bool param_2 = obj->deQueue();
 * int param_3 = obj->Front();
 * int param_4 = obj->Rear();
 * bool param_5 = obj->isEmpty();
 * bool param_6 = obj->isFull();
 */