Skip to content

[Python] 雙端佇列： deque

雙端佇列（Doubly Ended Queue, Deque）是一種經典的資料結構，跟 Python 中的 List 元件不同，deque 能夠同時操作佇列的兩端。除此之外，List 在需要於開頭插入元件時只能使用 O(n) 的 insert()；而 deque 卻能使用 O(1) 的 appedleft()。

而在 Python 中可以直接使用 collections 模組中的 deque。其最重要的 4 個函式如下：

  • append(): 新增元素於佇列右側
  • appendleft(): 新增元素於佇列左側
  • pop(): 刪除最右側元素
  • popleft(): 刪除最左側元素

使用方法則如下述。

deque 使用方法

直接使用範例程式碼看看不同函式的效果。

# coding: utf-8
from collections import deque


def main():
    q = deque([5, 6, 7])

    # append()
    q.append(8)
    print('After append(8):', q)

    # pop()
    q.pop()
    print('After pop():', q)

    # appendleft()
    q.appendleft(4)
    print('After appendleft(4):', q)

    # popleft()
    q.popleft()
    print('After popleft():', q)


if __name__ == '__main__':
    main()


Output:

After append(8): deque([5, 6, 7, 8])
After pop(): deque([5, 6, 7])
After appendleft(4): deque([4, 5, 6, 7])
After popleft(): deque([5, 6, 7])


deque 在 Python 中的使用方法基本如此。

References

Read More

Tags:

Leave a Reply