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 simulating a simple single-server queue system
   • ... 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 = []    # python list
        #   we need to push at the top and pop off the top?
        # which end of the array is the top?
        # front of list(array) as the top  NO, then to push we would need to move everything
        # end of the List as the top  YES   push and pop at end are easy O(1) amortized 
        # spread the load of infrequent slow appends among the majority fast appends
        
    def push(self, val):
        self.data.append(val)   # O(1)amortized

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

    def pop(self):
        assert(not self.empty())
        return self.data.pop()    # O(1)amortized   assume shrink list when extra unused slots
    
    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:
        # which end of the linked list is the top?
        # front of linkedist as the top     YES
        # end of the linkedList as the top      NO, hard to remove at end without prior pointers (or tail pointer)
    class Node:
        def __init__(self, val, next=None):
            self.val = val
            self.next  = next
    
    def __init__(self):
        self.top = None

    def push(self, val):   #O(1)
        self.top = Stack.Node(val,self.top)
        
    def empty(self):
        return self.top==None
    
    def pop(self):
        assert(not self.empty())
        valToReturn=self.top.val
        self.top  =  self.top.next
        return valToReturn
    
    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):   #expr is a string 
    s = Stack()
    for c in expr:  # c is a char in string
        if c == '(':
            s.push(c)
        elif c == ')':
            if s.empty():
                return False
            else:
                garbage=s.pop()
        # if not a ( or ), just skip it
    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):
    s = Stack()
    toks = expr.split()
    for t in toks:
        # if t is a number, push it
        # if t is a operator, pop two items, apply the operator, push the result
        if t == '+':
            a=s.pop()
            b=s.pop()
            s.push(a+b)
        elif t == '-':
            a=s.pop()
            b=s.pop()
            s.push(b-a)
        elif t == '*':
            a=s.pop()
            b=s.pop()
            s.push(a*b)
        elif t == '/':
            a=s.pop()
            b=s.pop()
            s.push(b/a)
        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()])
    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)
maze[1][0] = 5
maze[1][1] = 4
print_maze(maze)

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

class Move:
    def __init__(self, frm, to):   #frm and to are each tuples of length 2  (row, col)
        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 our 2D array of the maze, place is a 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))  
               #prevRow,sameCol  nextRow,sameCol
            if place[0]+d[0] in range(len(maze)) and    #check the row OK  still in the maze
               place[1]+d[1] in range(len(maze[0])) and   #check the col OK still in the maze
               maze[place[0]+d[0]][place[1]+d[1]] in (1, 2, 3)]  # 1 is openhallway, 2 is door in, 3 is door out
    return moves    #returning a list of possible moves from the "place"

maze = 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]]

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

def solve_maze(maze, entry):
    for m in moves(maze, entry):
        save_move(m)
    visit(maze, entry)
    while not out_of_moves():  # while stack not  empty
        move = next_move()   # move is a tuple (from, to)
        if maze[move.to[0]][move.to[1]] == 3:
            return True   #  i found the out door
        display(maze)
        visit(maze, move.to)
        for m in moves(maze, move.to):
            mark(maze, m.to)   # mark the row,col as a potential future move
            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))

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):   # end of the list is back of the line
        self.data.append(val)   # python list append amortized O(1)
        
    def empty(self):
        return len(self.data)==0

    def dequeue(self):    # front of list is front of the line
        assert(not self.empty()) 
        # move everything over    O(n)  not good
        val = self.data[0]
        for i in range(1, len(self.data)):
            self.data[i-1]=self.data[i]
        # the last item is in the list twice, remove the second one
        del self.data[len(self.data)-1]  # python list is one item shorter  
        
        # or instead of writing the above loop, just self.data.pop(0)
        
        return val
    
    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

# 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):   #O(1)
        # add at the tail of the linked list
        # special case, if self.tail is None (empty queue)
        if not self.tail:
            self.head=self.tail=Queue.Node(val, None)
        else:
            self.tail.next = Queue.Node(val, None)
            self.tail = self.tail.next
    
    def dequeue(self):    #O(1)
        assert(not self.empty())
        val = self.head.val
        self.head=self.head.next
        # special case if just deleted last node
        if not self.head:
            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

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

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

... for simulating a simple single-server queue system

