-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSQueue.py
More file actions
56 lines (49 loc) · 1.36 KB
/
Copy pathSQueue.py
File metadata and controls
56 lines (49 loc) · 1.36 KB
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
class QueueUnderflow(ValueError):
pass
class Squeue(object):
"""队列"""
# def __init__(self):
# self.__list = []
#
# def enqueue(self,item):
# self.__list.append(item)
# # self.__list.insert(0,item)
#
# def dequeue(self):
# return self.__list.pop(0)
#
# def is_empty(self):
# return self.__list == []
#
# def size(self):
# return len(self.__list)
def __init__(self,init_len=8):
self._len = init_len
self._elems = [0]*init_len
self._head = 0
self._num = 0
def is_empty(self):
return self._num == 0
def peek(self):
if self._num == 0:
raise QueueUnderflow
return self._elems[self._head]
def dequeue(self):
if self._num == 0:
raise QueueUnderflow
e = self._elems[self._head]
self._head = (self._head+1) % self._len
self._num -= 1
return e
def enqueue(self,e):
if self._num == self._len:
self.__extend()
self._elems[(self._head+self._num)%self._len] = e
self._num += 1
def __extend(self):
old_len = self._len
self._len *= 2
new_elems = [0] * self._len
for i in range(old_len):
new_elems[i] = self._elems[(self._head+i)%old_len]
self._elems, self._head = new_elems, 0