Stacks and Queues

Agenda

1. Stacks
   • ... for delimiter pairing
   • ... for postfix expression evaluation
   • ... for tracking execution and backtracking
2. Queues
   • ... for tracking execution and backtracking
   • ... for apportioning work
   • ... for fair scheduling (aka "round-robin" scheduling)
3. Run-time analysis
4. Closing remarks

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

Overview

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.

1. Stacks

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 = []   # end of the array (python list) is the top of the stack
        #assume append is O(1)   and del self.data[len(self.data)-1]  is O(1)
        #  no movelment of elements needed
        
    def push(self, val):
        self.data.append(val)

    def empty(self):
        return len(self.data)==0

    def pop(self):
        assert(not self.empty())
        return self.data.pop()
    
    def peek(self):
        assert(not self.empty())
        return self.data[len(self.data)-1]
    
    def __bool__(self):
        return not self.empty()

s = Stack()
for x in range(10):
    s.push(x)

s.data

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

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):
        self.top = None

    def push(self, val):
        self.top = Stack.Node(val,self.top)
        
    def empty(self):
        return self.top==None
    
    def pop(self):
        assert(not self.empty())
        val=self.top.val
        self.top=self.top.next
        return val
    
    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

... for delimiter pairing

e.g., '(1 + 2 * (3 - (4 / 2) + 5) - (6 + 1))'

def check_parens(expr):    # return false if not valid pairing
    s = Stack()
    for c in expr:
        if c == '(':
            s.push(c)
        elif c == ')':    
            try:
                s.pop()   # what if pop fails on empty stack
            except:
                return False
            
    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

... for postfix expression (aka "reverse polish notation") evaluation

e.g., '(1 + 2) * 5' $\rightarrow$ '1 2 + 5 *'

def eval_postfix(expr):   #  assume the expr is valid post fix
    s = Stack()
    toks = expr.split()  # toks=['1' ,'2', '+', '5', '*']
    for t in toks:
        # operands get pushed on stack (AS INTEGERS)
        # operators pop 2 things off stack (operands) and does the math
        # pushes the result back on stack
        if t == '+':
            s.push (s.pop()+s.pop())
        elif t=='*':
            s.push (s.pop()*s.pop())
        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))
    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

... for tracking execution and backtracking

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()])
        #             0123
    return grid

def print_maze(grid):
    for r in grid:
        print(''.join('# IO!+'[c] for c in r))

parse_maze(maze_str)
#maze_str = """######   
#              I    #   
#              # ## #   
#              # ####   
#              #    O   
#              ######"""

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

#  0 is wall    1 is hallway   2 is IN   3 is OUT
maze = parse_maze(maze_str)
#  5 is visited spot,     4 is a place of interest (possible next)
maze[1][0] = 5     #  shows as a +
maze[1][1] = 4    #  shows as a !
print_maze(maze)

######
+!   #
# ## #
# ####
#    O
######

class Move:
    def __init__(self, frm, to):
        self.frm = frm   # 2 element tuple  (row, col)
        self.to  = to   # 2 element tuple  (row, col)
        
    def __repr__(self):
        return '({},{}) -> ({},{})'.format(self.frm[0], self.frm[1],
                                           self.to[0],  self.to[1])

def moves(maze, place):   # place is  2 element tuple  (row, col)
    moves = [Move(place, (place[0]+d[0], place[1]+d[1]))
            for d in ((-1, 0), (1, 0), (0, -1), (0, 1))
             #           up      down     left    right
             #       prev row  next row  prev col   next col
            if place[0]+d[0] in range(len(maze)) and 
               place[1]+d[1] in range(len(maze[0])) and
               maze[place[0]+d[0]][place[1]+d[1]] in (1, 2, 3)]
    return moves

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(3)

