数据结构：队列 链表，顺序表和循环顺序表实现，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):
 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 QueueUnderflow
102         return self._elems[self._head]
103 
104     def dequeue(self):
105         if self.is_empty():
106             raise QueueUnderflow
107         result = self._elems[self._head]
108         self._head = (self._head + 1) % self._len
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)