LeetCode 622. Designing Circular Queues

622. 设计循环队列

【数组】Implemented with a one-dimensional array,front指向头,rearPointing to the tail of the next one（This is done to distinguish between empty and full,if both point to the same element,那么front==rearMay be empty may also be a circle around the full）因为要存k个元素,所以要开k+1的空间.这样,Empty is(front + 1) % (k + 1) == rear,Sentence is full(rear + 1) % (k + 1) == front,添加元素为arr[rear] = val, rear = (rear + k + 1) % (k + 1),删除元素为front = (front + 1) % (k + 1),The first element of the queue isarr[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();
 */