Question

641. 设计循环双端队列

English Version

题目描述

设计实现双端队列。

实现 MyCircularDeque 类:

• MyCircularDeque(int k) ：构造函数,双端队列最大为 k 。
• boolean insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true ，否则返回 false 。
• boolean insertLast() ：将一个元素添加到双端队列尾部。如果操作成功返回 true ，否则返回 false 。
• boolean deleteFront() ：从双端队列头部删除一个元素。 如果操作成功返回 true ，否则返回 false 。
• boolean deleteLast() ：从双端队列尾部删除一个元素。如果操作成功返回 true ，否则返回 false 。
• int getFront() )：从双端队列头部获得一个元素。如果双端队列为空，返回 -1 。
• int getRear() ：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1 。
• boolean isEmpty() ：若双端队列为空，则返回 true ，否则返回 false  。
• boolean isFull() ：若双端队列满了，则返回 true ，否则返回 false 。

 

示例 1：

输入
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
输出
[null, true, true, true, false, 2, true, true, true, 4]

解释
MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3
circularDeque.insertLast(1);          // 返回 true
circularDeque.insertLast(2);          // 返回 true
circularDeque.insertFront(3);          // 返回 true
circularDeque.insertFront(4);          // 已经满了，返回 false
circularDeque.getRear();          // 返回 2
circularDeque.isFull();            // 返回 true
circularDeque.deleteLast();          // 返回 true
circularDeque.insertFront(4);          // 返回 true
circularDeque.getFront();        // 返回 4
 

 

提示：

• 1 <= k <= 1000
• 0 <= value <= 1000
• insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull  调用次数不大于 2000 次

解法

方法一：数组

利用循环数组，实现循环双端队列。

基本元素有：

• front：队头元素的下标
• size：队列中元素的个数
• capacity：队列的容量
• q：循环数组，存储队列中的元素

时间复杂度 $O(1)$，空间复杂度 $O(k)$。其中 $k$ 是队列的容量。

class MyCircularDeque:
  def __init__(self, k: int):
    """
    Initialize your data structure here. Set the size of the deque to be k.
    """
    self.q = [0] * k
    self.front = 0
    self.size = 0
    self.capacity = k

  def insertFront(self, value: int) -> bool:
    """
    Adds an item at the front of Deque. Return true if the operation is successful.
    """
    if self.isFull():
      return False
    if not self.isEmpty():
      self.front = (self.front - 1 + self.capacity) % self.capacity
    self.q[self.front] = value
    self.size += 1
    return True

  def insertLast(self, value: int) -> bool:
    """
    Adds an item at the rear of Deque. Return true if the operation is successful.
    """
    if self.isFull():
      return False
    idx = (self.front + self.size) % self.capacity
    self.q[idx] = value
    self.size += 1
    return True

  def deleteFront(self) -> bool:
    """
    Deletes an item from the front of Deque. Return true if the operation is successful.
    """
    if self.isEmpty():
      return False
    self.front = (self.front + 1) % self.capacity
    self.size -= 1
    return True

  def deleteLast(self) -> bool:
    """
    Deletes an item from the rear of Deque. Return true if the operation is successful.
    """
    if self.isEmpty():
      return False
    self.size -= 1
    return True

  def getFront(self) -> int:
    """
    Get the front item from the deque.
    """
    if self.isEmpty():
      return -1
    return self.q[self.front]

  def getRear(self) -> int:
    """
    Get the last item from the deque.
    """
    if self.isEmpty():
      return -1
    idx = (self.front + self.size - 1) % self.capacity
    return self.q[idx]

  def isEmpty(self) -> bool:
    """
    Checks whether the circular deque is empty or not.
    """
    return self.size == 0

  def isFull(self) -> bool:
    """
    Checks whether the circular deque is full or not.
    """
    return self.size == self.capacity


# Your MyCircularDeque object will be instantiated and called as such:
# obj = MyCircularDeque(k)
# param_1 = obj.insertFront(value)
# param_2 = obj.insertLast(value)
# param_3 = obj.deleteFront()
# param_4 = obj.deleteLast()
# param_5 = obj.getFront()
# param_6 = obj.getRear()
# param_7 = obj.isEmpty()
# param_8 = obj.isFull()

