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   # amortized append is O(1) and del [-1] is O(1)
# using python list to represent the array
class Stack:
    def __init__(self):
        self.data = []
        
    def push(self, val):
        # use list append O(1)
        self.data.append(val)

    def empty(self):   # pyhton list len()  is O(1)
        return len(self.data)==0

    def pop(self):   #must return the value on top of the stack, and delete it from the stack
        assert(not self.empty())  # calls the empty we just wrote
        #  use del [-1]   O(1)
        temp = self.data[-1]
        del self.data[-1]   # self.data.pop(-1)
        return temp
            
    def peek(self):
        assert(not self.empty())
        return self.data[-1] 
    
    def __bool__(self):    # supports  if stack exists
        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

s.data

[]

# linked implementation

class Stack:
    class Node:
        def __init__(self, val, next=None):
            self.val = val
            self.next  = next
    
    def __init__(self):   # stack constructor, Stack is empty, top is None
        self.top = None

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

s.top.val

9

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

#     )(       can't just count parens
# push open parens on stack
#  if we see a close paren, pop an open off the stack (that is the paired open for the close)
# if we see a close paren and stack is empty, the expression is not valid
# if we are done reading the expression and the stack is not empty, the  expression is not valid
def check_parens(expr):   # expr is a STRING
    s = Stack()
    for c in expr:   # for every character in the String
        if c == '(':
            s.push(c)
        elif c==')':
            if s:
                temp=s.pop()
            else:   # if stack was empty when I saw a close paren, expression is not valid
                return False
    # if stack is not empty when no more characters in expression , expression is not valid
    if s:
        return False
    else:
        return True

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 *'

# if I read a number, push it on the stack
# if I read an operator, pop 2 numbers off stack, do the arithmetic, push the result on the stack
# not doing error checking on the expression (assume expression in postfix is valid)
def eval_postfix(expr):
    s = Stack()
    toks = expr.split()   #use String split function to break the string into a list of numbers and operators
    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(x*y)  
        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

eval_postfix('1 2 * +')

---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-26-14adc3aaf0bc> in <module>
----> 1 eval_postfix('1 2 * +')

<ipython-input-22-362cb6ae4b93> in eval_postfix(expr)
      8         if t=='+':
      9             x=s.pop()
---> 10             y=s.pop()
     11             s.push(x+y)
     12         elif t=='-':

<ipython-input-7-a5ff08888ce7> in pop(self)
     18 
     19     def pop(self):
---> 20         assert(not self.empty())
     21         temp = self.top.val
     22         self.top = self.top.next

AssertionError: 

eval_postfix('1 2 4 5 * +')   #but the stack is left non empty, need to do error checking on that

22

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

# 0 is a wall, 1 is a place to walk, 2 is door in, 3 is door out
# 4 is "place of interest"  !     5 is "visited already"  +
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 is a [row,col] pair   to is a [row,col] pair
        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):   # generate a list of possible moves from the loaction "place"
    moves = [Move(place, (place[0]+d[0], place[1]+d[1]))
             #  (prevRow,sameCOl)  (nextRow,sameCol)  (sameRow,prevCol) (sameRow,nextCol)
             #  up  down   left  rigth
            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

maze = parse_maze(maze_str)
print_maze(maze)

######
I    #
# ## #
# ####
#    O
######

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
print_maze(maze)
moves(maze, (1, 1))

######
+    #
# ## #
# ####
#    O
######

[(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:    # as long as not the exit
        maze[loc[0]][loc[1]] = 4       #push on stack and visit later
    
def display(maze):
    clear_output(True)
    print_maze(maze)
    sleep(1.5)

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

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:    #not good, dequeue is O(n)
    def __init__(self):
        self.data = []    # front of the queue is [0]   back of the queue is [-1]

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

    def dequeue(self):
        assert(not self.empty())
        temp=self.data[0]
        del self.data[0]  # or self.data.pop(0)       O(n)  because needs to move everything down
        return temp
    
    
    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   #self.head is front of the line, self.tail is end of the line

    def enqueue(self, val):    #O(1)
        #assuming a non empty list
        if self.head:
            self.tail.next=Queue.Node(val)
            self.tail=self.tail.next
        else:   #first node added special case
            self.head=Queue.Node(val)
            self.tail=self.head
    
    def dequeue(self):
        assert(not self.empty())
        temp=self.head.val
        self.head=self.head.next
        if self.head==None:  #remove laST NOde sepcial case
            self.tail=None
        return temp
    
    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) )

    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(1.5)  # mean 1/1.5
                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 1.23: Customer 0 arrives.
  Customer 0 begins service (duration 0.74).
Time 1.34: Customer 1 arrives.
  Customer 1 waits in queue.
Time 1.97: Customer 2 arrives.
  Customer 2 waits in queue.
Time 2.10: Customer 3 arrives.
  Customer 3 waits in queue.
Time 2.28: Customer 4 arrives.
  Customer 4 waits in queue.
Time 2.84: Customer 5 arrives.
  Customer 5 waits in queue.
Time 3.16: Customer 6 arrives.
  Customer 6 waits in queue.
Time 4.53: Customer 7 arrives.
  Customer 7 waits in queue.
Time 4.65: Customer 8 arrives.
  Customer 8 waits in queue.
Time 4.67: Customer 9 arrives.
  Customer 9 waits in queue.
Time 1.98: Customer 0 departs.
  Customer 1 begins service after waiting 0.64.
Time 2.80: Customer 0 departs.
  Customer 2 begins service after waiting 0.84.
Time 2.84: Customer 0 departs.
  Customer 3 begins service after waiting 0.74.
Time 4.17: Customer 0 departs.
  Customer 4 begins service after waiting 1.89.
Time 4.37: Customer 0 departs.
  Customer 5 begins service after waiting 1.53.
Time 4.44: Customer 0 departs.
  Customer 6 begins service after waiting 1.28.
Time 5.12: Customer 0 departs.
  Customer 7 begins service after waiting 0.59.
Time 5.24: Customer 0 departs.
  Customer 8 begins service after waiting 0.58.
Time 6.61: Customer 0 departs.
  Customer 9 begins service after waiting 1.95.
Time 7.73: Customer 0 departs.

Average wait time: 1.00 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

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

3. Run-time analysis

Stack & Queue implementations:

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

4. Closing remarks