622. 设计循环队列

原创

Michel_Rolle

修改于 2023-12-20 08:04:45

1.1K2

修改于 2023-12-20 08:04:45

文章被收录于专栏：golang分享golang分享

设计你的循环队列实现。循环队列是一种线性数据结构，其操作表现基于 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

// MyCircularQueue 结构体
type MyCircularQueue struct {
	queue []int
	k     int
}

// Constructor initialize your data structure here. Set the size of the queue to be k.
func Constructor(k int) MyCircularQueue {
	return MyCircularQueue{
		queue: make([]int, 0, k*3),
		k:     k,
	}
}

// EnQueue insert an element into the circular queue. Return true if the operation is successful.
func (m *MyCircularQueue) EnQueue(value int) bool {
	if len(m.queue) == m.k {
		return false
	}
	m.queue = append(m.queue, value)
	return true
}

// DeQueue delete an element from the circular queue. Return true if the operation is successful.
func (m *MyCircularQueue) DeQueue() bool {
	if len(m.queue) == 0 {
		return false
	}

	m.queue = m.queue[1:]
	return true
}

// Front get the front item from the queue.
func (m *MyCircularQueue) Front() int {
	if len(m.queue) == 0 {
		return -1
	}

	return m.queue[0]
}

// Rear get the last item from the queue. */
func (m *MyCircularQueue) Rear() int {
	if len(m.queue) == 0 {
		return -1
	}
	return m.queue[len(m.queue)-1]
}

// IsEmpty checks whether the circular queue is empty or not. */
func (m *MyCircularQueue) IsEmpty() bool {
	return len(m.queue) == 0
}

// IsFull checks whether the circular queue is full or not. */
func (m *MyCircularQueue) IsFull() bool {
	return len(m.queue) == m.k
}

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * obj := Constructor(k);
 * param_1 := obj.EnQueue(value);
 * param_2 := obj.DeQueue();
 * param_3 := obj.Front();
 * param_4 := obj.Rear();
 * param_5 := obj.IsEmpty();
 * param_6 := obj.IsFull();
 */

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

2023腾讯·技术创作特训营第三期