python实现循环队列_实现循环队列python

$$python实现循环队列$$

Front==tail队列为空
(tail+1)%c == front 队列列满，进行扩容
浪费一个空间来区分满队列和空队列

练习三部曲之一

class LoopQueue(object):
    # 1.成员构造
    def __init__(self, capacity=2):
        self.arr = [None] * (capacity + 1)
        self.front = 0
        self.tail = 0
        self.size = 0

    # 2.魔法方法
    def __str__(self):
        return str(self.arr)

    def __len__(self):
        return len(self.arr)

    def __iter__(self):
        return iter(self.arr)
    
    # 3.返回大小
    def get_size(self):
        return self.size

    def get_capaticty(self):
        return self.__len__() - 1
    
    # 4.判满
    def is_full(self):
        return (self.tail + 1) % len(self.arr) == self.front

    # 5.判空
    def is_empty(self):
        return self.size == 0
    # 6.查
    def get_front(self):
        return self.arr[self.front]
    # 7.增
    def enqueue(self, e):
        if self.is_full():
            self.resize(self.get_capaticty() * 2)
        self.arr[self.tail] = e
        self.tail = (self.tail + 1) % len(self.arr)
        self.size += 1
    # 8.删
    def dequeue(self):
        if self.is_empty():
            raise Exception("Cannot dequeue from en empty queue")

        result = self.arr[self.front]
        self.arr[self.front] = None
        self.front = (self.front + 1) % len(self.arr)
        self.size -= 1

        if self.size < self.get_capaticty() // 4 and self.get_capaticty() > 1:
            self.resize(self.get_capaticty() // 2)
        return result
    
    # 9.附加函数
    def resize(self, new_capacity):
        new_arr = [None] * (new_capacity + 1)
        for i in range(self.size):
            new_arr[i] = self.arr[(i + self.front) % len(self.arr)]

        self.arr = new_arr
        self.front = 0
        self.tail = self.size
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
'
运行
运行

练习三部曲之二

class Queue():
    # 1.成员构造
    # 2.返回大小
    # 3.判空
    # 4.增
    # 5.删
class LoopQueue(object):
    # 1.成员构造
    def __init__(self, capacity=2):

    # 2.魔法方法
    def __str__(self):

    def __len__(self):

    def __iter__(self):


    # 3.返回大小
    def get_size(self):


    def get_capaticty(self):


    # 4.判满
    def is_full(self):

    # 5.判空
    def is_empty(self):

    # 6.查
    def get_front(self):

    # 7.增
    def enqueue(self, e):

    # 8.删
    def dequeue(self):

    # 9.附加函数
    def resize(self, new_capacity):
    
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

练习三部曲之三

class LoopQueue(object):
    # 1.成员构造

    # 2.魔法方法

    # 3.返回大小

    # 4.判满

    # 5.判空

    # 6.查

    # 7.增

    # 8.删

    # 9.附加函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19