PW 18: Queues

This PW consist of one huge class. I'll try to add comments to explicitly state what I did. Take your time to read the code, test the functions, and draw some the queues!

from stack import stack

class queue:
    def __init__(self):
        """
        """
        self.stackIn  = stack()
        self.stackOut = stack()

    def __str__(self):
        """
        """
        string = "]"
        tmp = stack()
        while not self.stackOut.is_empty():
            e = self.stackOut.pop()
            string += str(e)
            string += ", "
            tmp.push(e)

        while not tmp.is_empty():
            self.stackOut.push(tmp.pop())

        while not self.stackIn.is_empty():
            e = self.stackIn.pop()
            string += str(e)
            string += ", "
            tmp.push(e)

        while not tmp.is_empty():
            self.stackIn.push(tmp.pop())

        
        string += "["
        return string

    def enqueue(self, x : int):
        """
        """
        self.stackIn.push(x)
        return self

    def is_empty(self):
        """
        """
        return self.stackIn.is_empty() and self.stackOut.is_empty()

    def dequeue(self):
        """
        """
        if self.is_empty():
            raise IndexError
        if self.stackOut.is_empty():
            while not self.stackIn.is_empty():
                self.stackOut.push(self.stackIn.pop())
        return self.stackOut.pop()

    def from_list(self, l: list):
        """
        """
        for e in l:
            self.stackIn.push(e)
        while not self.stackIn.is_empty():
            self.stackOut.push(self.stackIn.pop())

    # ---------------------------------------------------------------------------

    def __copy__(self):
        """
        Return a deep copy of the queue.
        Time Cost: O(4n) = O(n)
        """
        l = 0
        tmp = stack()
        res = queue()
        while not self.stackOut.is_empty():
            e = self.stackOut.pop()
            l += 1
            tmp.push(e)

        while not tmp.is_empty():
            e = tmp.pop()
            self.stackOut.push(e)
            res.stackOut.push(e)

        while not self.stackIn.is_empty():
            e = self.stackIn.pop()
            tmp.push(e)

        while not tmp.is_empty():
            e = tmp.pop()
            self.stackIn.push()
            res.stackIn.push(e)

        return res

    def __len__(self):
        """
        Get the lenght of the queue.
        Time Cost: O(4n) = O(n)
        """
        l = 0
        tmp = stack()
        while not self.stackOut.is_empty():
            e = self.stackOut.pop()
            l += 1
            tmp.push(e)

        while not tmp.is_empty():
            self.stackOut.push(tmp.pop())

        while not self.stackIn.is_empty():
            e = self.stackIn.pop()
            l += 1
            tmp.push(e)

        while not tmp.is_empty():
            self.stackIn.push(tmp.pop())

        return l
    
    def reverse(self):
        """
        Reverse the order of a stack
        Time Cost: O(4n) = O(n)
        """
        tmp1 = stack()
        tmp2 = stack()
        while not self.stackOut.is_empty():
            e = self.stackOut.pop()
            tmp1.push(e)

        while not self.stackIn.is_empty():
            self.stackOut.push(self.stackIn.pop())

        while not tmp1.is_empty():
            tmp2.push(tmp1.pop())

        while not tmp2.is_empty():
            self.stackIn.push(tmp2.pop())

        return self

    def concatenate(self, other: queue):
        if type(q) != queue:
            raise TypeError
        tmp = stack()
        while not other.stackIn.is_empty():
            self.stackOut.push(other.stackIn.pop())

        while not other.stackOut.is_empty():
            tmp.push(other.stackOut.pop())

        while not tmp.is_empty():
            self.stackOut.push(tmp.pop())

    def insertion_sort(self, x : int):
        """
        Reverse the order of a stack
        Time Cost: O(4n) = O(n)
        """
        is_added = False
        tmp = stack()
        while not self.stackIn.is_empty():
            e = self.stackIn.pop()
            tmp.push(e)

        while not tmp.is_empty():
            e = tmp.pop()
            if e >= x and not is_added:
                self.stackIn.push(x)
                is_added = True
            self.stackIn.push(e)

        while not self.stackOut.is_empty():
            e = self.stackOut.pop()
            tmp.push(e)

        while not tmp.is_empty():
            e = tmp.pop()
            if e <= x and not is_added:
                self.stackOut.push(x)
                is_added = True
            self.stackOut.push(e)

    def insertion_sort(self):
        # Work In Progress
        pass