首页 > 代码库 > 数组队列 与 链表队列
数组队列 与 链表队列
做了些实验，感觉 用链表实现队列 比 用数组实现队列 性能好
进出队的每秒操作数比较
数组队列
enqueue | 37,037 |
dequeue | 4,166,666 |
链表队列
enqueue | 277,778 |
dequeue | 666,667 |
先入队n次，再出队n次的运行时间比较，单位是秒
出入队次数 | 数组队列运行时间 | 链表队列运行时间
1,000 | 0.01 | 0.01 |
10,000 | 0.04 | 0.04 |
100,000 | 2.7 | 0.4 |
1,000,000 |
| 4 |
最后一组，数组队列的半天没运行出来
下面是代码
class ArrayQueue:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def enqueue(self, item):
self.items.insert(0,item)
def dequeue(self):
return self.items.pop()
def size(self):
return len(self.items)
class Node:
def __init__(self,initdata):
self.data = initdata
self.next = None
self.prev = None
class LinkedListQueue:
def __init__(self):
self.head = None
self.rear = None
self.size = 0
def isEmpty(self):
return self.size == 0
def size(self):
return self.size
def enqueue(self,item):
self.size += 1
pre = self.head
self.head = Node(item)
self.head.next = pre
if pre != None: pre.prev = self.head
else: self.rear = self.head
def dequeue(self):
if self.size == 0: return None
self.size -= 1
rmdata = self.rear.data
if self.rear.prev != None:
self.rear = self.rear.prev
return rmdata
数组队列 与 链表队列