class MyCircularDeque {
  private int[] q;
  private int front;
  private int size;
  private int capacity;

  /** Initialize your data structure here. Set the size of the deque to be k. */
  public MyCircularDeque(int k) {
    q = new int[k];
    capacity = k;
  }

  /** Adds an item at the front of Deque. Return true if the operation is successful. */
  public boolean insertFront(int value) {
    if (isFull()) {
      return false;
    }
    if (!isEmpty()) {
      front = (front - 1 + capacity) % capacity;
    }
    q[front] = value;
    ++size;
    return true;
  }

  /** Adds an item at the rear of Deque. Return true if the operation is successful. */
  public boolean insertLast(int value) {
    if (isFull()) {
      return false;
    }
    int idx = (front + size) % capacity;
    q[idx] = value;
    ++size;
    return true;
  }

  /** Deletes an item from the front of Deque. Return true if the operation is successful. */
  public boolean deleteFront() {
    if (isEmpty()) {
      return false;
    }
    front = (front + 1) % capacity;
    --size;
    return true;
  }

  /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
  public boolean deleteLast() {
    if (isEmpty()) {
      return false;
    }
    --size;
    return true;
  }

  /** Get the front item from the deque. */
  public int getFront() {
    if (isEmpty()) {
      return -1;
    }
    return q[front];
  }

  /** Get the last item from the deque. */
  public int getRear() {
    if (isEmpty()) {
      return -1;
    }
    int idx = (front + size - 1) % capacity;
    return q[idx];
  }

  /** Checks whether the circular deque is empty or not. */
  public boolean isEmpty() {
    return size == 0;
  }

  /** Checks whether the circular deque is full or not. */
  public boolean isFull() {
    return size == capacity;
  }
}

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque obj = new MyCircularDeque(k);
 * boolean param_1 = obj.insertFront(value);
 * boolean param_2 = obj.insertLast(value);
 * boolean param_3 = obj.deleteFront();
 * boolean param_4 = obj.deleteLast();
 * int param_5 = obj.getFront();
 * int param_6 = obj.getRear();
 * boolean param_7 = obj.isEmpty();
 * boolean param_8 = obj.isFull();
 */

class MyCircularDeque {
public:
  vector<int> q;
  int front = 0;
  int size = 0;
  int capacity = 0;

  MyCircularDeque(int k) {
    q.assign(k, 0);
    capacity = k;
  }

  bool insertFront(int value) {
    if (isFull()) {
      return false;
    }
    if (!isEmpty()) {
      front = (front - 1 + capacity) % capacity;
    }
    q[front] = value;
    ++size;
    return true;
  }

  bool insertLast(int value) {
    if (isFull()) {
      return false;
    }
    int idx = (front + size) % capacity;
    q[idx] = value;
    ++size;
    return true;
  }

  bool deleteFront() {
    if (isEmpty()) {
      return false;
    }
    front = (front + 1) % capacity;
    --size;
    return true;
  }

  bool deleteLast() {
    if (isEmpty()) {
      return false;
    }
    --size;
    return true;
  }

  int getFront() {
    return isEmpty() ? -1 : q[front];
  }

  int getRear() {
    return isEmpty() ? -1 : q[(front + size - 1) % capacity];
  }

  bool isEmpty() {
    return size == 0;
  }

  bool isFull() {
    return size == capacity;
  }
};

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque* obj = new MyCircularDeque(k);
 * bool param_1 = obj->insertFront(value);
 * bool param_2 = obj->insertLast(value);
 * bool param_3 = obj->deleteFront();
 * bool param_4 = obj->deleteLast();
 * int param_5 = obj->getFront();
 * int param_6 = obj->getRear();
 * bool param_7 = obj->isEmpty();
 * bool param_8 = obj->isFull();
 */

type MyCircularDeque struct {
  q    []int
  size   int
  front  int
  capacity int
}

