DataStructure/queue_resize.py at master · TheBestTvarynka/DataStructure · GitHub

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
class queue:
    def __init__(self):
        self.size = 5
        self.array = [None] * self.size
        self.top = 0
        self.button = 0

    def print(self):
        if self.top < self.button:
            f = self.size - self.button
            s = self.top
        else:
            s = 0
            f = self.top - self.button
        print('=-=-=-=-=-=-=-=-=-=-=-=')
        print(self.button, self.top, self.size)
        for i in range(f):
            print(self.array[i + self.button], end=' ')
        for j in range(s):
            print(self.array[j], end=' ')
        print('\n=-=-=-=-=-=-=-=-=-=-=-=')

    def show(self):
        for i in range(self.size):
            print(self.array[i], end=' ')
        print('')

    def resize(self, new_size):
        print('resize', new_size)
        new_array = [None] * new_size
        if self.top <= self.button:
            f = self.size - self.button
            s = self.top
        else:
            s = 0
            f = self.top - self.button
        for i in range(f):
            new_array[i] = self.array[i + self.button]
        for j in range(s):
            new_array[j + f] = self.array[j]
        self.size = new_size
        self.button = 0
        self.top = f + s
        self.array = new_array

    def push(self, item):
        self.array[self.top] = item
        self.top += 1
        if self.is_full():
            self.resize(self.size * 2)

    def pop(self):
        s = self.size
        if self.is_empty():
            print('Error: Queue is empty')
            return 0
        result = self.array[self.button]
        self.button += 1
        if self.top < self.button:
            if self.button == self.size:
                self.button = 0
            s = self.top + self.size - self.button
        if self.top > self.button:
            s = self.top - self.button
        if s <= self.size // 4:
            self.resize(self.size // 2)
        return result


    def is_full(self):
        # queue is full in two case: 1) when top == size (button < top) or 2) button == top (top < button)
        if self.top > self.button and self.top == self.size:
            if self.button > 0:
                self.top = 0
                return False
            return True
        if self.top == self.button:
            return True

    def is_empty(self):
        if self.button == self.top:
            return True


A = queue()
A.push(6)
A.push(7)
A.push(8)
A.push(9)
A.push(0)
A.push(10)
A.push(11)
A.push(12)
A.print()
print(A.pop())
print(A.pop())
print(A.pop())
print(A.pop())
print(A.pop())
A.print()
A.push(21)
A.push(22)
A.push(23)
A.push(24)
A.push(25)
A.print()
# A.show()
print(A.pop())
A.print()
print(A.pop())
print(A.pop())
print(A.pop())
print(A.pop())
A.print()