python循环队列_用python实现循环顺序队列的基本操作

循环队列

什么是循环队列？

相较于普通的队列（详见：python实现队列(点击跳转)），循环队列的数据区是固定的（在规定了队列的大小后），而传统的队列的数据区是动态变化的。

而循环队列的本质：固定的数据区域，变动的索引指向

例如：在弹出队首元素的时候，并不会真的将原来的队首元素删除，而是将队首元素的索引变量改变，从而使其指向新的队首元素。如下图所示：

可见并未真正删除原来索引为0的元素（原来的队首），仅仅只是将新的队首的索引赋值给队头变量head

---

为什么要引入循环队列

简单来讲就是循环队列的执行效率较高

举个简单的例子：

传统队列的，弹出队首的方法，使用的是列表内置的pop()方法，但是其时间复杂度是O(n)，因为当列表中的第一个元素被删除后，其他所有的元素都会向前移动一位。但是循环队列呢？根本不会改变任何的底层中的元素，仅仅只是将索引变一下即可，时间复杂度为O(1),执行效率高，故，在真正使用队列的时候一般都是使用循环队列。

---

循环队列的顺序表实现

基本框架

队列顺序表实现的基本框架（基本参数）如下图所示：

1. 队列的头索引head
2. 队列的实际长度length
3. 队列的最大尺寸size
4. 存储队列的顺序表item

代码实现如下：

class Queue:
    def __init__(self,size):
        self.items = [None] * size
        self.size = size
        self._lenth = 0
        self.head = 0
1
2
3
4
5
6
'
运行
运行

值得注意的是:因为队列的大小是固定的，所以当我们创建顺序表的时候，需要创建一个长度为size的初始化的顺序表才行，如上面的第3行代码。

self.items = [None] * size
1

---

基础方法

基础方法包括：

• 返回链表的长度
• 判断链表是否为空

代码实现如下：

    def is_empty(self):
        return  self._lenth == 0

    def length(self):
        return self._lenth
1
2
3
4
5

坚决不可以用以下代码判断是否为空

    def is_empty(self):
        return  self.items == []
1
2
'
运行
运行

因为循环链表中的顺序表中一直有元素,不为空。

---

给队尾添加值data(重点内容)

1. 判断队列是否已满
2. 队尾索引
3. 将值赋值给索引

• 情况1如下：

• 情况2如下：

到这里都可以看出，为节点的索引公式为：
$$\begin{gathered} index=self.head+self.\_lenth \\ 待添加值的索引=队首索引+队列实际长度 \\ indexofthevaluetobeadded=indexoftheheadofthequeue+actuallengthofthequeue \end{gathered}$$
但是真的就这样了？没有其他的情况了？

• 情况3如下：

我们可以看出，我们想给0的位置添加索引，但是算出来的却是8，进行对size取余即可（至于为什么取余，小伙伴自行研究哈！！）

故最终的公式为：
$$index=(self.head+self.\_lenth)\%self.size$$
代码实现：

        def push(self,data):
        if self._lenth < self.size:
            idx = (self._lenth + self.head) % self.size
            self.items[idx] = data
            self._lenth += 1
        else:
            print('队列已经满了')
1
2
3
4
5
6
7
'
运行
运行

---

弹出队首元素

如下图可知，想要弹出索引为2的队首元素3，步骤如下

1. 将原来的队首元素存储到一个新的变量，用于返回值
2. 找到新的队首元素的索引（也就是下图中的索引3）
3. 将head属性指向新的索引
4. 队列长度减1
5. 返回原来的队首元素
   
   索引的确定：
   因为是队首元素的下一个对象，直接self.head + 1即可,但是，如果是尾部跳到头部，同样的也需要进行取余操作:

$$next\_item\_idx=(self.head+1)\%self.size$$
代码实现如下：

    def pop(self):    # 弹出队首元素
        if self.is_empty():
            raise  ValueError('队列为空')
        res = self.items[self.head]
        self.head = (self.head + 1 ) % self.size
        self._lenth -= 1
        return res
1
2
3
4
5
6
7
'
运行
运行

