# pytests
def test_insertIntoStack():
    s = Stack()
    s.push("There")
    s.push("Hi")
    assert s.size() == 2
    assert s.peek() == "Hi"
    assert s.isEmpty() == False

def test_deleteFromStack():
    s = Stack()
    s.push("There")
    s.push("Hi")
    x = s.pop()
    assert x == "Hi"
    assert s.peek() == "There"
    assert s.size() == 1
    assert s.isEmpty() == False
    y = s.pop()
    assert y == "There"
    assert s.size() == 0
    assert s.isEmpty() == True

class Stack:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[len(self.items)-1]

    def size(self):
        return len(self.items)

# pytests
def test_insertIntoQueue():
    q = Queue()
    assert q.isEmpty() == True
    assert q.size() == 0
    q.enqueue("Customer 1")
    q.enqueue("Customer 2")
    assert q.isEmpty() == False
    assert q.size() == 2
    
def test_removeFromQueue():
    q = Queue()
    q.enqueue("Customer 1")
    q.enqueue("Customer 2")
    assert q.dequeue() == "Customer 1"
    assert q.isEmpty() == False
    assert q.size() == 1
    assert q.dequeue() == "Customer 2"
    assert q.isEmpty() == True
    assert q.size() == 0

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

    def isEmpty(self):
        return self.items == []

    def enqueue(self, item):
        self.items.insert(0, item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)

# pytests
def test_Deque():
    d = Deque()
    assert d.isEmpty() == True
    assert d.size() == 0
    d.addFront(10)
    d.addFront(20)
    d.addRear(30)
    d.addRear(40)
    assert d.isEmpty() == False
    assert d.size() == 4
    assert d.removeFront() == 20
    assert d.removeRear() == 40
    assert d.isEmpty() == False
    assert d.size() == 2
    assert d.removeRear() == 30
    assert d.removeRear() == 10
    assert d.isEmpty() == True
    assert d.size() == 0

class Deque:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def addFront(self, item):
        self.items.append(item)

    def addRear(self, item):
        self.items.insert(0, item)

    def removeFront(self):
        return self.items.pop()

    def removeRear(self):
        return self.items.pop(0)

    def size(self):
        return len(self.items)

Time:
* In-person (EMBAR HALL), Thursday 10/30 11am -12:15pm PST

Logistics:
* Bring a writing utensil and STUDENT ID
* Please write legibly (if we can't read your answer, we can't grade it)
* When leaving the room, you must hand in your exam and present your STUDENT ID
* Closed book (no notes / book / electronic devices (including smart watches / AI glasses))
* TAs and I will be proctoring the exam. We can answer any CLARIFYING questions

Possible Types of Questions:
* True / False (if False, briefly state why (1 sentence))
* Short Answer - Briefly define / state / describe / ...
* Given some code, write the output / state the O-notation
* Write code satisfying a specification
* Given some partial algorithm, fill in the blank to make it work
* Draw diagrams

Midterm Topics:

Will cover material from the beginning of the class up until the end of week 4's (10/23) lecture
    * Linked Lists won't be asked on the midterm, but will be on the final exam

Python Basics 
- Types
    * I don't expect students to know ALL Python basics, but do expect students to know
    the ones we explicitly covered in lectures and/or assignments
    * int, float, boolean, strings, lists, sets, dictionaries, ...
    * conversion functions (int(), float(), str(), ...)
    * mutable vs. immutable
- Relational / logical operators (==, <, >, <=, >=, and, or, not, ...)
- Python Lists
    * Supporting methods (count, pop, append, insert, ...)
    * List / string slicing [:]
- Understanding under-the-hood functionality of lists and dictionaries
- Strings
    * Supporting methods (replace, split, find, ...)
- Function definitions
- Control Structures (if, else, elif, for, while, ...)

Python Errors / Exceptions
- Runtime vs. Syntax errors
- Exception types (NameError, TypeError, ZeroDivisionError, ...)
- Exception handling
    * try / except / raise
    * Flow of execution
    * Passing exceptions to function / method caller(s) when not handled in try / except
    * Multiple except blocks
    * Handling Exceptions in an Inheritance hierarchy

Object Oriented Programming
- Defining classes and methods
- constructors (defining / initializing default state)
- Shallow vs. Deep equality (overloading __eq__ method)
- Overloading operators (__str__, __add__, __le__, ...)
- Inheritance
    * Know method lookup for inheritance hierarchy
    * implementation for inherited fields / methods
    * overriding inherited methods
    * calling super / base class(es) methods

Testing
- Test Driven Development (TDD)
- pytest

Algorithm Analysis and O-notation
- Know how to derive O-notation for snippets of code

Recursion
- Implementation of recursive functions and O-notation analysis
- Understanding how recursive algorithms are managed by the call stack
- Draw call stack given a recursive function

Binary Search
- Search for items in a SORTED list
- Know the implementation (as covered in textbook / lecture) and O-notation

Linear Data Structures
- Know implementations (as covered in textbook / lecture) and O-notation
for various functionality
    * Stacks, Queues, Deques