设计循环队列

Laikee

发布于 2022-04-25 18:11:06

1630

发布于 2022-04-25 18:11:06

文章被收录于专栏：Laikee Tech Space

简单记录一下思路： 1, 队列为空状态：head = tail = -1; 2, 入队：如果入队前是空的，则将head 和 tail 都向右移一位，也就是下标为0的地方; 否则只需右移tail 3, 出队：如果出队时队列不为空且为最后一个元素(head == tail)，则置head = tail = -1, 否则只需右移head 4, 取队首：只要队不为空，head指向队首元素 5, 取对尾：同理，tail指向队尾元素 6, 判空：见1 7, 判满：tail右移发现与head重合了，则没有地方放入新的元素了，此时为满

class MyCircularQueue:

    def __init__(self, k: int):
        self.head, self.tail = -1, -1
        self.list = {}
        self.size = k
    def enQueue(self, value: int) -> bool:
        if self.isEmpty():
            self.head = 0
            self.tail = 0
            self.list[self.tail] = value
            return True
        if self.isFull():
            return False
        self.tail = (self.tail+1) % self.size
        self.list[self.tail] = value
        return True
    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        if self.head == self.tail:
            self.head = -1
            self.tail = -1
            return True
        self.head = (self.head+1) % self.size
        return True

    def Front(self) -> int:
        if self.isEmpty():
            return -1
        return self.list[self.head]

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        return self.list[self.tail]

    def isEmpty(self) -> bool:
        if self.tail == self.head and self.head == -1:
            return True
        return False

    def isFull(self) -> bool:
        if (self.tail+1) % self.size == self.head:
            return True
        return False


# Your MyCircularQueue object will be instantiated and called as such:
# obj = MyCircularQueue(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()

又想了下，主要是要约定什么状态是队列为空的，且有两个状态比较特殊：一个是，队列为空的时候插入的第一个元素（需要同时移动head 和 tail），此时head = tail = 0，另一个是，队列只有一个元素且要删除的时候（需要同时置head 和 tail 为 -1）