[python队列]用链表实现队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
# 定义一个头结点，左边指向队列的开头，
# 右边指向队列的末尾，保证我们插入一个元素和取出一个元素都是O(1)的操作
class Head:
    def __init__(self):
        self.left = None
        self.right = None


class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


class Queue:
    def __init__(self):
        # 初始化节点
        self.head = Head()

    def enqueue(self, value):
        # 插入元素，先新建一个结点
        newnode = Node(value)
        p = self.head
        if p.right:
            # 如果head结点的右边不为None
            # 说明队列中已经有元素了

            temp = p.right
            p.right = newnode
            temp.next = newnode
        else:
            # 队列为空，插入第一个元素
            p.right = newnode
            p.left = newnode

    def dequeue(self):
        p = self.head
        if p.left and (p.left == p.right):
            # 这说明队列中已经有元素
            # 但是这是最后一个元素
            temp = p.left
            p.left = p.right = None
            return temp.value
        elif p.left and (p.left != p.right):
            # 说明队列中有元素，而且不止一个
            temp = p.left
            p.left = temp.next
            return temp.value

        else:
            # 队列为空，抛出查询错误
            raise LookupError('queue is empty')

    def is_empty(self):
        if self.head.left:
            return False
        else:
            return True

    def top(self):
        # 查询目前队列中最早入队的元素
        if self.head.left:
            return self.head.left.value
        else:
            raise LookupError('queue is empty')


if __name__ == '__main__':
    queue = Queue()
    print(queue.is_empty())
    queue.enqueue(1)
    queue.enqueue(2)
    queue.enqueue(3)
    queue.enqueue(4)
    queue.enqueue(5)
    print(queue.is_empty())
    print(queue.dequeue())
    print(queue.dequeue())
    
    print(queue.top())

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Queue:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def enqueue(self, item):
        self.items.insert(0, item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)


if __name__ == '__main__':
    q = Queue()
    q.enqueue(1)
    q.enqueue(2)
    q.enqueue(3)
    q.enqueue(4)
    print(q.items)
    q.dequeue()
    q.dequeue()
    print(q.items)