<jupyter_start><jupyter_text>Chapter 3: Stacks and Queues<jupyter_code>class Stack:
    def __init__(self):
        self.items = []
    def is_empty(self):
        return self.items == []
    def push(self, item):
        self.items.append(item)
    def pop(self):
        return self.items.pop() # Python's pop removes the last element in the list and returns it
    def peek(self):
        # Peek returns the top of the stack
        return self.items[-1]
    def size(self):
        return len(self.items)

class Queue:
    def __init__(self):
        self.items = []
    def is_empty(self):
        return self.items == []
    def add(self, item):
        self.items.append(item)
    def remove(self):
        del self.items[0] # Python's del removes an indexed element in O(1) time
    def peek(self):
        # Peek returns the top of the queue
        return self.items[0]
    def size(self):
        return len(self.items)<jupyter_output><empty_output><jupyter_text>3.1 Three in One:Describe how you could use a single array to implement three stacks. To use a single array to implement three stacks, one could fix the available space for a single stack, then divide the array into three parts to hold each stack.<jupyter_code># Each stack will have a threshhold of 15 items (at first).
class ThreeStack:
    def __init__(self, size=45, num_stacks=3):
        self.items = [None] * size
        self.size = size
        self.num_stacks = num_stacks
        self.stack_size = int(size / num_stacks)
    def is_empty(self, stack_id):
        # stack_id starts at 1
        return self.items[self.stack_size * (stack_id - 1)] is None
    def push(self, stack_id, item):
        count = 0
        index = self.stack_size * (stack_id - 1)
        while count < self.stack_size:
            if self.items[index] is None:
                self.items[index] = item
                return "Successfully added."
            else:
                count += 1
                index += 1
        return "Stack full."
    def pop(self, stack_id):
        count = 0
        index = self.stack_size * (stack_id - 1)
        while count < self.stack_size:
            if self.items[index] is None and count > 0:
                result = self.items[index - 1]
                self.items[index - 1] = None
                return result
            elif self.items[index] is None:
                return Exception("Stack is empty.")
            else:
                count += 1
                index += 1
    def peek(self, stack_id):
        count = 0
        index = self.stack_size * (stack_id - 1)
        while count < self.stack_size:
            if self.items[index] is None and count > 0:
                return self.items[index - 1]
            elif self.items[index] is None:
                return Exception("Stack is empty.")
            else:
                count += 1
                index += 1<jupyter_output><empty_output><jupyter_text>3.2 Stack MinHow would you design a stack which, in addition to push and pop, has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.<jupyter_code>class StackMin(Stack):
    def __init__(self, min_stack=None):
        self.min_stack = min_stack
        super().__init__()
    def push(self, item):
        if self.min_stack is None:
            self.min_stack = item
        self.items.append(item)
    def minStack(self):
        return self.min_stack
test = StackMin()
test.push(4)
test.push(5)
test.push(8)
test.push(9)
print(test.minStack())
test.push(1)
print(test.minStack())<jupyter_output>4<jupyter_text>3.3 Stack of PlatesImagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this. SetOfStacks should be composed of several stacks and should create a new stack once the previous one exceeds capacity. SetOfStacks.push() and SetOfStacks.pop() should behave identically to a single stack (that is, pop() should return the same values as it would if there were just a single stack).FOLLOW UPImplement a function popAt(int index) which performs a pop operation on a specific sub-stack.<jupyter_code>class SetOfStacks():
    def __init__(self, capacity=10):
        self.capacity = capacity
        self.items = [[]]
    def is_empty():
        return self.items == [[]]
    def push(item):
        if len(self.items[-1]) <= capacity:
            self.items[-1].append(item)
        else:
            self.items.append([item])
    def pop(item):
        if len(self.items) > 1 and len(self.items[-1]) <= 1:
            temp = self.items[-1].pop()
            del self.items[-1]
            return temp()
        else:
            return self.items[-1].pop()
    def peek():
        return self.items[-1][-1]
    def popAt(index):
        result = self.items[index].pop()
        size = len(self.items)
        # Check to see if a shift is necessary
        if index == size - 1:
            return result
        # Rebalance the stacks
        while index < size - 2:
            self.items[index].append(self.items[index + 1].pop(0))
            index += 1
        return result