func Constructor(k int) MyCircularDeque {
  q := make([]int, k)
  return MyCircularDeque{q, 0, 0, k}
}

func (this *MyCircularDeque) InsertFront(value int) bool {
  if this.IsFull() {
    return false
  }
  if !this.IsEmpty() {
    this.front = (this.front - 1 + this.capacity) % this.capacity
  }
  this.q[this.front] = value
  this.size++
  return true
}

func (this *MyCircularDeque) InsertLast(value int) bool {
  if this.IsFull() {
    return false
  }
  idx := (this.front + this.size) % this.capacity
  this.q[idx] = value
  this.size++
  return true
}

func (this *MyCircularDeque) DeleteFront() bool {
  if this.IsEmpty() {
    return false
  }
  this.front = (this.front + 1) % this.capacity
  this.size -= 1
  return true
}

func (this *MyCircularDeque) DeleteLast() bool {
  if this.IsEmpty() {
    return false
  }
  this.size -= 1
  return true
}

func (this *MyCircularDeque) GetFront() int {
  if this.IsEmpty() {
    return -1
  }
  return this.q[this.front]
}

func (this *MyCircularDeque) GetRear() int {
  if this.IsEmpty() {
    return -1
  }
  return this.q[(this.front+this.size-1)%this.capacity]
}

func (this *MyCircularDeque) IsEmpty() bool {
  return this.size == 0
}

func (this *MyCircularDeque) IsFull() bool {
  return this.size == this.capacity
}

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * obj := Constructor(k);
 * param_1 := obj.InsertFront(value);
 * param_2 := obj.InsertLast(value);
 * param_3 := obj.DeleteFront();
 * param_4 := obj.DeleteLast();
 * param_5 := obj.GetFront();
 * param_6 := obj.GetRear();
 * param_7 := obj.IsEmpty();
 * param_8 := obj.IsFull();
 */

class MyCircularDeque {
  private vals: number[];
  private length: number;
  private size: number;
  private start: number;
  private end: number;

  constructor(k: number) {
    this.vals = new Array(k).fill(0);
    this.start = 0;
    this.end = 0;
    this.length = 0;
    this.size = k;
  }

  insertFront(value: number): boolean {
    if (this.isFull()) {
      return false;
    }

    if (this.start === 0) {
      this.start = this.size - 1;
    } else {
      this.start--;
    }
    this.vals[this.start] = value;
    this.length++;
    return true;
  }

  insertLast(value: number): boolean {
    if (this.isFull()) {
      return false;
    }

    this.vals[this.end] = value;
    this.length++;
    if (this.end + 1 === this.size) {
      this.end = 0;
    } else {
      this.end++;
    }
    return true;
  }

  deleteFront(): boolean {
    if (this.isEmpty()) {
      return false;
    }

    if (this.start + 1 === this.size) {
      this.start = 0;
    } else {
      this.start++;
    }
    this.length--;
    return true;
  }

  deleteLast(): boolean {
    if (this.isEmpty()) {
      return false;
    }

    if (this.end === 0) {
      this.end = this.size - 1;
    } else {
      this.end--;
    }
    this.length--;
    return true;
  }

  getFront(): number {
    if (this.isEmpty()) {
      return -1;
    }

    return this.vals[this.start];
  }

  getRear(): number {
    if (this.isEmpty()) {
      return -1;
    }

    if (this.end === 0) {
      return this.vals[this.size - 1];
    }
    return this.vals[this.end - 1];
  }

  isEmpty(): boolean {
    return this.length === 0;
  }

  isFull(): boolean {
    return this.length === this.size;
  }
}

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * var obj = new MyCircularDeque(k)
 * var param_1 = obj.insertFront(value)
 * var param_2 = obj.insertLast(value)
 * var param_3 = obj.deleteFront()
 * var param_4 = obj.deleteLast()
 * var param_5 = obj.getFront()
 * var param_6 = obj.getRear()
 * var param_7 = obj.isEmpty()
 * var param_8 = obj.isFull()
 */