Queues
Using built-in list
Implement a single-ended queue with basic operations enqueue(), dequeue(), and is_empty(), as well as optional argument maxlen.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Queue:
"""
Dequeue takes O(n) time since all elements need to shift.
"""
def __init__(self, maxlen=None):
self.items = []
self.maxlen = maxlen
def enqueue(self, item):
if maxlen and len(self.items) == maxlen:
self.items = self.items[1:]
self.items.append(item)
def dequeue(self):
return self.items.pop(0)
def is_empty(self):
return len(self.items) == 0
|
Using standard library implementation
Import the standard library queue module. What does its name stand for?
1
2
3
4
| # I tend to forget whether it is deque or heapq that is part of the
# collections module. Use 'deck from collections' as an mnemonic.
# Deque stands for 'double-ended-queue'.
from collections import deque
|
Instantiate the que with a max length of 3.
Add 1, and then, in one go, 2, 3, and 4, and, finally, the list [5, 6, 7] to the queue.
1
2
3
| q.append(1)
q.extend([2, 3, 4])
q.append([5, 6, 7])
|
Dequeue the first item. What will it be?
3
Stacks
Using a list
1
2
3
| stack = [1, 2, 3, 4, 5]
stack.pop()
stack
|
[1, 2, 3, 4]
Using deque
1
2
3
4
5
6
7
| from collections import deque
stack = deque([1, 2, 3, 4])
reversed_stack = []
while stack:
reversed_stack.append(stack.pop())
reversed_stack
|
[4, 3, 2, 1]
1
2
3
| stack.append(1)
stack.append([9, 4, 2])
print(stack.popleft(), stack.pop())
|
1 [9, 4, 2]
Sources