622.设计循环队列

链接：622.设计循环队列
难度：Medium
标签：设计、队列、数组、链表
简介：设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

题解 1 - typescript

• 编辑时间：2021-03-14
• 执行用时：172ms
• 内存消耗：45.1MB
• 编程语言：typescript
• 解法介绍：利用 js 特性直接构建数组。

function copyRandomList(head: Node | null): Node | null {
  if (head === null) return null;
  let p: Node | null = head;
  while (p !== null) {
    p.next = new Node(p.val, p.next, p.random);
    p = p.next.next;
  }
  p = head.next;
  while (p) {
    if (p.random) p.random = p.random!.next;
    p = p.next?.next ?? null;
  }
  const newHead: Node | null = head.next;
  p = head;
  while (p) {
    const q: Node = p.next!;
    p.next = q.next;
    q.next = q.next?.next ?? null;
    p = p.next;
  }
  return newHead;
}

题解 2 - typescript

• 编辑时间：2021-03-14
• 执行用时：152ms
• 内存消耗：45.4MB
• 编程语言：typescript
• 解法介绍：创建头尾指针控制。

class MyCircularQueue {
  private arr: number[];
  private head = 0;
  private rear = 0;
  private count = 0;
  constructor(private k: number) {
    this.arr = new Array(k);
  }
  enQueue(value: number): boolean {
    if (this.isFull()) return false;
    this.arr[this.rear] = value;
    this.rear = (this.rear + 1) % this.k;
    this.count++;
    return true;
  }
  deQueue(): boolean {
    if (this.isEmpty()) return false;
    this.head = (this.head + 1) % this.k;
    this.count--;
    return true;
  }
  Front(): number {
    if (this.isEmpty()) return -1;
    return this.arr[this.head];
  }
  Rear(): number {
    if (this.isEmpty()) return -1;
    return this.arr[this.rear === 0 ? this.k - 1 : this.rear - 1];
  }
  isEmpty(): boolean {
    return this.count === 0;
  }
  isFull(): boolean {
    return this.count === this.k;
  }
}

题解 3 - cpp

• 编辑时间：2022-03-03
• 执行用时：20ms
• 内存消耗：16.3MB
• 编程语言：cpp
• 解法介绍：双指针。

class MyCircularQueue {
   public:
    int head, tail, *list, n;
    MyCircularQueue(int k) : head(0), tail(0), n(k + 1) {
        list = ((int *)malloc(sizeof(int) * n));
    }
    ~MyCircularQueue() { free(list); }
    bool enQueue(int value) {
        if (isFull()) return 0;
        list[tail] = value;
        tail = (tail + 1) % n;
        return 1;
    }
    bool deQueue() {
        if (isEmpty()) return 0;
        head = (head + 1) % n;
        return 1;
    }
    int Front() {
        if (isEmpty()) return -1;
        return list[head];
    }
    int Rear() {
        if (isEmpty()) return -1;
        return list[tail == 0 ? n - 1 : tail - 1];
    }
    bool isEmpty() { return head == tail; }
    bool isFull() { return (tail + 1) % n == head; }
};

题解 4 - rust

• 编辑时间：2022-08-02
• 执行用时：4ms
• 内存消耗：2.3MB
• 编程语言：rust
• 解法介绍：queue。

struct MyCircularQueue {
    list: Vec<i32>,
    max: usize,
    head: usize,
    rear: usize,
}
impl MyCircularQueue {
    fn new(k: i32) -> Self {
        let max = (k + 1) as usize;
        let mut list = Vec::with_capacity(max);
        for _ in 0..max {
            list.push(0);
        }
        MyCircularQueue {
            max,
            list,
            head: 0,
            rear: 0,
        }
    }
    fn en_queue(&mut self, value: i32) -> bool {
        if self.is_full() {
            false
        } else {
            self.list[self.rear] = value;
            self.rear = (self.rear + 1) % self.max;
            true
        }
    }
    fn de_queue(&mut self) -> bool {
        if self.is_empty() {
            false
        } else {
            self.head = (self.head + 1) % self.max;
            true
        }
    }
    fn front(&self) -> i32 {
        if self.is_empty() {
            -1
        } else {
            *self.list.get(self.head).unwrap()
        }
    }
    fn rear(&self) -> i32 {
        if self.is_empty() {
            -1
        } else {
            let rear = if self.rear == 0 {
                self.max - 1
            } else {
                self.rear - 1
            };
            *self.list.get(rear).unwrap()
        }
    }
    fn is_empty(&self) -> bool {
        self.rear == self.head
    }
    fn is_full(&self) -> bool {
        (self.rear + 1) % self.max == self.head
    }
}