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

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.

In [1]:
# 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"
In [2]:
# array-backed implementation

class Stack:
    def __init__(self):
        self.data = []
        
    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(-1)
    
    def peek(self):
        assert(not self.empty())
        return self.data[len(self.data)-1]
    
    def __bool__(self):
        return not self.empty()
In [3]:
s = Stack()
for x in range(10):
    s.push(x)
In [4]:
while s:
    print(s.pop())
9
8
7
6
5
4
3
2
1
0
In [5]:
# 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())
        value=self.top.val
        self.top=self.top.next
        return value
    
    def peek(self):
        assert(not self.empty())
        value=self.top.val
        return value
        
    def __bool__(self):
        return not self.empty()
In [6]:
s = Stack()
for x in range(10):
    s.push(x)
In [7]:
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))'

In [8]:
def check_parens(expr):
    s = Stack()
    for c in expr:
        if c=='(':
            s.push(c)
        elif c==')':
            try:
                s.pop()
            except:
                return False
    return s.empty()
In [9]:
check_parens('()')
Out[9]:
True
In [10]:
check_parens('((()))')
Out[10]:
True
In [11]:
check_parens('()(()()(()))')
Out[11]:
True
In [12]:
check_parens('(')
Out[12]:
False
In [13]:
check_parens('())')
Out[13]:
False
In [14]:
check_parens('(1 + 2 * (3 - (4 / 2) + 5) - (6 + 1))')
Out[14]:
True

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

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

In [15]:
def eval_postfix(expr):
    s = Stack()
    toks = expr.split()
    for t in toks:
        if t=='+':
            s.push(s.pop()+s.pop())
        elif t=='*':
            s.push(s.pop()*s.pop())
        else:
            s.push(int(t))
    return s.pop()         
In [16]:
eval_postfix('1 2 + 5 *')
Out[16]:
15
In [17]:
eval_postfix('1 2 5 * +')
Out[17]:
11
In [18]:
# ((1 + 2) * (3 + 2)) * 10
eval_postfix('1 2 + 3 2 + * 10 *')
Out[18]:
150

... for tracking execution and backtracking

In [19]:
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))
In [20]:
parse_maze(maze_str)
Out[20]:
[[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]]
In [21]:
print_maze(parse_maze(maze_str))
######
I    #
# ## #
# ####
#    O
######
In [22]:
maze = parse_maze(maze_str)
maze[1][0] = 5
maze[1][1] = 4
print_maze(maze)
######
+!   #
# ## #
# ####
#    O
######
In [23]:
class Move:
    def __init__(self, frm, to):
        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):
    moves = [Move(place, (place[0]+d[0], place[1]+d[1]))
            for d in ((-1, 0), (1, 0), (0, -1), (0, 1))
            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
In [24]:
maze = parse_maze(maze_str)
In [25]:
moves(maze, (1, 0))
Out[25]:
[(1,0) -> (1,1)]
In [26]:
moves(maze, (1, 1))
Out[26]:
[(1,1) -> (2,1), (1,1) -> (1,0), (1,1) -> (1,2)]
In [27]:
maze[1][0] = 5
moves(maze, (1, 1))
Out[27]:
[(1,1) -> (2,1), (1,1) -> (1,2)]
In [28]:
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)
In [29]:
def solve_maze(maze, entry):
    for m in moves(maze, entry):
        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
In [30]:
move_stack = Stack()

def save_move(move):
    move_stack.push(move)

def next_move():
    return move_stack.pop()   #  FIXED THIS REMOVE (MOVE) ARGUMENT

def out_of_moves():
    return move_stack.empty()
In [32]:
solve_maze(parse_maze(maze_str), (1, 0))
######
+++++#
#+##+#
#+####
#+++!O
######
Out[32]:
True
In [33]:
maze_str = """#################
              I #       #     #
              # ##### # # # # #
              #     # # # # # #
              # ### ### # # ###
              #   #       #   O
              #################"""
In [34]:
solve_maze(parse_maze(maze_str), (1, 0))
#################
++#       #+++++#
#+##### # #+#+#+#
#+++++# # #+#+#+#
#!###+###!#+#+###
#   #+++++++#++!O
#################
Out[34]:
True
In [35]:
maze_str = """#################
              I               #
              # # # # # # # # #
              # # # # # # # # #
              # ###############
              #               O
              #################"""