---

返回队首元素

返回队首元素索引[self.head]在items中对应的值即可

    def peek(self):
        if self.is_empty():
            raise  ValueError('队列为空')
        res = self.items[self.head]
        return res
1
2
3
4
5
'
运行
运行

附件中附完整代码

---

链表实现

注：由于链表的所有操作的时间复杂度均为O(1)，故，没有必要进行循环操作！

附上链表实现队列代码：

'''
@Time    : 2023-08-07 22:21
@Author  : TAGRENLA
@File    : 队列_链表.py
'''

'''用链表实现队列'''

# 定义结点类
class Node():
    def __init__(self,data,next = None):
        self.data = data
        self.next = next

class Queue:
    '''
    链表的第一个元素是队列的头部，链表的最后一个元素是对列的尾部
    '''
    def __init__(self,size):
        self.head = None
        self.rear = None
        self.lenth = 0
        self.size = size

    def is_empty(self):
        return  self.lenth == 0

    def length(self):
        return self.lenth

    def push(self,data):
        '''
        添加一个元素data到队列尾部
        创建一个新的结点
        将新的结点添加到链表的尾部（链表的尾部既队列的尾部）
            将原来的尾结点的next属性指向新的结点
            将队列的rear（原来的尾结点）属性指向新的结点
        队列长度加1
        特殊情况下：
        如果链表为空
        那么就是添加到链表的头部  具体操作如下：
        1.将队列的head属性指向新的结点
        2.将队列的rear属性指向新的结点 （因为在空的队列中台添加一个对象那么这个对象既是队首又是队尾）
        '''
        if self.length() == self.size:
            raise ValueError('队列已经满了')
        node = Node(data)
        if self.is_empty():
            self.head = node
            self.rear = node
        else:
            self.rear.next = node # 将原来的尾结点的next属性指向新的结点
            self.rear = node      # 将队列的rear（原来的尾结点）属性指向新的结点
        self.lenth += 1


    def pop(self):
        '''抛出队首元素也就是链表的第一个结点'''
        '''
        创建一个变量指向头节点(用于后续的返回)
        将链表的head属性指向原来头节点的下一个结点
        '''
        if self.is_empty():
            raise  ValueError('队列为空')
        value = self.head.data
        if self.lenth == 1:
            self.head = None
            self.rear = None
            # print(f'队列的头部结点是{self.rear}')
        else:
            self.head = self.head.next
            self.lenth -= 1
        return value

    def peek(self):
        if self.is_empty():
            raise  ValueError('队列为空')
        return self.head.data

if __name__ == '__main__':
    queue = Queue(3)
    queue.push(1)
    queue.push(2)
    queue.push(3)
    print(queue.pop())
    queue.push(4)
    print(queue.peek())
    print(queue.pop())
    print(queue.pop())
    print(queue.pop())
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
'
运行
运行

附件

循环队列顺序表完整代码

class Queue:
    def __init__(self,size):
        self.items = [None] * size
        self.size = size
        self._lenth = 0
        self.head = 0

    def is_empty(self):
        return  self._lenth == 0

    def length(self):
        return self._lenth

    def push(self,data):
        if self._lenth < self.size:
            idx = (self._lenth + self.head) % self.size
            self.items[idx] = data
            self._lenth += 1
        else:
            print('队列已经满了')

    def pop(self):    # 弹出队首元素
        if self.is_empty():
            raise  ValueError('队列为空')
        res = self.items[self.head]
        self.head = (self.head + 1 ) % self.size
        self._lenth -= 1
        return res

    def peek(self):
        if self.is_empty():
            raise  ValueError('队列为空')
        res = self.items[self.head]
        return res

if __name__ == '__main__':
    queue = Queue(3)
    print(queue.is_empty())
    print(queue.items)
    queue.push(1)
    print(queue.items)
    queue.push(11)
    print(queue.items)
    queue.push(111)
    print(queue.items)
    queue.push(1111)
    print(queue.pop())
    print(queue.pop())
    print(queue.peek())
    print(queue.length())
    print(queue.items)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
'
运行
运行