JavaScript / TypeScript / PHP / Golang / Python / Java / C# / C / C++ 构造循环队列，链表和数组，2 解法求解《622. 设计循环队列》
循环队列构造图示
例题
622. 设计循环队列
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。
示例：
MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false，队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
circularQueue.enQueue(4); // 返回 true
circularQueue.Rear(); // 返回 4
答案
链表
var MyCircularQueue = function(k) {
this.capacity = k
this.size = 0
this.head = null
this.tail = null
};
MyCircularQueue.prototype.enQueue = function(value) {
if (this.isFull()) return false
const n = new ListNode(value)
if (this.head === null) {
this.head = n
this.tail = n
} else {
this.tail.next = n
this.tail = n
}
this.size++
return true
};
MyCircularQueue.prototype.deQueue = function() {
if (this.isEmpty()) return false
this.head = this.head.next
this.size--
return true
};
MyCircularQueue.prototype.Front = function() {
if (this.isEmpty()) return -1
return this.head.val
};
MyCircularQueue.prototype.Rear = function() {
if (this.isEmpty()) return -1
return this.tail.val
};
MyCircularQueue.prototype.isEmpty = function() {
return this.size === 0
};
MyCircularQueue.prototype.isFull = function() {
return this.size === this.capacity
};class MyCircularQueue {
capacity: number
size: number
head: ListNode
tail: ListNode
constructor(k: number) {
this.capacity = k
this.size = 0
this.head = null
this.tail = null
}
enQueue(value: number): boolean {
if (this.isFull()) return false
const n = new ListNode(value)
if (this.head === null) {
this.head = n
this.tail = n
} else {
this.tail.next = n
this.tail = n
}
this.size++
return true
}
deQueue(): boolean {
if (this.isEmpty()) return false
this.head = this.head.next
this.size--
return true
}
Front(): number {
if (this.isEmpty()) return -1
return this.head.val
}
Rear(): number {
if (this.isEmpty()) return -1
return this.tail.val
}
isEmpty(): boolean {
return this.size === 0
}
isFull(): boolean {
return this.size === this.capacity
}
}class MyCircularQueue {
private $capacity;
private $size;
private $head;
private $tail;
function __construct($k) {
$this->capacity = $k;
$this->size = 0;
$this->head = null;
$this->tail = null;
}
function enQueue($value) {
if ($this->isFull()) return false;
$n = new ListNode($value);
if ($this->head === null) {
$this->tail = $this->head = $n;
} else {
$this->tail = $this->tail->next = $n;
}
$this->size++;
return true;
}
function deQueue() {
if ($this->isEmpty()) return false;
$this->head = $this->head->next;
$this->size--;
return true;
}
function Front() {
if ($this->isEmpty()) return -1;
return $this->head->val;
}
function Rear() {
if ($this->isEmpty()) return -1;
return $this->tail->val;
}
function isEmpty() {
return $this->size === 0;
}
function isFull() {
return $this->size === $this->capacity;
}
}type MyCircularQueue struct {
capacity int
size int
head *ListNode
tail *ListNode
}
func Constructor(k int) MyCircularQueue {
return MyCircularQueue{
k,
0,
nil,
nil,
}
}
func (this *MyCircularQueue) EnQueue(value int) bool {
if this.IsFull() {
return false
}
n := &ListNode{value, nil}
if this.head == nil {
this.head = n
this.tail = n
} else {
this.tail.Next = n
this.tail = n
}
this.size++
return true
}
func (this *MyCircularQueue) DeQueue() bool {
if this.IsEmpty() {
return false
}
this.head = this.head.Next
this.size--
return true
}
func (this *MyCircularQueue) Front() int {
if this.IsEmpty() {
return -1
}
return this.head.Val
}
func (this *MyCircularQueue) Rear() int {
if this.IsEmpty() {
return -1
}
return this.tail.Val
}
func (this *MyCircularQueue) IsEmpty() bool {
return this.size == 0
}
func (this *MyCircularQueue) IsFull() bool {
return this.size == this.capacity
}class MyCircularQueue:
def __init__(self, k: int):
self.capacity = k
self.size = 0
self.head = None
self.tail = None
def enQueue(self, value: int) -> bool:
if self.isFull(): return False
n: Optional[ListNode] = ListNode(value)
if self.head == None:
self.tail = n
self.head = n
else:
self.tail.next = n
self.tail = n
self.size += 1
return True
def deQueue(self) -> bool:
if self.isEmpty(): return False
self.head = self.head.next
self.size -= 1
return True
def Front(self) -> int:
if self.isEmpty(): return -1
return self.head.val
def Rear(self) -> int:
if self.isEmpty(): return -1
return self.tail.val
def isEmpty(self) -> bool:
return self.size == 0
def isFull(self) -> bool:
return self.size == self.capacityclass MyCircularQueue {
private int capacity;
private int size;
private ListNode head;
private ListNode tail;
public MyCircularQueue(int k) {
capacity = k;
size = 0;
head = null;
tail = null;
}
public boolean enQueue(int value) {
if (isFull()) return false;
ListNode n = new ListNode(value);
if (head == null) {
tail = head = n;
} else {
tail = tail.next = n;
}
size++;
return true;
}
public boolean deQueue() {
if (isEmpty()) return false;
head = head.next;
size--;
return true;
}
public int Front() {
if (isEmpty()) return -1;
return head.val;
}
public int Rear() {
if (isEmpty()) return -1;
return tail.val;
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == capacity;
}
}public class MyCircularQueue {
private int capacity;
private int size;
private ListNode head;
private ListNode tail;
public MyCircularQueue(int k) {
capacity = k;
size = 0;
head = null;
tail = null;
}
public bool EnQueue(int value) {
if (IsFull()) return false;
ListNode n = new ListNode(value);
if (head == null) {
head = n;
tail = n;
} else {
tail.next = n;
tail = n;
}
size++;
return true;
}
public bool DeQueue() {
if (IsEmpty()) return false;
head = head.next;
size--;
return true;
}
public int Front() {
if (IsEmpty()) return -1;
return head.val;
}
public int Rear() {
if (IsEmpty()) return -1;
return tail.val;
}
public bool IsEmpty() {
return this.size == 0;
}
public bool IsFull() {
return this.size == this.capacity;
}
}typedef struct {
int capactiy;
int size;
struct ListNode* head;
struct ListNode* tail;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj = malloc(sizeof(MyCircularQueue));
obj->capactiy = k;
obj->size = 0;
obj->head = NULL;
obj->tail = NULL;
return obj;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if (obj->size == obj->capactiy) return false;
struct ListNode* n = malloc(sizeof(struct ListNode));
n->val = value;
n->next = NULL;
if (obj->head == NULL) {
obj->head = n;
obj->tail = n;
} else {
obj->tail->next = n;
obj->tail = n;
}
obj->size++;
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if (obj->size == 0) return false;
struct ListNode* node = obj->head;
obj->head = obj->head->next;
free(node);
obj->size--;
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
if (obj->size == 0) return -1;
return obj->head->val;
}
int myCircularQueueRear(MyCircularQueue* obj) {
if (obj->size == 0) return -1;
return obj->tail->val;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->size == 0;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return obj->size == obj->capactiy;
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj);
}class MyCircularQueue {
private:
int capacity;
int size;
ListNode* head;
ListNode* tail;
public:
MyCircularQueue(int k) {
capacity = k;
size = 0;
tail = head = nullptr;
}
bool enQueue(int value) {
if (isFull()) return false;
ListNode* n = new ListNode(value);
if (head == nullptr) {
tail = head = n;
} else {
tail = tail->next = n;
}
size++;
return true;
}
bool deQueue() {
if (isEmpty()) return false;
head = head->next;
size--;
return true;
}
int Front() {
if (isEmpty()) return -1;
return head->val;
}
int Rear() {
if (isEmpty()) return -1;
return tail->val;
}
bool isEmpty() {
return size == 0;
}
bool isFull() {
return size == capacity;
}
};数组
var MyCircularQueue = function(k) {
this.capacity = k + 1
this.ar = new Uint16Array(this.capacity)
this.front = this.rear = 0
};
MyCircularQueue.prototype.enQueue = function(value) {
if (this.isFull()) return false
this.ar[this.rear] = value
this.rear = (this.rear + 1) % this.capacity
return true
};
MyCircularQueue.prototype.deQueue = function() {
if (this.isEmpty()) return false
this.front = (this.front + 1) % this.capacity
return true
};
MyCircularQueue.prototype.Front = function() {
if (this.isEmpty()) return -1
return this.ar[this.front]
};
MyCircularQueue.prototype.Rear = function() {
if (this.isEmpty()) return -1
return this.ar[(this.rear + this.capacity - 1) % this.capacity]
};
MyCircularQueue.prototype.isEmpty = function() {
return this.front === this.rear
};
MyCircularQueue.prototype.isFull = function() {
return (this.rear + 1) % this.capacity === this.front
};class MyCircularQueue {
capacity: number
ar: number[]
front: number = 0
rear: number = 0
constructor(k: number) {
this.capacity = k + 1
this.ar = new Array(k + 1)
}
enQueue(value: number): boolean {
if (this.isFull()) return false
this.ar[this.rear] = value
this.rear = (this.rear + 1) % this.capacity
return true
}
deQueue(): boolean {
if (this.isEmpty()) return false
this.front = (this.front + 1) % this.capacity
return true
}
Front(): number {
if (this.isEmpty()) return -1
return this.ar[this.front]
}
Rear(): number {
if (this.isEmpty()) return -1
return this.ar[(this.rear + this.capacity - 1) % this.capacity]
}
isEmpty(): boolean {
return this.front === this.rear
}
isFull(): boolean {
return (this.rear + 1) % this.capacity === this.front
}
}class MyCircularQueue {
function __construct($k) {
$this->capacity = $k + 1;
$this->ar = array_fill(0, $this->capacity, 0);
$this->front = 0;
$this->rear = 0;
}
function enQueue($value) {
if ($this->isFull()) return false;
$this->ar[$this->rear] = $value;
$this->rear = ($this->rear + 1) % $this->capacity;
return true;
}
function deQueue() {
if ($this->isEmpty()) return false;
$this->front = ($this->front + 1) % $this->capacity;
return true;
}
function Front() {
if ($this->isEmpty()) return -1;
return $this->ar[$this->front];
}
function Rear() {
if ($this->isEmpty()) return -1;
return $this->ar[($this->rear + $this->capacity - 1) % $this->capacity];
}
function isEmpty() {
return $this->front === $this->rear;
}
function isFull() {
return ($this->rear + 1) % $this->capacity === $this->front;
}
}
type MyCircularQueue struct {
ar []int
capacity int
front int
rear int
}
func Constructor(k int) MyCircularQueue {
return MyCircularQueue {
make([]int, k + 1),
k + 1,
0,
0,
}
}
func (this *MyCircularQueue) EnQueue(value int) bool {
if this.IsFull() == true {
return false
}
this.ar[this.rear] = value
this.rear = (this.rear + 1) % this.capacity
return true
}
func (this *MyCircularQueue) DeQueue() bool {
if this.IsEmpty() == true {
return false
}
this.front = (this.front + 1) % this.capacity
return true
}
func (this *MyCircularQueue) Front() int {
if this.IsEmpty() == true {
return -1
}
return this.ar[this.front]
}
func (this *MyCircularQueue) Rear() int {
if this.IsEmpty() == true {
return -1
}
return this.ar[(this.rear + this.capacity - 1) % this.capacity]
}
func (this *MyCircularQueue) IsEmpty() bool {
return this.front == this.rear
}
func (this *MyCircularQueue) IsFull() bool {
return (this.rear + 1) % this.capacity == this.front
}class MyCircularQueue:
def __init__(self, k: int):
self.capacity = k + 1
self.a = [0] * self.capacity
self.front = 0
self.rear = 0
def enQueue(self, value: int) -> bool:
if self.isFull(): return False
self.a[self.rear] = value
self.rear = (self.rear + 1) % self.capacity
return True
def deQueue(self) -> bool:
if self.isEmpty(): return False
self.front = (self.front + 1) % self.capacity
return True
def Front(self) -> int:
if self.isEmpty(): return -1
return self.a[self.front]
def Rear(self) -> int:
if self.isEmpty(): return -1
return self.a[(self.rear + self.capacity - 1) % self.capacity]
def isEmpty(self) -> bool:
return self.front == self.rear
def isFull(self) -> bool:
return (self.rear + 1) % self.capacity == self.frontclass MyCircularQueue {
private final int capacity;
private int[] a;
private int front;
private int rear;
public MyCircularQueue(int k) {
capacity = k + 1;
a = new int[capacity];
front = 0;
rear = 0;
}
public boolean enQueue(int value) {
if (isFull()) return false;
a[rear] = value;
rear = (rear + 1) % capacity;
return true;
}
public boolean deQueue() {
if (isEmpty()) return false;
front = (front + 1) % capacity;
return true;
}
public int Front() {
if (isEmpty()) return -1;
return a[front];
}
public int Rear() {
if (isEmpty()) return -1;
return a[(rear + capacity - 1) % capacity];
}
public boolean isEmpty() {
return front == rear;
}
public boolean isFull() {
return (rear + 1) % capacity == front;
}
}public class MyCircularQueue {
private int capacity;
private int[] a;
private int front;
private int rear;
public MyCircularQueue(int k) {
capacity = k + 1;
a = new int[capacity];
front = 0;
rear = 0;
}
public bool EnQueue(int value) {
if (IsFull() == true) return false;
a[rear] = value;
rear = (rear + 1) % capacity;
return true;
}
public bool DeQueue() {
if (IsEmpty() == true) return false;
front = (front + 1) % capacity;
return true;
}
public int Front() {
if (IsEmpty() == true) return -1;
return a[front];
}
public int Rear() {
if (IsEmpty() == true) return -1;
return a[(rear + capacity - 1) % capacity];
}
public bool IsEmpty() {
return front == rear;
}
public bool IsFull() {
return (rear + 1) % capacity == front;
}
}typedef struct {
int capacity;
int* a;
int front;
int rear;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj = malloc(sizeof(MyCircularQueue));
obj->capacity = k + 1;
obj->a = malloc(sizeof(int) * (k + 1));
obj->front = 0;
obj->rear = 0;
return obj;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if ((obj->rear + 1) % obj->capacity == obj->front) return false;
obj->a[obj->rear] = value;
obj->rear = (obj->rear + 1) % obj->capacity;
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if (obj->front == obj->rear) return false;
obj->front = (obj->front + 1) % obj->capacity;
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
if (obj->front == obj->rear) return -1;
return obj->a[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) {
if (obj->front == obj->rear) return -1;
return obj->a[(obj->rear + obj->capacity - 1) % obj->capacity];
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->front == obj->rear;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->rear + 1) % obj->capacity == obj->front;
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->a);
free(obj);
}class MyCircularQueue {
private:
int capacity;
vector<int> a;
int front;
int rear;
public:
MyCircularQueue(int k) {
capacity = k + 1;
a = vector<int>(capacity);
front = 0;
rear = 0;
}
bool enQueue(int value) {
if (isFull()) return false;
a[rear] = value;
rear = (rear + 1) % capacity;
return true;
}
bool deQueue() {
if (isEmpty()) return false;
front = (front + 1) % capacity;
return true;
}
int Front() {
if (isEmpty()) return -1;
return a[front];
}
int Rear() {
if (isEmpty()) return -1;
return a[(rear + capacity - 1) % capacity];
}
bool isEmpty() {
return front == rear;
}
bool isFull() {
return (rear + 1) % capacity == front;
}
};