用Python实现队列---循环队列

分析

代码

class Queue:
    def __init__(self,size):
        # 以列表的最后一个元素作为队尾
        self.items = [None]*size  #长度占位 声明长度为size的数据区
        self.size =size  #队列的最大长度
        self.head = 0 #队头的索引
        self._length = 0 #记录队列的长度


    def is_empty(self):
        return self._length ==0 # items中实际是有元素的，没有真正pop,只是进行了封装

    def length(self):
        return self._length

    def push(self, item):
        if self.length() == self.size:
            raise ValueError("队列已满")
        else:
            idx = (self.head + self.length()) % self.size #要加入元素的索引
            self.items[idx] = item #赋值
            self._length += 1

    def pop(self):
        # 抛出队首元素
        if self.is_empty():
            raise ValueError("队列为空")
        else:
            value = self.items[self.head]
            self.head = (self.head +1) % self.size #出队之后的队头索引
            self._length -= 1
            return value#时间复杂度为O(1)

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


if __name__ == "__main__":
    queue = Queue(3)
    queue.push(1)  # 进入队列
    queue.push(2)
    queue.push(3)
    print(queue.pop())#注释测试
    queue.push(4)
    print(queue.length())  # 队列长度
    print(queue.peek())  # 队头元素
    print(queue.pop())  # 出队
    print(queue.pop())
    print(queue.pop())
    print(queue.items)#应该为空  但其实是有元素的 对使用者而言队列为空  封装
    # 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

结果