Contents

## 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.

 1  q = deque(maxlen=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?

 1  q.popleft() 
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]