链表实现队列：
尾部 添加数据，效率为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): 16 self._head = None 17 self._rear = None 18 19 def is_empty(self): 20 return self._head is None 21 22 #查看队列中最早进入的元素，不删除 23 def peek(self): 24 if self.is_empty(): 25 raise QueueUnderflow 26 return self._head.elem 27 28 #将元素elem加入队列，入队 29 def enqueue(self, elem): 30 p = Node(elem) 31 if self.is_empty(): 32 self._head = p 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 42 result = self._head.elem 43 self._head = self._head.next 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 93 self._head = 0 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 QueueUnderflow102 return self._elems[self._head]103 104 def dequeue(self):105 if self.is_empty():106 raise QueueUnderflow107 result = self._elems[self._head]108 self._head = (self._head + 1) % self._len109 self._num -= 1110 return result111 112 def enqueue(self, elem):113 if self._num == self._len:114 self.__extand()115 self._elems[(self._head + self._num) % self._len] = elem116 self._num += 1117 118 def __extand(self):119 old_len = self._len120 self._len *= 2121 new_elems = [None] * self._len122 for i in range(old_len):123 new_elems[i] = self._elems[(self._head + i) % old_len]124 self._elems, self._head = new_elems, 0125 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)