ruk·si

🐍 Python
Queues and Stacks

Updated at 2018-06-09 18:43

Avoid using lists as stacks or queues. Lists can become very slow in some cases.

Dequeue is a thread-safe queue/stack implementation.

from queue import deque

stack = deque()
stack.append('eat')
stack.append('sleep')
stack.append('code')
assert stack.pop() == 'code'
assert stack.pop() == 'sleep'
assert stack.pop() == 'eat'
# stack.pop() # => IndexError
from queue import deque

queue = deque()
queue.append('eat')
queue.append('sleep')
queue.append('code')
assert queue.popleft() == 'eat'
assert queue.popleft() == 'sleep'
assert queue.popleft() == 'code'
# queue.popleft() # => IndexError
from queue import deque

dq = deque()
dq.append('sleep')
dq.append('code')
dq.appendleft('drink')
dq.appendleft('eat')
assert list(dq) == ['eat', 'drink', 'sleep', 'code']
dq.rotate(2)
assert list(dq) == ['sleep', 'code', 'eat', 'drink']
dq.extend(['play'])
assert list(dq) == ['sleep', 'code', 'eat', 'drink', 'play']

Queue module contains a thread-safe queue implementation.

from queue import Queue

stack = Queue()
stack.put('eat')
stack.put('sleep')
stack.put('code')
assert stack.get() == 'eat'
assert stack.get() == 'sleep'
assert stack.get() == 'code'
# stack.get_nowait() # => queue.Empty
# stack.get() # => blocks forever

Last-in-first-out queue is a thread-safe stack implementation.

from queue import LifoQueue

stack = LifoQueue()
stack.put('eat')
stack.put('sleep')
stack.put('code')
assert stack.get() == 'code'
assert stack.get() == 'sleep'
assert stack.get() == 'eat'
# stack.get_nowait() # => queue.Empty
# stack.get() # => blocks forever

Priority queue is a thread-safe queue with internal item sorting.

from queue import PriorityQueue

queue = PriorityQueue()
queue.put((2, 'code'))
queue.put((1, 'eat'))
queue.put((3, 'sleep'))
assert queue.get() == (1, 'eat')
assert queue.get() == (2, 'code')
queue.put((1, 'drink'))
assert queue.get() == (1, 'drink')
assert queue.get() == (3, 'sleep')
# queue.get() # => blocks forever

Source

  • Python Tricks The Book, Dan Bader
  • Fluent Python, Luciano Ramalho