使用 Python 學習資料結構（四）：隊列

Data Structures
, ,

前言

本文為〈資料結構與演算法〉一文的學習筆記。

隊列

隊列是 FIFO (First In, First Out) 的資料結構。

1
2
3
4
5
6
7
8
9
10
11
12
>>> queue = []
>>> queue.append(1)
    queue.append(2)
    queue
[1, 2]
>>> queue.pop(0)
    1
    queue
[2]
>>> size = len(queue)
    size
1

優先隊列

優先隊列中的每個項目都有各自的優先級，優先級最高的項目最先得到服務。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
>>> import heapq
    class PriorityQueue(object):
        def __init__(self):
            # 使用串列存放隊列
            self._queue = []
            # 紀錄索引
            self._index = 0

        def push(self, item, priority):
            # 隊列由元組構成
            heapq.heappush(self._queue, (-priority, self._index, item))
            self._index += 1

        def pop(self):
            # 返回最高優先級項目
            return heapq.heappop(self._queue)

    class Item(object):
        def __init__(self, name):
            self.name = name

        def __repr__(self):
            return 'Item: {!r}'.format(self.name)
  • heapq 的 heappop() 函式會返回最小値項，因此把 priority 的値變為負値。
  • format() 函式指定的 !r 格式會對應 repr() 函数，能將物件轉換為字串形式。

實例化一個優先隊列類別。

1
>>> q = PriorityQueue()

推入幾個項目。

1
2
3
4
5
6
>>> q.push(Item('foo'), 5)
    q.push(Item('bar'), 1)
    q.push(Item('spam'), 3)
    q.push(Item('grok'), 1)
>>> print(q._queue)
[(-5, 0, Item: 'foo'), (-1, 1, Item: 'bar'), (-3, 2, Item: 'spam'), (-1, 3, Item: 'grok')]

彈出所有項目。

1
2
3
4
5
6
>>> for i in range(4):
        print(q.pop())
(-5, 0, Item: 'foo')
(-3, 2, Item: 'spam')
(-1, 1, Item: 'bar')
(-1, 3, Item: 'grok')

雙端隊列

雙端隊列（double-ended queue，簡稱 deque）可以在任何一端添加或移除元素，它是一種具有隊列和堆疊性質的資料結構。

從右邊新增元素。

1
2
3
4
5
6
7
8
>>> import collections
>>> d1 = collections.deque()
    d1.extend('abcdefg')
    print('extend:', d1)
extend: deque(['a', 'b', 'c', 'd', 'e', 'f', 'g'])
>>> d1.append('h')
    print('append:', d1)
append: deque(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'])

從左邊新增元素。

1
2
3
4
5
6
7
>>> d2 = collections.deque()
>>> d2.extendleft(range(6))
    print('extendleft:', d2)
extendleft: deque([5, 4, 3, 2, 1, 0])
>>> d2.appendleft(6)
    print('appendleft:', d2)
appendleft: deque([6, 5, 4, 3, 2, 1, 0])

參考資料