# Data Structures¶

## Counter: TODO¶

``````collections.counter
``````
``````class Solution:
def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
m = collections.defaultdict(int)
lists = [A, B, C, D]

def nSumCount() -> int:
return countComplements(len(lists) // 2, 0)

def addToHash(i: int, total: int) -> None:
if i == len(lists) // 2:
m[total] += 1
else:
for a in lists[i]:
addToHash(i + 1, total + a)

def countComplements(i: int, complement: int) -> int:
if i == len(lists):
return m[complement]
cnt = 0
for a in lists[i]:
cnt += countComplements(i + 1, complement - a)
return cnt

return nSumCount()
``````

## Stacks¶

• list
• amortized O(1) for inserts and deletes

### `collections.deque`¶

• double-ended queue

Adding: stack is the same as queue

``````>>> from collections import deque
>>> s = deque()
>>> s.append('eat')
``````
``````>>> s.pop()
'eat'
>>> s.pop()
IndexError: "pop from an empty deque"
``````

### `queue.LifoQueue`¶

• multi-producers & multi-consumers from different threads
• same process
``````>>> from queue import LifoQueue
>>> s = LifoQueue()
>>> s.put('eat')
>>> s.get()
'eat'
>>> s.get_nowait()
queue.Empty
>>> s.get()
# Blocks / waits forever...
``````

## Queues¶

### `collections.deque`¶

Adding: stack is the same as queue

``````>>> from collections import deque
>>> q = deque()
>>> q.append('eat')
``````
``````>>> q.popleft()
'eat'
>>> q.popleft()
IndexError: "pop from an empty deque"
``````

### `queue.Queue`¶

• multi-producers & multi-consumers from different threads
• same process
``````>>> from queue import Queue
>>> q = Queue()
>>> q.put('eat')
``````
``````>>> q.get()
'eat'
>>> q.get_nowait()
queue.Empty
>>> q.get()
# Blocks / waits forever...
``````

### `multiprocessing.Queue`¶

• similar to `queue.Queue`
• also handles different processes vs threads

## Priority Queue¶

### `heapq`¶

• binary heap
``````from heapq import heapq

pq = []

heappush(pq.(2, 'code'))
``````

### `queue.PriorityQueue`¶

• wrapper around `heapq`
• supports concurrency (locks, threads, ...)
• API is class based
``````from queue import PriorityQueue

q = PriorityQueue()
q.put((2, 'code'))
q.put((1, 'eat'))
q.put((3, 'sleep'))
``````

Last update: 2023-02-03