# by default, only the result of the last expression in a cell is displayed after evaluation.
# the following forces display of *all* self-standing expressions in a cell.
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"
While the list data structure is incredibly useful, both implementations we explored (array-backed and linked) have operations that run in $O(N)$ time, which make them non-ideal for use with large, growing collections of data.
By further restricting the list API, however — in particular, by isolating points of access to either the front or end of the data set — we can create data structures whose operations are all $O(1)$, and remain very useful in their own right.
Stacks are linear data structures which only permit access to one "end" of the data collection. We can only append ("push") items onto the tail end (a.k.a. the "top") of a stack, and only the most recently added item can be removed ("popped"). The last item to be pushed onto a stack is therefore the first one to be popped off, which is why we refer to stacks as last-in, first out (LIFO) structures.
# array-backed implementation
class Stack:
def __init__(self):
self.data = [] # python list, we can use python list "append" O(1) amortized
# python list "pop" to get/remove last item in O(1)
def push(self, val):
self.data.append(val)
def empty(self):
return len(self.data)==0
def pop(self): # removing and returning the top of the stack
assert(not self.empty())
return self.data.pop() #self.data.pop(-1) self.data.pop(len(self.data)-1)
def peek(self): # return the value on top of stack
assert(not self.empty())
return self.data[-1]
def __bool__(self):
return not self.empty()
s = Stack()
for x in range(10):
s.push(x)
while s:
print(s.pop())
9 8 7 6 5 4 3 2 1 0
# linked implementation
class Stack:
class Node:
def __init__(self, val, next=None):
self.val = val
self.next = next
def __init__(self): # front of linked list is the top of stack, push and pop are both
# working at first node, O(1)
self.top = None
def push(self, val): # put a new node at front of linked list
self.top=Stack.Node(val, self.top) # no special case needed for first node pushed
def empty(self):
return self.top == None
def pop(self):
assert(not self.empty())
x = self.top.val
self.top= self.top.next
return x
def peek(self):
assert(not self.empty())
return self.top.val
def __bool__(self):
return not self.empty()
s = Stack()
for x in range(10):
s.push(x)
while s:
print(s.pop())
9 8 7 6 5 4 3 2 1 0
e.g., '(1 + 2 * (3 - (4 / 2) + 5) - (6 + 1))'
def check_parens(expr): #boolean return True if expr is OK, False if not OK
s = Stack()
for c in expr:
if c == "(":
s.push(c)
elif c == ")":
try:
garbage=s.pop() # if the stack is empty, this pop will fail, which means the expr is not valid
except:
return False
#any other character c is ignored
# if done with iterating the expr, and stack is not empty, the expr is bad
return s.empty()
check_parens('()')
True
check_parens('((()))')
True
check_parens('()(()()(()))')
True
check_parens('(')
False
check_parens('())')
False
check_parens('(1 + 2 * (3 - (4 / 2) + 5) - (6 + 1))')
True
e.g., '(1 + 2) * 5' $\rightarrow$ '1 2 + 5 *'
def eval_postfix(expr): #assuming expr is valid
s = Stack()
toks = expr.split()
for t in toks:
if t == '+':
x = s.pop()
y = s.pop()
s.push(x+y)
elif t=='-':
x = s.pop()
y = s.pop()
s.push(y-x)
elif t=='*':
x = s.pop()
y = s.pop()
s.push(y*x)
elif t=='/':
x = s.pop()
y = s.pop()
s.push(y/x)
else:
s.push(int(t)) #must be a digit
return s.pop()
eval_postfix('1 2 + 5 *')
15
eval_postfix('1 2 5 * +')
11
# ((1 + 2) * (3 + 2)) * 10
eval_postfix('1 2 + 3 2 + * 10 *')
150
maze_str = """######
I #
# ## #
# ####
# O
######"""
def parse_maze(maze_str):
grid = []
for line in maze_str.split('\n'):
grid.append(['# IO'.index(c) for c in line.strip()])
return grid
def print_maze(grid):
for r in grid:
print(''.join('# IO!+'[c] for c in r))
parse_maze(maze_str)
[[0, 0, 0, 0, 0, 0], [2, 1, 1, 1, 1, 0], [0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 0, 0], [0, 1, 1, 1, 1, 3], [0, 0, 0, 0, 0, 0]]
print_maze(parse_maze(maze_str))
###### I # # ## # # #### # O ######
maze = parse_maze(maze_str)
# 0=wall # 1 is an unexplored hall 2=in I 3=out O 5=visited + 4=possible move to !
maze[1][0] = 5
maze[1][1] = 4
print_maze(maze)
###### +! # # ## # # #### # O ######
class Move:
def __init__(self, frm, to): #frm is tuple (row1,col1) to tuple (row2, col2)
self.frm = frm
self.to = to
def __repr__(self):
return '({},{}) -> ({},{})'.format(self.frm[0], self.frm[1],
self.to[0], self.to[1])
def moves(maze, place): #maze is 2D array of numbers for a maze
# place is a tuple representing a current location (row, col)
# generating a list of move objects
moves = [Move(place, (place[0]+d[0], place[1]+d[1]))
#previousrow, samecol (-1, 0)
#nextrow, samecol (1, 0)
#samerow, previouscol (0, -1)
#samerow, nextcol (0, 1)
# for d in ((-1, 0), (1, 0), (0, -1), (0, 1)) #above below left right
for d in ((0, -1), (0, 1), (-1, 0), (1, 0) ) # left right above below
if place[0]+d[0] in range(len(maze)) and #len(maze) is how many rows
place[1]+d[1] in range(len(maze[0])) and #len(maze[0]) is how many cols
maze[place[0]+d[0]][place[1]+d[1]] in (1, 2, 3)]
return moves #list of move objects
maze = parse_maze(maze_str)
moves(maze, (1, 0))
[(1,0) -> (1,1)]
moves(maze, (1, 1))
[(1,1) -> (2,1), (1,1) -> (1,0), (1,1) -> (1,2)]
maze[1][0] = 5
moves(maze, (1, 1))
[(1,1) -> (2,1), (1,1) -> (1,2)]
from time import sleep
from IPython.display import clear_output
def visit(maze, loc):
"""Annotates a loc in the maze as visited"""
maze[loc[0]][loc[1]] = 5
def mark(maze, loc):
"""Annotates a loc in the maze as being of interest"""
if maze[loc[0]][loc[1]] != 3:
maze[loc[0]][loc[1]] = 4
def display(maze):
clear_output(True)
print_maze(maze)
# sleep(0.5)
sleep(1.0)
def solve_maze(maze, entry): #entry is a (row,col)
for m in moves(maze, entry): #moves returns a list of moves
save_move(m)
visit(maze, entry)
while not out_of_moves():
move = next_move()
if maze[move.to[0]][move.to[1]] == 3:
return True
display(maze)
visit(maze, move.to)
for m in moves(maze, move.to):
mark(maze, m.to)
save_move(m)
return False
move_stack = Stack()
def save_move(move):
move_stack.push(move)
def next_move():
return move_stack.pop()
def out_of_moves():
return move_stack.empty()
solve_maze(parse_maze(maze_str), (1, 0))
###### ++! # #+## # #+#### #+++!O ######
True
maze_str = """#################
I # # #
# ##### # # # # #
# # # # # # #
# ### ### # # ###
# # # O
#################"""
solve_maze(parse_maze(maze_str), (1, 0))
################# ++#+++++++#+++! # #+#####+#+#+#+# # #+++++#+#+#+#+# # #+###+###+#+#+### #+++#+++++++#++!O #################
True
maze_str = """#################
I #
# # # # # # # # #
# # # # # # # # #
# ###############
# O
#################"""
solve_maze(parse_maze(maze_str), (1, 0))
################# ++! # #+# # # # # # # # #+# # # # # # # # #+############### #++++++++++++++!O #################
True
Queues are linear data structures wherein we are only permitted to append ("enqueue") items onto the rear, and remove ("dequeue") items from the front. The oldest item still in a queue is therefore the next one to be dequeued, which is why we refer to a queue as a first-in, first-out (FIFO) structure. It is helpful to think of a queue as being the model for a line at a typical supermarket checkout aisle (first customer in, first customer to be checked out).
# array-backed implementation NOT GOOD, either enqueue or dequeue will be O(n)
class Queue:
def __init__(self):
self.data = []
def enqueue(self, val):
pass
def empty(self):
pass
def dequeue(self):
assert(not self.empty())
pass
def __bool__(self):
return not self.empty()
q = Queue()
for x in range(10):
q.enqueue(x)
while q:
print(q.dequeue())
# linked implementation
class Queue:
class Node:
def __init__(self, val, next=None):
self.val = val
self.next = next
def __init__(self):
self.head = self.tail = None
def enqueue(self, val):
#special case for empty Q
if self.empty():
self.head=Queue.Node(val, None)
self.tail=self.head
else:
self.tail.next=Queue.Node(val, None)
self.tail=self.tail.next
def dequeue(self):
assert(not self.empty()) #head must be pointing to a node
val = self.head.val
self.head=self.head.next #self.head.next is the 2nd node, OR None
if not self.head: #i must have deleted the last node
self.tail=None
return val
def empty(self):
return self.head == None
def __bool__(self):
return not self.empty()
q = Queue()
for x in range(10):
q.enqueue(x)
while q:
print(q.dequeue())
0 1 2 3 4 5 6 7 8 9
move_queue = Queue()
def save_move(move):
move_queue.enqueue(move)
def next_move():
return move_queue.dequeue()
def out_of_moves():
return move_queue.empty()
maze_str = """######
I #
# ## #
# ####
# O
######"""
solve_maze(parse_maze(maze_str), (1, 0))
###### +++++# #+##+# #+#### #+++!O ######
True
maze_str = """#################
I # # #
# ##### # # # # #
# # # # # # #
# ### ### # # ###
# # # O
#################"""
solve_maze(parse_maze(maze_str), (1, 0))
################# ++#+++++++#+++++# #+#####+#+#+#+#+# #+++++#+#+#+#+#+# #+###+###+#+#+### #+++#+++++++#++!O #################
True
maze_str = """#################
I #
# # # # # # # # #
# # # # # # # # #
# ###############
# O
#################"""
solve_maze(parse_maze(maze_str), (1, 0))
################# ++++++++++++++++# #+#+#+#+#+#+#+#+# #+#+#+#+#+#+#+#+# #+############### #++++++++++++++!O #################
True
# Show how many threads are already running in the notebook
import threading
threading.active_count()
5
from threading import Thread, Lock
from time import sleep
import random
lock = Lock()
def worker_fn(workerId, q):
while True:
try:
with lock: # only one worker can access the queue at a time
work = q.dequeue() # get some work
except: # queue is empty
sleep(1)
continue
if work == 'Stop':
print(' Worker: ', workerId, 'stopping.')
break
else: # work on it some random amount of time, when finished, check the queue again
print(' Worker:', workerId, 'processing:', work)
sleep(10*random.random())
work_queue = Queue()
for i in range(5):
Thread(target=worker_fn, args=(i, work_queue)).start()
# Should be 5 more threads running
import threading
threading.active_count()
15
# KEEP RERUNNING THIS CELL
for i in range(10):
with lock:
work_queue.enqueue(i)
Worker: 3 processing: 0 Worker: 0 processing: 1 Worker: 4 processing: 2 Worker: 2 processing: 3 Worker: 1 processing: 4 Worker: 4 processing: 5 Worker: 3 processing: 6 Worker: 2 processing: 7 Worker: 1 processing: 8 Worker: 4 processing: 9
# stop the simulation
for i in range(5):
with lock:
work_queue.enqueue('Stop')
Worker: 0 stopping. Worker: 1 stopping. Worker: 4 stopping. Worker: 3 stopping. Worker: 2 stopping.
from random import randint
from time import sleep
task_queue = Queue()
for i in range(3):
task_queue.enqueue(('Job {}'.format(i), randint(3, 6)))
n = task_queue.head
while n:
print(n.val)
n = n.next
('Job 0', 4)
('Job 1', 3)
('Job 2', 6)
while not task_queue.empty():
job, time_left = task_queue.dequeue()
print('Running', job)
sleep(1)
time_left -= 1
if time_left > 0:
print('Re-queueuing', job, 'with remaining time =', time_left)
task_queue.enqueue((job, time_left))
else:
print('*', job, 'done')
Running Job 0 Re-queueuing Job 0 with remaining time = 3 Running Job 1 Re-queueuing Job 1 with remaining time = 2 Running Job 2 Re-queueuing Job 2 with remaining time = 5 Running Job 0 Re-queueuing Job 0 with remaining time = 2 Running Job 1 Re-queueuing Job 1 with remaining time = 1 Running Job 2 Re-queueuing Job 2 with remaining time = 4 Running Job 0 Re-queueuing Job 0 with remaining time = 1 Running Job 1 * Job 1 done Running Job 2 Re-queueuing Job 2 with remaining time = 3 Running Job 0 * Job 0 done Running Job 2 Re-queueuing Job 2 with remaining time = 2 Running Job 2 Re-queueuing Job 2 with remaining time = 1 Running Job 2 * Job 2 done
Stack & Queue implementations: