#!/usr/bin/env python

# This bounded queue is implemented as a doubly-linked list with an additional size
# parameter. This enables O(1) time efficiency for the enqueue and dequeue
# operations, as these operations only operate on the first and last nodes.
# 
# This may not have optimal space efficiency because of the double pointers in
# each node, but it is a tradeoff for maximum time and throughput. The queue
# never examines nodes in the middle of the list, so it uses a minimal amount
# of memory throughput.

class BoundedQueue:
    size = 0
    maxSize = 0
    firstNode = None # end delimiter
    lastNode = None
    
    # constructor
    #
    # usage:
    # queue = BoundedQueue(maxSize)
    # 
    def __init__(self, maxSize):
        self.maxSize = maxSize
    
    # enqueue
    # 
    # usage:
    # queue.enqueue(num)
    # 
    # check that the size is within the maxSize
    # if it is, add a new node at the beginning of the list
    # otherwise, ignore the command
    #
    def enqueue(self, n):
        if self.size < self.maxSize:
            self.size += 1
            
            if self.firstNode is None:
                # empty list, so create a new node referencing end delimiters
                self.firstNode = DoublyLinkedNode(n, None, None)
                
                # first node and last node are the same for now
                self.lastNode = self.firstNode
            else:
                # non-empty list, so start by creating a node that references
                # the current first node
                newNode = DoublyLinkedNode(n, self.firstNode.prev, self.firstNode)
                
                # make the current first node point to the new first node
                self.firstNode.prev = newNode
                
                # make the first node our new node
                self.firstNode = newNode
    
    # dequeue
    # 
    # usage:
    # queue.dequeue()
    # 
    # if the queue is not empty, remove the last node from the list
    # otherwise, ignore the command
    # 
    def dequeue(self):
        if self.lastNode is not None:
            self.size -= 1
            
            # set the second-to-last node to be the last
            self.lastNode = self.lastNode.prev
            
            if self.lastNode is None:
                # list is empty, but firstNode still references a node
                self.firstNode = None
            else:
                # list is not empty, but lastNode has to link to None
                self.lastNode.next = None;
    
    # equalsList
    #
    # a comparison function for testing purposes. compares this queue to a list
    # 
    def equalsList(self, list):
        # check size first. guarantees that loop is best way to check
        #
        if self.size != len(list):
            return False
        else:
            # simultaneously loop over the values in the queue and in the list
            # to make sure they match
            #
            # start at last node because the oldest nodes get pushed to the end,
            # and this is a FIFO data structure
            
            node = self.lastNode
            index = 0
            
            while node is not None:
                if node.val != list[index]:
                    return False
                node = node.prev
                index += 1
            
            return True

class DoublyLinkedNode:
    def __init__(self, val, prev, next):
        self.val = val
        self.prev = prev
        self.next = next