l = [[]]
len(l[-1])<jupyter_output><empty_output><jupyter_text>3.4 Queues via StacksImplement a MyQueue class which implements a queue using two stacks.<jupyter_code>class MyQueue():
    def __init__(self):
        self.front_first = Stack()
        self.back_first = Stack()
    def is_empty():
        return self.front_first.is_empty() and self.back_first.is_empty()
    def switch():
        if self.front_first.is_empty():
            while not self.back_first.is_empty():
                self.front_first.push(self.back_first.pop())
        else:
            while not self.front_first.is_empty():
                self.back_first.push(self.front_first.pop())
    def add(item):
        if self.is_empty(item):
            self.front_first.push(item)
        else:
            if self.front_first.is_empty():
                self.switch()
                self.front_first.push()
    def remove():
        if self.is_empty():
            return Exception("Queue is empty.")
        if self.back_first.is_empty():
            self.switch()
            self.back_first.pop()
        else:
            self.back_first.pop()
    def peek():
        if self.is_empty():
            return Exception("Queue is empty.")
        if self.back_first.is_empty():
            self.switch()
            return self.back_first.peek()
        else:
            return self.back_first.peek()<jupyter_output><empty_output><jupyter_text>3.5 Sort StackWrite a program to sort a stack such that the smallest items are on the top. You can use an additional temporary stack, but you may not copy the elements into any other data structure (such as an array). The stack supports the following operations: push, pop, peek, and isEmpty.<jupyter_code>def sort_stack(stack):
    if stack.is_empty():
        return Exception("Stack is empty.")
    buffer_stack = Stack()
    while not stack.is_empty():
        element = stack.pop()
        while (not buffer_stack.is_empty()) and (element < buffer_stack.peek()):
            stack.push(buffer_stack.pop())
        buffer_stack.push(element)
    while (not buffer_stack.is_empty()):
        stack.push(buffer_stack.pop())
test_sort = Stack()
test_sort.push(4)
test_sort.push(3)
test_sort.push(7)
test_sort.push(3)
test_sort.push(0)
test_sort.push(10)
print(test_sort.items)
sort_stack(test_sort)
print(test_sort.items)<jupyter_output>[10, 7, 4, 3, 3, 0]<jupyter_text>3.6 Animal ShelterAn animal shelter, which holds only dogs and cats, operates on a strictly "first in, first out" basis. People must adopt either the "oldest" (based on arrival time) of all animals at the shelter, or they can select whether they would prefer a dog or a cat (and will receive the oldest animal of that type). They cannot select which specific animal they would like. Create the data structures to maintain this system and implement operations such as enqueue, dequeueAny, dequeueDog, and dequeueCat. You may use the built-in LinkedList data structure.<jupyter_code>class Animal():
    def __init__(self, name, species):
        self.name = name
        self.species = species
class AnimalShelter():
    def __init__(self):
        self.dog_queue = []
        self.cat_queue = []
        self.queue = []
    def enqueue(animal):
        if animal.species == "dog":
            self.dog_queue.append(animal)
        else:
            self.cat_queue.append(animal)
        self.queue.append(animal)
    def dequeue_any(species=None):
        if species is None:
            return self.queue.pop(0)
        else:
            index = 0
            while index < len(self.queue):
                if self.queue[index].species == species:
                    return self.queue[index]
                else:
                    index += 1
            return Exception("Animal preference unavailable.")
    def dequeue_dog():
        return self.dequeue_any("dog")
    def dequeue_cat():
        return self.dequeue_any("cat")<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09995658780117213, 'fraction_numerical': 0.009008031256783157, 'mean_word_length': 2.335142960550127, 'pattern_counts': {'":': 1, '<': 35, '<?xml version=': 0, '>': 30, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '374344', 'license': 'Apache-2.0', 'n_tokens_mistral': 2749, 'n_tokens_neox': 2651, 'n_words': 844, 'path': 'chapter3.ipynb', 'repo_name': 'hangulu/ctci', 'size': '9214'}