2022-08-01每日一题:622 设计循环队列

2022-08-02
3分钟阅读时长

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

 

提示:

  • 所有的值都在 0 至 1000 的范围内;
  • 操作数将在 1 至 1000 的范围内;
  • 请不要使用内置的队列库。
### 方法一:数组

写法一

type MyCircularQueue struct {
    head, tail, size int
	nums []int
}


func Constructor(k int) MyCircularQueue {
    return MyCircularQueue{size:k, nums: make([]int, k)}
}


func (this *MyCircularQueue) EnQueue(value int) bool {
    if this.IsFull() {
        return false
    }
    this.nums[this.tail % this.size] = value
    this.tail++
    return this.tail >= 0
}


func (this *MyCircularQueue) DeQueue() bool {
    if this.IsEmpty() {
        return false
    }
    this.head++
    return this.head >= 0
}


func (this *MyCircularQueue) Front() int {
    if this.IsEmpty() {
        return -1
    }
    return this.nums[this.head%this.size]
}


func (this *MyCircularQueue) Rear() int {
    if this.IsEmpty() {
        return -1
    }
    return this.nums[(this.tail-1)%this.size]
}


func (this *MyCircularQueue) IsEmpty() bool {
	return this.head == this.tail
}


func (this *MyCircularQueue) IsFull() bool {
	return this.tail - this.head == this.size
}


/**
 * 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();
 */

写法二

// https://leetcode.cn/problems/design-circular-queue/solution/she-ji-xun-huan-dui-lie-by-leetcode-solu-1w0a/
type MyCircularQueue struct {
    front, rear int
    elements    []int
}

func Constructor(k int) MyCircularQueue {
    return MyCircularQueue{elements: make([]int, k+1)}
}

func (q *MyCircularQueue) EnQueue(value int) bool {
    if q.IsFull() {
        return false
    }
    q.elements[q.rear] = value
    q.rear = (q.rear + 1) % len(q.elements)
    return true
}

func (q *MyCircularQueue) DeQueue() bool {
    if q.IsEmpty() {
        return false
    }
    q.front = (q.front + 1) % len(q.elements)
    return true
}

func (q MyCircularQueue) Front() int {
    if q.IsEmpty() {
        return -1
    }
    return q.elements[q.front]
}

func (q MyCircularQueue) Rear() int {
    if q.IsEmpty() {
        return -1
    }
    return q.elements[(q.rear-1+len(q.elements))%len(q.elements)]
}

func (q MyCircularQueue) IsEmpty() bool {
    return q.rear == q.front
}

func (q MyCircularQueue) IsFull() bool {
    return (q.rear+1)%len(q.elements) == q.front
}
  • 时间复杂度:初始化和每项操作的时间复杂度均为 O(1)。
  • 空间复杂度:O(k)O(k),其中 kk 为给定的队列元素数目。

方法二:链表

type ListNode struct {
    Val int
    Next *ListNode
}
type MyCircularQueue struct {
    head, tail     *ListNode
    capacity, size int
}

func Constructor(k int) MyCircularQueue {
    return MyCircularQueue{capacity: k}
}

func (q *MyCircularQueue) EnQueue(value int) bool {
    if q.IsFull() {
        return false
    }
    node := &ListNode{Val: value}
    if q.head == nil {
        q.head = node
        q.tail = node
    } else {
        q.tail.Next = node
        q.tail = node
    }
    q.size++
    return true
}

func (q *MyCircularQueue) DeQueue() bool {
    if q.IsEmpty() {
        return false
    }
    q.head = q.head.Next
    q.size--
    return true
}

func (q MyCircularQueue) Front() int {
    if q.IsEmpty() {
        return -1
    }
    return q.head.Val
}

func (q MyCircularQueue) Rear() int {
    if q.IsEmpty() {
        return -1
    }
    return q.tail.Val
}

func (q MyCircularQueue) IsEmpty() bool {
    return q.size == 0
}

func (q MyCircularQueue) IsFull() bool {
    return q.size == q.capacity
}
  • 时间复杂度:初始化和每项操作的时间复杂度均为 O(1)。
  • 空间复杂度:O(k)O(k),其中 kk 为给定的队列元素数目。

LeetCode题库地址