找回密码
 立即注册

扫一扫,访问微社区

QQ登录

只需一步,快速开始

查看: 2746|回复: 0

数组队列 与 链表队列

11

主题

35

帖子

35

积分

贫民

积分
35
zy1 发表于 2014-9-26 11:56:19 | 显示全部楼层 |阅读模式
做了些实验,感觉 用链表实现队列 比 用数组实现队列 性能好

进出队的每秒操作数比较
数组队列
enqueue37,037
dequeue4,166,666
链表队列
enqueue277,778
dequeue666,667


先入队n次,再出队n次的运行时间比较,单位是秒
出入队次数 | 数组队列运行时间 | 链表队列运行时间
1,0000.010.01
10,0000.040.04
100,0002.70.4
1,000,0004
最后一组,数组队列的半天没运行出来

下面是代码
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



回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表