641.设计循环双端队列

链接：641.设计循环双端队列
难度：Medium
标签：设计、队列、数组、链表
简介：设计实现双端队列。

题解 1 - typescript

• 编辑时间：2021-03-14
• 执行用时：160ms
• 内存消耗：46.1MB
• 编程语言：typescript
• 解法介绍：根据题 622 完善。

class MyCircularDeque {
  private arr: number[];
  private head = 0;
  private rear = 0;
  private count = 0;
  constructor(private k: number) {
    this.arr = new Array(k);
  }
  isEmpty(): boolean {
    return this.count === 0;
  }
  isFull(): boolean {
    return this.count === this.k;
  }
  insertFront(value: number): boolean {
    if (this.isFull()) return false;
    this.head = this.head === 0 ? this.k - 1 : this.head - 1;
    this.arr[this.head] = value;
    this.count++;
    return true;
  }
  insertLast(value: number): boolean {
    if (this.isFull()) return false;
    this.arr[this.rear] = value;
    this.rear = (this.rear + 1) % this.k;
    this.count++;
    return true;
  }
  deleteFront(): boolean {
    if (this.isEmpty()) return false;
    this.head = (this.head + 1) % this.k;
    this.count--;
    return true;
  }
  deleteLast(): boolean {
    if (this.isEmpty()) return false;
    this.rear = this.rear === 0 ? this.k - 1 : this.rear - 1;
    this.count--;
    return true;
  }
  getFront(): number {
    if (this.isEmpty()) return -1;
    return this.arr[this.head];
  }
  getRear(): number {
    if (this.isEmpty()) return -1;
    return this.arr[this.rear === 0 ? this.k - 1 : this.rear - 1];
  }
}

题解 2 - cpp

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

class MyCircularDeque {
   public:
    int head, tail, *list, n;
    MyCircularDeque(int k) : head(0), tail(0), n(k + 1) {
        list = ((int *)malloc(sizeof(int) * n));
    }
    ~MyCircularDeque() { free(list); }
    bool insertLast(int value) {
        if (isFull()) return 0;
        list[tail] = value;
        tail = (tail + 1) % n;
        return 1;
    }
    bool insertFront(int value) {
        if (isFull()) return 0;
        head = head == 0 ? n - 1 : head - 1;
        list[head] = value;
        return 1;
    }
    bool deleteLast() {
        if (isEmpty()) return 0;
        tail = tail == 0 ? n - 1 : tail - 1;
        return 1;
    }
    bool deleteFront() {
        if (isEmpty()) return 0;
        head = (head + 1) % n;
        return 1;
    }
    int getFront() {
        if (isEmpty()) return -1;
        return list[head];
    }
    int getRear() {
        if (isEmpty()) return -1;
        return list[tail == 0 ? n - 1 : tail - 1];
    }
    bool isEmpty() { return head == tail; }
    bool isFull() { return (tail + 1) % n == head; }
};

题解 3 - rust

• 编辑时间：2022-08-15
• 执行用时：4ms
• 内存消耗：2.5MB
• 编程语言：rust
• 解法介绍：循环队列。

struct MyCircularDeque {
    list: Vec<i32>,
    first: usize,
    last: usize,
    len: usize,
}
impl MyCircularDeque {
    fn new(k: i32) -> Self {
        let len = (k + 1) as usize;
        let mut list = Vec::with_capacity(len);
        for _ in 0..len {
            list.push(0);
        }
        MyCircularDeque {
            list,
            first: 0,
            last: 0,
            len,
        }
    }
    fn insert_front(&mut self, value: i32) -> bool {
        if self.is_full() {
            false
        } else {
            self.first = self.get_prev(self.first);
            self.list[self.first] = value;
            true
        }
    }
    fn insert_last(&mut self, value: i32) -> bool {
        if self.is_full() {
            false
        } else {
            self.list[self.last] = value;
            self.last = self.get_next(self.last);
            true
        }
    }
    fn delete_front(&mut self) -> bool {
        if self.is_empty() {
            false
        } else {
            self.first = self.get_next(self.first);
            true
        }
    }
    fn delete_last(&mut self) -> bool {
        if self.is_empty() {
            false
        } else {
            self.last = self.get_prev(self.last);
            true
        }
    }
    fn get_front(&self) -> i32 {
        if self.is_empty() {
            -1
        } else {
            self.list[self.first]
        }
    }
    fn get_rear(&self) -> i32 {
        if self.is_empty() {
            -1
        } else {
            self.list[self.get_prev(self.last)]
        }
    }
    fn is_empty(&self) -> bool {
        self.first == self.last
    }
    fn is_full(&self) -> bool {
        self.get_next(self.last) == self.first
    }
    fn get_prev(&self, cur: usize) -> usize {
        if cur == 0 {
            self.len - 1
        } else {
            cur - 1
        }
    }
    fn get_next(&self, cur: usize) -> usize {
        (cur + 1) % self.len
    }
}