def solve_maze(maze, entry):
    count=0
    move_list=[]
    for m in moves(maze, entry):
        save_move(m)  #  DO SOMETHING WITH STACK
    visit(maze, entry)
    while not out_of_moves():   #  DO SOMETHING WITH STACK
        move = next_move()    #  DO SOMETHING WITH STACK
        if maze[move.to[0]][move.to[1]] == 3:
            print(count)
            print(move_list)
            return True
        display(maze)
        visit(maze, move.to)
        count+=1
        move_list.append( move.to)
        for m in moves(maze, move.to):
            mark(maze, m.to)
            save_move(m)  #  DO SOMETHING WITH STACK
    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()

maze_str = """######   
              I    #   
              # ## #   
              # ####   
              #    O   
              ######"""

solve_maze(parse_maze(maze_str), (1, 0))

######
+++++#
#+##+#
#+####
#+++!O
######
11
[(1, 1), (1, 2), (1, 3), (1, 4), (2, 4), (2, 1), (3, 1), (4, 1), (4, 2), (4, 3), (4, 4)]

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))

2. Queues

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

class Queue:
    def __init__(self):
        self.data = []

    def enqueue(self, val):
        pass
        
    def empty(self):
        pass

    def dequeue(self):
        assert(not self.empty())
        val = head.
    
    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):
        if self.tail:
            self.tail.next=Queue.Node(val, None)
            self.tail=self.tail.next
        else:  # if empty queue (tail=None and head=None)
            self.head=Queue.Node(val, None)
            self.tail=self.head
    
    def dequeue(self):
        assert(not self.empty())
        value=self.head.val
        self.head=self.head.next
        if self.head==None:
            self.tail=None
        return value
    
    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

... for tracking execution and backtracking

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
######
11
[(1, 1), (2, 1), (1, 2), (3, 1), (1, 3), (4, 1), (1, 4), (4, 2), (2, 4), (4, 3), (4, 4)]

True

maze_str = """#################
              I #       #     #
              # ##### # # # # #
              #     # # # # # #
              # ### ### # # ###
              #   #       #   O
              #################"""

solve_maze(parse_maze(maze_str), (1, 0))

#################
++#       #     #
#+##### # # # # #
#+++++# # # # # #
#+###+### # # ###
#+++#++++!  #   O
#################

---------------------------------------------------------------------------
KeyboardInterrupt                         Traceback (most recent call last)
<ipython-input-48-dc5bd976e629> in <module>
----> 1 solve_maze(parse_maze(maze_str), (1, 0))

<ipython-input-33-8af816d9bca6> in solve_maze(maze, entry)
     11             print(move_list)
     12             return True
---> 13         display(maze)
     14         visit(maze, move.to)
     15         count+=1

<ipython-input-43-ba134c1d6206> in display(maze)
     14     clear_output(True)
     15     print_maze(maze)
---> 16     sleep(3)

KeyboardInterrupt: 

maze_str = """#################
              I               #
              # # # # # # # # #
              # # # # # # # # #
              # ###############
              #               O
              #################"""

solve_maze(parse_maze(maze_str), (1, 0))

... for doling out work

# 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()

10

# KEEP RERUNNING THIS CELL
for i in range(10):
    with lock:
        work_queue.enqueue(i)

 Worker: 1 processing: 0
 Worker: Worker: 2 processing: 2
 0 processing: 1
 Worker: 3 processing: 3
 Worker: 4 processing: 4
 Worker: 3 processing: 5
 Worker: 0 processing: 6
 Worker: 1 processing: 7
 Worker: 2 processing: 8
 Worker: 3 processing: 9

# stop the simulation
for i in range(5):
    with lock:
        work_queue.enqueue('Stop')

 Worker:  0 stopping.
 Worker:  1 stopping.
 Worker:  2 stopping.
 Worker:  3 stopping.
 Worker:  4 stopping.

... for fair scheduling (aka "round-robin" scheduling)

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', 4)
('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 = 3
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 = 2
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
Re-queueuing Job 1 with remaining time = 1
Running Job 2
Re-queueuing Job 2 with remaining time = 3
Running Job 0
* Job 0 done
Running Job 1
* Job 1 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

3. Run-time analysis

Stack & Queue implementations:

• Insertion (push and enqueue) = $O(1)$
• Deletion (pop and dequeue) = $O(1)$

4. Closing remarks