In [36]:
solve_maze(parse_maze(maze_str), (1, 0))
#################
++++++++++++++++#
#+#+#+#+#+#+#+#+#
#+#+#+#+#+#+#+#+#
#+###############
#++++++++++++++!O
#################
Out[36]:
True

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

In [37]:
# array-backed implementation

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

    def enqueue(self, val):
        self.data.append(val)
        
    def empty(self):
        return len(self.data)==0
    

    def dequeue(self):
        assert(not self.empty())
        return self.data.pop(0)
    
    def __bool__(self):
        return not self.empty()
In [38]:
q = Queue()
for x in range(10):
    q.enqueue(x)
In [39]:
while q:
    print(q.dequeue())
0
1
2
3
4
5
6
7
8
9
In [53]:
# 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 not self.tail:
            self.head=Queue.Node(val)
            self.tail=self.head
        else:
            self.tail.next=Queue.Node(val)
            self.tail=self.tail.next
    
    def empty(self):
        return self.tail==None
    

    def dequeue(self):
        assert(not self.empty())
        temp = self.head.val
        self.head=self.head.next
        if self.head==None:
            self.tail=None
        return temp
    
    def __bool__(self):
        return not self.empty()
In [54]:
q = Queue()
for x in range(10):
    q.enqueue(x)
In [55]:
while q:
    print(q.dequeue())
0
1
2
3
4
5
6
7
8
9

... for tracking execution and backtracking

In [59]:
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()
In [60]:
maze_str = """######   
              I    #   
              # ## #   
              # ####   
              #    O   
              ######"""
In [61]:
solve_maze(parse_maze(maze_str), (1, 0))
######
+++++#
#+##+#
#+####
#+++!O
######
Out[61]:
True
In [62]:
maze_str = """#################
              I #       #     #
              # ##### # # # # #
              #     # # # # # #
              # ### ### # # ###
              #   #       #   O
              #################"""
In [63]:
solve_maze(parse_maze(maze_str), (1, 0))
#################
++#+++++++#+++++#
#+#####+#+#+#+#+#
#+++++#+#+#+#+#+#
#+###+###+#+#+###
#+++#+++++++#++!O
#################
Out[63]:
True
In [64]:
maze_str = """#################
              I               #
              # # # # # # # # #
              # # # # # # # # #
              # ###############
              #               O
              #################"""
In [65]:
solve_maze(parse_maze(maze_str), (1, 0))
#################
++++++++++++++++#
#+#+#+#+#+#+#+#+#
#+#+#+#+#+#+#+#+#
#+###############
#++++++++++++++!O
#################
Out[65]:
True

... for doling out work

In [66]:
from threading import Thread, Lock
from time import sleep
import random

lock = Lock()
def worker_fn(cid, q):
    while True:
        try:
            with lock:
                work = q.dequeue()
        except: # queue is empty
            sleep(1)
            continue
        if work == 'Stop':
            print('Consumer', cid, 'stopping.')
            break
        else:
            print('Consumer', cid, 'processing', work)
            sleep(random.random())

work_queue = Queue()
for i in range(5):
    Thread(target=worker_fn, args=(i, work_queue)).start()
In [67]:
import threading
threading.active_count()
Out[67]:
10
In [71]:
for i in range(10):
    with lock:
        work_queue.enqueue(i)
Consumer 4 processing 0
Consumer 2 processing 1
Consumer 0 processing 2
Consumer 2 processing 3
Consumer 1 processing 4
Consumer 2 processing 5
Consumer 3 processing 6
Consumer 4 processing 7
Consumer 2 processing 8
Consumer 0 processing 9
In [72]:
for i in range(5):
    with lock:
        work_queue.enqueue('Stop')
Consumer 3 stopping.
Consumer 4 stopping.
Consumer 1 stopping.
Consumer 0 stopping.
Consumer 2 stopping.

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

In [73]:
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)))
In [74]:
n = task_queue.head
while n:
    print(n.val)
    n = n.next
('Job 0', 4)
('Job 1', 6)
('Job 2', 6)
In [75]:
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 = 5
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 = 4
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 = 3
Running Job 2
Re-queueuing Job 2 with remaining time = 3
Running Job 0
* Job 0 done
Running Job 1
Re-queueuing Job 1 with remaining time = 2
Running Job 2
Re-queueuing Job 2 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 = 1
Running Job 1
* Job 1 done
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