面试官竟拿循环队列为难我...

laohanshuibi 2021-09-06 原文

大家好，我是程序员学长。今天我们来聊一聊循环队列那些事。

上周群里的小伙伴去面试快手大数据岗位，竟然让实现一个循环队列…，今天我们就来分析一下。

Tips: 你也许会有疑问，面试数据岗，为什么还要问这个问题。其实，循环队列在软件开发中是经常需要用到了一个技术，比如大数据基石MapReduce中就有环形缓冲区的概念、在Redis主从同步中也用到了环形缓存区。

问题描述

设计一个循环队列实现。支持如下操作。

MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。

分析问题

要想了解什么是循环队列，我们就需要先知道什么是队列。队列是一种先进先出（FIFO）的线性数据结构，就和我们排队买东西一样，先来的先买，后来的后买。如下图所示：

循环队列是在队列的基础上，把队尾和队首连接在一起形成一个循环结构。

我们都知道算法是建立在数据结构之上的，要想实现题目要求，我们就需要先确定元素是采用何种数据结构来存储的。

对于队列来说，我们一般是采用数组来进行存储的。所以这里，我们也使用数组来存储元素。因为数组不是环形结构，只是一种线性的数据结构，所以我们需要通过操作数组的索引来模拟构建一个虚拟的环。

在循环队列中最主要的就是确定队列为空和队列为满的条件。

下面我们来看一下代码的实现。

class MyCircularQueue(object):

    def __init__(self, k):
        self.queue = [0]*k
        self.head = 0
        self.tail = 0
        self.capacity = k

    def enQueue(self, value):
        #入队
        #判断队列是否满
        if self.head==(self.tail+1)%self.capacity:
            return False
        self.queue[self.tail] = value
        self.tail=(self.tail+1)%self.capacity
        return True

    def deQueue(self):
        #出队
        if self.head == self.tail:
            return False
        self.head=(self.head+1)%self.capacity
        return True

    def Front(self):
        #队首元素
        if self.head == self.tail:
            return -1
        return self.queue[self.head]

    def Rear(self):
        #队尾元素
        #判断是否为空
        if self.head == self.tail:
            return -1
        return self.queue[self.tail-1]

    def isEmpty(self):
        return self.head == self.tail

    def isFull(self):

        return self.head == (self.tail+1)%self.capacity