数据结构-循环队列（Python实现）

分手后的思念是犯贱 2021-10-19 04:14 427阅读 0赞

今天我们来到了循环队列这一节，[之前的文章][Link 1]中，我介绍过了用python自带的列表来实现队列，这是最简单的实现方法。

但是，我们都知道，在列表中删除第一个元素和删除最后一个元素花费的时间代价是不一样的，删除列表的第一个元素，那么在它之后的所有元素都要进行移动。所以当列表特别长的时候，这个代价就比较明显了。我们本文介绍的循环队列可以避免这个问题，同样我们上篇文章提到的用链表实现的方法也可以避免。

下面，我们来介绍循环队列。

## 循坏队列 ##

循环队列，就是将普通的队列首尾连接起来， 形成一个环状，并分别设置首尾指针，用来指明队列的头和尾。每当我们插入一个元素，尾指针就向后移动一位，当然，在这里我们队列的最大长度是提前定义好的，当我们弹出一个元素，头指针就向后移动一位。

这样，列表中就不存在删除操作，只有修改操作，从而避免了删除前面节点造成的代价大的问题。

好，话不多说，我们用代码来实现一下

class Loopqueue:
        def __init__(self, length):
            self.head = 0
            self.tail = 0
            self.maxSize = length
            self.cnt = 0
            self.__list = [None]*length

这里同样，我们定义一个队列类，在实例化循环队列的时候，要求指定队列的大小，除了首尾指针以及队列最大长度之外，我们还声明一个表示队列当前长度的属性cnt。

接下来我们给队列增加一些操作：

*  判空

def isEmpty(self):
            return self.cnt == 0

*  判满

def isFull(self):
            return self.cnt == self.maxSize

*  添加元素

def push(self, data):
            if self.isFull():
                return False
            if self.isEmpty():
                self.__list[0] = data
                self.head = 0
                self.tail = 0
                self.cnt = 1
                return True
            self.tail = (self.tail+1)%self.maxSize
            self.cnt += 1
            self.__list[self.tail] = data
            return True

*  弹出元素

def pop(self):
            if self.isEmpty():
                return False
            data = self.__list[self.head]
            self.head = (self.head+1)%self.maxSize
            self.cnt -= 1
            return data

*  清空队列

def clear(self):
            self.head = 0
            self.tail = 0
            self.cnt = 0
            return True

*  定义len和print函数

def __len__(self):
            return self.cnt
    
        def __str__(self):
            s = ''
            for i in range(self.cnt):
                index = (i + self.head) % self.maxSize
                s += str(self.__list[index])+' '
            return s

OK，我们的循环队列类就定义好了，如果你看过介绍队列的文章，就会发现循环队列和普通队列的操作在逻辑上还是有一些相似的。

代码并不难，相信你已经完全理解了，自己动手操作一下吧。

你还了解哪些队列类型呢？留言告诉我吧。

转载于:https://www.cnblogs.com/dongyangblog/p/11198456.html

[Link 1]: https://www.cnblogs.com/dongyangblog/p/11192532.html