Let’s simulate a simple single-server queue system, such as a bank teller.

• Customers arrive at random times.
• Each customer has a service time.
• The server handles one customer at a time.
• We simulate how the queue behaves over time.

import random
# Event types
ARRIVAL = "arrival"
DEPARTURE = "departure"
# Priority queue for the event list
event_queue = Queue()
# Queue for waiting customers
waiting_queue = Queue()
# Server status
server_busy = False
# Current simulation time
current_time = 0
# Statistics
total_wait_time = 0
num_customers = 0

def simulate(num_events=10):
    global current_time, server_busy, total_wait_time, num_customers

    # Generate arrival events
    time = 0
    for i in range(num_events):
        interarrival_time = random.expovariate(1.0)  # mean 1.0
        time += interarrival_time
        event_queue.enqueue( (time, ARRIVAL, i) )
#        schedule_event(time, ARRIVAL, i)

    while event_queue:
        current_time, event_type, customer_id =  event_queue.dequeue()    
        if event_type == ARRIVAL:
            print(f"Time {current_time:.2f}: Customer {customer_id} arrives.")
            if not server_busy:
                server_busy = True
                service_time = random.expovariate(0.25)  # mean 1/1.5    1/0.5  1/0.25
                departure_time = current_time + service_time
                event_queue.enqueue((departure_time, DEPARTURE, customer_id))
                print(f"  Customer {customer_id} begins service (duration {service_time:.2f}).")
            else:
                waiting_queue.enqueue((customer_id, current_time))
                print(f"  Customer {customer_id} waits in queue.")
        
        elif event_type == DEPARTURE:
            print(f"Time {current_time:.2f}: Customer {customer_id} departs.")
            num_customers += 1
            if waiting_queue:
                next_customer_id, arrival_time = waiting_queue.dequeue()
                wait_time = current_time - arrival_time
                if wait_time<0:
                    wait_time=0
                total_wait_time += wait_time
                service_time = random.expovariate(1.5)
                departure_time = current_time + service_time
                event_queue.enqueue((departure_time, DEPARTURE, customer_id))
                print(f"  Customer {next_customer_id} begins service after waiting {wait_time:.2f}.")
            else:
                server_busy = False

    if num_customers > 0:
        print(f"\nAverage wait time: {total_wait_time / num_customers:.2f} units.")

# Run simulation
simulate(10)

Time 3.10: Customer 0 arrives.
  Customer 0 begins service (duration 16.65).
Time 4.39: Customer 1 arrives.
  Customer 1 waits in queue.
Time 4.90: Customer 2 arrives.
  Customer 2 waits in queue.
Time 5.79: Customer 3 arrives.
  Customer 3 waits in queue.
Time 5.88: Customer 4 arrives.
  Customer 4 waits in queue.
Time 6.96: Customer 5 arrives.
  Customer 5 waits in queue.
Time 7.76: Customer 6 arrives.
  Customer 6 waits in queue.
Time 8.27: Customer 7 arrives.
  Customer 7 waits in queue.
Time 9.27: Customer 8 arrives.
  Customer 8 waits in queue.
Time 10.11: Customer 9 arrives.
  Customer 9 waits in queue.
Time 19.74: Customer 0 departs.
  Customer 1 begins service after waiting 15.35.
Time 20.32: Customer 0 departs.
  Customer 2 begins service after waiting 15.42.
Time 21.53: Customer 0 departs.
  Customer 3 begins service after waiting 15.74.
Time 22.64: Customer 0 departs.
  Customer 4 begins service after waiting 16.76.
Time 22.94: Customer 0 departs.
  Customer 5 begins service after waiting 15.98.
Time 23.86: Customer 0 departs.
  Customer 6 begins service after waiting 16.10.
Time 25.66: Customer 0 departs.
  Customer 7 begins service after waiting 17.39.
Time 25.86: Customer 0 departs.
  Customer 8 begins service after waiting 16.59.
Time 26.09: Customer 0 departs.
  Customer 9 begins service after waiting 15.99.
Time 26.19: Customer 0 departs.

Average wait time: 14.53 units.

... 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', 6)
('Job 2', 5)

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

3. Run-time analysis

Stack & Queue implementations:

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

4. Closing remarks