# 数据结构：队列 链表，顺序表和循环顺序表实现，python版

尾部 添加数据，效率为0(1)

头部 元素的删除和查看，效率也为0(1)

头部 添加数据，效率为0(n)

尾部 元素的删除和查看，效率也为0(1)

尾部 添加数据，效率为0(1)

头部 元素的删除和查看，效率也为0(1)

```  1 #!/usr/bin/env python
2 # -*- coding:utf-8 -*-
3
4 class QueueUnderflow(ValueError):
5     pass
6
7 #链表节点
8 class Node(object):
9     def __init__(self, elem, next_ = None):
10         self.elem = elem
11         self.next = next_
12
13 #链表实现队列,头部删除和查看O(1),尾部加入O(1)
14 class LQueue(object):
15     def __init__(self):
17         self._rear = None
18
19     def is_empty(self):
21
22     #查看队列中最早进入的元素，不删除
23     def peek(self):
24         if self.is_empty():
25             raise QueueUnderflow
27
28     #将元素elem加入队列，入队
29     def enqueue(self, elem):
30         p = Node(elem)
31         if self.is_empty():
33             self._rear = p
34         else:
35             self._rear.next = p
36             self._rear =p
37
38     #删除队列中最早进入的元素并将其返回，出队
39     def dequeue(self):
40         if self.is_empty():
41             raise QueueUnderflow
44         return result
45
46 #顺序表实现队列,头部删除和查看O(1),尾部加入O(n)
47 class Simple_SQueue(object):
48     def __init__(self, init_len = 8):
49         self._len = init_len
50         self._elems = [None] * init_len
51         self._num = 0
52
53     def is_empty(self):
54         return self._num == 0
55
56     def is_full(self):
57         return self._num == self._len
58
59     def peek(self):
60         if self._num == 0:
61             raise QueueUnderflow
62         return self._elems[self._num-1]
63
64     def dequeue(self):
65         if self._num == 0:
66             raise QueueUnderflow
67         result = self._elems[self._num-1]
68         self._num -= 1
69         return result
70
71     def enqueue(self,elem):
72         if self.is_full():
73             self.__extand()
74         for i in range(self._num,0,-1):
75             self._elems[i] = self._elems[i-1]
76         self._elems[0] = elem
77         self._num += 1
78
79     def __extand(self):
80         old_len = self._len
81         self._len *= 2
82         new_elems = [None] * self._len
83         for i in range(old_len):
84             new_elems[i] = self._elems[i]
85         self._elems = new_elems
86
87
88 #循环顺序表实现队列,头部删除和查看O(1),尾部加入O(1)
89 class SQueue(object):
90     def __init__(self, init_num = 8):
91         self._len = init_num
92         self._elems = [None] * init_num
94         self._num  = 0
95
96     def is_empty(self):
97         return self._num == 0
98
99     def peek(self):
100         if self.is_empty():
101             raise QueueUnderflow
103
104     def dequeue(self):
105         if self.is_empty():
106             raise QueueUnderflow
109         self._num -= 1
110         return result
111
112     def enqueue(self, elem):
113         if self._num == self._len:
114             self.__extand()
115         self._elems[(self._head + self._num) % self._len] = elem
116         self._num += 1
117
118     def __extand(self):
119         old_len = self._len
120         self._len *= 2
121         new_elems = [None] * self._len
122         for i in range(old_len):
123             new_elems[i] = self._elems[(self._head + i) % old_len]
124         self._elems, self._head = new_elems, 0
125
126
127
128 if __name__=="__main__":
129     q = SQueue()
130     for i in range(8):
131         q.enqueue(i)
132     #for i in range(8):
133     #    print(q.dequeue())
134     #print(q._num)
135     q.enqueue(8)
136     print(q._len)```