stackoverflow question

gistfile1.txt

#!/usr/bin/env python
# coding: utf-8

# In[1]:


"""
Queue
"""

import logging

logger = logging.getLogger(__name__)


class UnderflowError(Exception):
    pass


class OverflowError(Exception):
    pass


class Queue:
    """Queue implements first-in-first-out (FIFO)
    
    Ref:
        - Introduction to Algorithms
        - https://ita.skanev.com/10/01/04.html
    """

    def __init__(self, size: int = 10):
        self.size = size
        self.head = None
        self.tail = 1
        self.array = [None] * self.size

    def enqueue(self, element: int):
        """Adds an element to the tail of the queue

        Args:
            element (int): element to add

        Raises:
            Exception: when the Queue overflows, when the queue is full and we
                try to add a new element
        """

        if self.tail == self.head:
            raise OverflowError()

        self.array[self.tail - 1] = element

        if self.head is None:
            self.head = self.tail

        if self.tail == self.size:
            self.tail = 1
        else:
            self.tail += 1

        logger.debug(
            f"array: {self.array} , head: {self.head}, tail: {self.tail}"
        )

    def dequeue(self) -> int:
        """Deletes and returns the head element of the queue

        Raises:
            Exception: when the queue underflows, when the queue is empty and
                we try to dequeue

        Returns:
            int: element at the head of the queue
        """

        if self.head is None:
            raise UnderflowError("Underflow")

        x = self.array[self.head - 1]

        if self.head == self.size:
            self.head = 1
        else:
            self.head += 1

        if self.tail == self.head:
            self.head = None

        logger.debug(
            f"array: {self.array} , head: {self.head}, tail: {self.tail}"
        )
        return x


# In[2]:


import pytest

def test_queue_based_stack(stack):

    stack.push(10)
    stack.push(1)
    stack.push(3)
    stack.push(9)
    stack.push(15)

    assert 15 == stack.pop()
    assert 9 == stack.pop()
    assert 3 == stack.pop()

    stack.push(5)

    assert 5 == stack.pop()

    stack.pop()
    stack.pop()

    with pytest.raises(Exception):
        stack.pop()

    for i in range(10):
        stack.push(i)

    with pytest.raises(Exception):
        stack.push(10)


# ### Queue using 2 stacks

# In[3]:


class QueueBasedStack1:
    """Queue built using 2 stacks
    """

    def __init__(self, size: int = 10):
        self.q1 = Queue(size)
        self.q2 = Queue(size)

    def push(self, element):
        self.q1.enqueue(element)

    def pop(self):
        _x = None
        while True:
            try:
                x = self.q1.dequeue()
            except UnderflowError:
                self.q1, self.q2 = self.q2, self.q1
                logger.debug(f"x: {x}, _x: {_x}")
                return _x

            if _x:
                self.q2.enqueue(_x)
            _x = x


# In[4]:


test_queue_based_stack(QueueBasedStack1(10))


# Same as the above class, only difference is that I removed the logger.debug statement under the `execpt UnderflowError`

# In[5]:


class QueueBasedStack2:
    """Queue built using 2 stacks
    """

    def __init__(self, size: int = 10):
        self.q1 = Queue(size)
        self.q2 = Queue(size)

    def push(self, element):
        self.q1.enqueue(element)

    def pop(self):
        _x = None
        while True:
            try:
                x = self.q1.dequeue()
            except UnderflowError:
                self.q1, self.q2 = self.q2, self.q1
                return _x

            if _x:
                self.q2.enqueue(_x)
            _x = x


# In[6]:


test_queue_based_stack(QueueBasedStack2(10))