641. 设计循环双端队列

Medium

题目描述

设计实现双端队列。

实现 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 myCircularDeque = new MyCircularDeque(3);
myCircularDeque.insertLast(1);  // 返回 True
myCircularDeque.insertLast(2);  // 返回 True
myCircularDeque.insertFront(3); // 返回 True
myCircularDeque.insertFront(4); // 返回 False，队列已满
myCircularDeque.getRear();      // 返回 2
myCircularDeque.isFull();       // 返回 True
myCircularDeque.deleteLast();   // 返回 True
myCircularDeque.insertFront(4); // 返回 True
myCircularDeque.getFront();     // 返回 4

提示：

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

解题思路

这道题要求设计一个循环双端队列，支持在队列两端进行插入和删除操作。有两种主要的实现方式：

方法一：数组实现（推荐） 使用固定大小的数组来实现循环双端队列。关键是维护两个指针：front 和 rear，以及当前元素个数 size。

初始化时，front = 0，rear = 0，size = 0
插入头部：front = (front - 1 + capacity) % capacity
插入尾部：rear = (rear + 1) % capacity
删除头部：front = (front + 1) % capacity
删除尾部：rear = (rear - 1 + capacity) % capacity

使用 size 来判断队列是否为空或已满，避免了 front 和 rear 重合时的歧义问题。

方法二：双向链表实现 使用双向链表节点，维护头尾指针。虽然概念上更直观，但在空间效率上不如数组实现。

数组实现在时间和空间复杂度上都更优，是推荐解法。所有操作的时间复杂度都是 O(1)，空间复杂度是 O(k)。

代码实现

class MyCircularDeque {
private:
    vector<int> data;
    int front;
    int rear;
    int size;
    int capacity;
    
public:
    MyCircularDeque(int k) {
        data.resize(k);
        capacity = k;
        front = 0;
        rear = 0;
        size = 0;
    }
    
    bool insertFront(int value) {
        if (isFull()) return false;
        front = (front - 1 + capacity) % capacity;
        data[front] = value;
        size++;
        return true;
    }
    
    bool insertLast(int value) {
        if (isFull()) return false;
        data[rear] = value;
        rear = (rear + 1) % capacity;
        size++;
        return true;
    }
    
    bool deleteFront() {
        if (isEmpty()) return false;
        front = (front + 1) % capacity;
        size--;
        return true;
    }
    
    bool deleteLast() {
        if (isEmpty()) return false;
        rear = (rear - 1 + capacity) % capacity;
        size--;
        return true;
    }
    
    int getFront() {
        if (isEmpty()) return -1;
        return data[front];
    }
    
    int getRear() {
        if (isEmpty()) return -1;
        return data[(rear - 1 + capacity) % capacity];
    }
    
    bool isEmpty() {
        return size == 0;
    }
    
    bool isFull() {
        return size == capacity;
    }
};

class MyCircularDeque:

    def __init__(self, k: int):
        self.data = [0] * k
        self.capacity = k
        self.front = 0
        self.rear = 0
        self.size = 0

    def insertFront(self, value: int) -> bool:
        if self.isFull():
            return False
        self.front = (self.front - 1 + self.capacity) % self.capacity
        self.data[self.front] = value
        self.size += 1
        return True

    def insertLast(self, value: int) -> bool:
        if self.isFull():
            return False
        self.data[self.rear] = value
        self.rear = (self.rear + 1) % self.capacity
        self.size += 1
        return True

    def deleteFront(self) -> bool:
        if self.isEmpty():
            return False
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return True

    def deleteLast(self) -> bool:
        if self.isEmpty():
            return False
        self.rear = (self.rear - 1 + self.capacity) % self.capacity
        self.size -= 1
        return True

    def getFront(self) -> int:
        if self.isEmpty():
            return -1
        return self.data[self.front]

    def getRear(self) -> int:
        if self.isEmpty():
            return -1
        return self.data[(self.rear - 1 + self.capacity) % self.capacity]

    def isEmpty(self) -> bool:
        return self.size == 0

    def isFull(self) -> bool:
        return self.size == self.capacity

public class MyCircularDeque {
    private int[] data;
    private int front;
    private int rear;
    private int size;
    private int capacity;

    public MyCircularDeque(int k) {
        data = new int[k];
        capacity = k;
        front = 0;
        rear = 0;
        size = 0;
    }
    
    public bool InsertFront(int value) {
        if (IsFull()) return false;
        front = (front - 1 + capacity) % capacity;
        data[front] = value;
        size++;
        return true;
    }
    
    public bool InsertLast(int value) {
        if (IsFull()) return false;
        data[rear] = value;
        rear = (rear + 1) % capacity;
        size++;
        return true;
    }
    
    public bool DeleteFront() {
        if (IsEmpty()) return false;
        front = (front + 1) % capacity;
        size--;
        return true;
    }
    
    public bool DeleteLast() {
        if (IsEmpty()) return false;
        rear = (rear - 1 + capacity) % capacity;
        size--;
        return true;
    }
    
    public int GetFront() {
        if (IsEmpty()) return -1;
        return data[front];
    }
    
    public int GetRear() {
        if (IsEmpty()) return -1;
        return data[(rear - 1 + capacity) % capacity];
    }
    
    public bool IsEmpty() {
        return size == 0;
    }
    
    public bool IsFull() {
        return size == capacity;
    }
}

var MyCircularDeque = function(k) {
    this.capacity = k;
    this.size = 0;
    this.front = 0;
    this.rear = 0;
    this.data = new Array(k);
};

MyCircularDeque.prototype.insertFront = function(value) {
    if (this.isFull()) return false;
    if (this.size === 0) {
        this.data[this.front] = value;
    } else {
        this.front = (this.front - 1 + this.capacity) % this.capacity;
        this.data[this.front] = value;
    }
    this.size++;
    return true;
};

MyCircularDeque.prototype.insertLast = function(value) {
    if (this.isFull()) return false;
    if (this.size === 0) {
        this.data[this.rear] = value;
    } else {
        this.rear = (this.rear + 1) % this.capacity;
        this.data[this.rear] = value;
    }
    this.size++;
    return true;
};

MyCircularDeque.prototype.deleteFront = function() {
    if (this.isEmpty()) return false;
    if (this.size === 1) {
        this.size = 0;
        return true;
    }
    this.front = (this.front + 1) % this.capacity;
    this.size--;
    return true;
};

MyCircularDeque.prototype.deleteLast = function() {
    if (this.isEmpty()) return false;
    if (this.size === 1) {
        this.size = 0;
        return true;
    }
    this.rear = (this.rear - 1 + this.capacity) % this.capacity;
    this.size--;
    return true;
};

MyCircularDeque.prototype.getFront = function() {
    if (this.isEmpty()) return -1;
    return this.data[this.front];
};

MyCircularDeque.prototype.getRear = function() {
    if (this.isEmpty()) return -1;
    return this.data[this.rear];
};

MyCircularDeque.prototype.isEmpty = function() {
    return this.size === 0;
};

MyCircularDeque.prototype.isFull = function() {
    return this.size === this.capacity;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

操作	时间复杂度	空间复杂度
所有操作	O(1)	O(k)

时间复杂度：O(1) - 所有操作都是常数时间
空间复杂度：O(k) - 需要大小为 k 的数组存储数据

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目