Stacks, Queues, Heaps, and Hash Tables in Python

Many interview problems that rely on stacks, queues, and hash tables, could be made easier by importing some python libraries that I rarely use. Most of these are in sections 8.3: collections, and 8.4 : heapq, in the Python documentation.

Stacks (docs)¶

First, just for reference, here is the way to implement a python stack using a list:

1
2
3

stack = [1,2,3] # a list named "stack"
stack.append(4) # just use regular list append to add something to the stack
stack.pop() # removes the last element of our list named stack

Pretty simple. Just remember that, while pop() is a list method in python, push() isn’t.

Priority Queue or Heap (docs)¶

There isn’t a purpose-built heap class in python. Like stacks, python heaps are implemented using a list. However, the methods for pushing, and popping and reheapifying aren’t standard list methods, so they have to be imported.

import heapq
heap = [21,1,45,78,3,5] # a python list named "heap"
heapq.heapify(heap) # run heapify on our list named heap
heapq.heappop(heap) # heappop pops one element off and reheapifies the list
heapq.heappush(heap,8) # heappush appends 8 and reheapifies the list

Queues (docs)¶

The queue must have it’s own class, because removing items from the front of a python list takes O(n) time. Each and every list element has to be moved once to the left, should the first list element be removed. I’m not certain as to why this is, since I had always thought that the underlying implementation of a python list was a linked list with indexed, random access pointers to each list element. At any rate, the deque class, which implements the queue data structure in python, has enqueue and dequeue operations that are both O(1).

import collections.deque
queue = deque(["Mon","Tue","Wed"]) # create deque named "queue" from list

# enter on right, leave on left
queue.append("Thu") # Append to the right
queue.popleft() # Remove from the left (removes Mon)

# enter on left, leave on right
queue.appendleft("Sun") # append to the left
queue.pop() # Remove from the right

The deque class implements a two sided queue. You enter from the left or the right. Consequentially, you can also implement a stack from the deque class.

Dictionary or Hashtable¶

The Dictionary¶

Suppose you have a string s. You can keep a tally of the number of letters of each kind in the word with a Python dictionary.

s = "letters"
d = {}
for char in s:
    if char in d: #check if the character exists in the dictionary
        d[char]+=1 #if it does, increment
    else: 
        d[char] = 1 #if not, initialize to 1

Counter Objects (docs)¶

Counters are a subclass of dictionaries, designed to keep tallies. You can pass any iterable and each element in the iterable (letters in a string, elements in a list, items in a dictionary.) Basically a Counter is a dictionary, but

# normal dictionary
d = {} 
d['a'] # returns KeyError: 'a'

# counter dictionary 
from collections import Counter
c = Counter()
c['a'] # initializes a dictionary element with default value of {'a': 0} AND returns 0

Here is how you would take a tally using Counter.

1
2
3

# Tally occurrences of words in a list
cnt = Counter(['red', 'blue', 'red', 'green', 'blue', 'blue'])
cnt.most_common() # returns list of tuples with count [('blue', 3), ('red', 2), ('green', 1)]

Default Dictionary (docs)¶

Like the Counter objects, defaultdict objects do not return key errors. Default dictionaries allow you to pass a lambda function as an argument that will be run whenever a value can’t be found for a given key.

1 2	`dd = defaultdict(lambda: None, {}) # this default dict creates key:None in dictionary whenever key doesn't already exist dd['a'] # returns None instead of KeyError`