arrayqueue.py

Below is the syntax highlighted version of arrayqueue.py from §4.3 Stacks and Queues.

#-----------------------------------------------------------------------
# arrayqueue.py
#-----------------------------------------------------------------------

import stdarray
import stdio

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

# The initial number of elements in the array that is stored within
# any Queue object.

_INITIAL_COUNT = 2

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

# A Queue object is a first-in-first-out collection.

class Queue:

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

    # Construct an empty Queue object.

    def __init__(self):
        self._a = stdarray.create1D(_INITIAL_COUNT, None) # Items
        self._count = 0  # Number of items
        self._first = 0  # Index of first item
        self._last = 0   # Index of last item

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

    # Resize the array stored within self such that it has
    # max elements.

    def _resize(self, max):
        temp = stdarray.create1D(max, None)
        for i in range(self._count):
            temp[i] = self._a[(self._first + i) % len(self._a)]
        self._a = temp
        self._first = 0
        self._last = self._count

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

    # Return True iff self is empty.

    def isEmpty(self):
        return self._count == 0

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

    # Add item to the end of self.

    def enqueue(self, item):
        if self._count == len(self._a):
            self._resize(2 * len(self._a))
        self._a[self._last] = item
        self._last += 1
        self._count += 1
        if self._last == len(self._a):
            self._last = 0

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

    # Remove the first item of self and return it.

    def dequeue(self):
        if self.isEmpty():
            raise Exception('Queue underflow')
        item = self._a[self._first]
        self._a[self._first] = None
        self._count -= 1
        self._first += 1
        if self._first == len(self._a):
            self._first = 0
        if (self._count > 0) and (self._count == (len(self._a) // 4)):
            self._resize(len(self._a) // 2)

        return item

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

    # Return the number of items in self.

    def __len__(self):
        return self._count

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

    # Return a string representation of self.

    def __str__(self):
        s = ''
        for i in range(self._count):
            s += self._a[(self._first + i) % len(self._a)] + ' '
        return s
    
#-----------------------------------------------------------------------

# Test the Queue class by reading strings from standard input and
# pushing or popping as indicated. A minus sign indicates pop (and
# write to standard output), and any other string indicates push.

def main():
    q = Queue()
    while not stdio.isEmpty():
        item = stdio.readString()
        if item != '-':
            q.enqueue(item)
        else:
            stdio.write(q.dequeue() + ' ')
    stdio.writeln()

if __name__ == '__main__':
    main()
    
#-----------------------------------------------------------------------

# more tobe.txt 
# to be or not to - be - - that - - - is

# python arrayqueue.py < tobe.txt 
# to be or not to be