StacksQueues/Python/ArrayQueue

From charlesreid1

Queue data structure, implemented in Python using an underlying array-based structure - a list. (See also: Arrays/Python)

Link: https://git.charlesreid1.com/cs/python/src/master/stacks-queues-deques/queues/ArrayQueue.py

Class code

"""
Queue ADT: ArrayQueue

This class implements the following methods:
    Q.enqueue(e)
    Q.dequeue()
    Q.first()
    Q.is_empty()
    len(Q)

This class utilizes an array-based data structure.

The Queue class needs to keep track of where the
beginning and end of the structure is.
This will dynamically expand under the hood
as needed. This is an O(1) data structure,
when amortized.

It needs to keep track of three things:
- pointer to first item in queue
- number of elements in queue (use in place of last pointer)
- pointer to data structure itself

"""

class Empty(Exception):
    pass

class ArrayQueue:

    def __init__(self):
        """Keep track of 3 things"""
        INIT_CAP = 10
        self._data = [None]*INIT_CAP
        self._front = 0
        self._n = 0

    def __len__(self):
        """Return number of elements in queue"""
        return self._n

    def __str__(self):
        return str(self._data)
        #ix_sequence = [(self._front+i)%(len(self._data)) for i in range(self._n)]
        #contents = ",".join([str(self._data[ix]) for ix in ix_sequence])
        #return "[" + contents + "]"

   #####################
   # Note: start with the
   # simple stuff. __getitem__,
   # __len__, __init__, __str__, etc.

    def is_empty(self):
        """Returns true if no elements in queue"""
        return self._n==0

    def dequeue(self):
        """Pop an item from the front of the queue (inch the front pointer along)"""
        if(self.is_empty()):
            raise Empty("oops, empty queue")

        dafront = self._data[self._front]

        self._data[self._front]=None # clean up
        self._front = (self._front+1)%(len(self._data)) # update front pointer
        self._n -= 1

        # Really, we need to resize this thing to be smaller
        # when we remove stuff from it.
        # If it is too big by a quarter, chop it in half.
        if(self._n < len(self._data)//4):
            self.resize( len(self._data)//2 )

        return dafront


    def enqueue(self, e):
        """Add an item to the back of the queue"""
        if(self._n==len(self._data)):
            self.resize(2*self._n)

        insert_index = (self._front + self._n )%(len(self._data))
        self._data[insert_index] = e
        self._n += 1

    def resize(self,newsize):
        """Resize, and shift everything to the front"""
        old = self._data
        walk = self._front
        self._data = [None]*newsize
        for k in range(self._n):
            self._data[k] = old[walk]
            walk = (walk+1)%len(old)
        self._front = 0

    def first(self):
        return self._data[self._first]

Class test

if __name__=="__main__":
    print("Testing ArrayQueue.")
    a = ArrayQueue()
    for c in "ABCDEFGHIJKLMNOPQRSTUVWX":
        a.enqueue(c)
        print(a)
    for i in range(15):
        a.dequeue()
        print(a)
    for c in "9876543":
        a.enqueue(c)
        print(a)
    for i in range(8):
        a.dequeue()
        print(a)
    print("Final:")
    print(a)

Output


$ python ArrayQueue.py
Testing ArrayQueue.
['A', None, None, None, None, None, None, None, None, None]
['A', 'B', None, None, None, None, None, None, None, None]
['A', 'B', 'C', None, None, None, None, None, None, None]
['A', 'B', 'C', 'D', None, None, None, None, None, None]
['A', 'B', 'C', 'D', 'E', None, None, None, None, None]
['A', 'B', 'C', 'D', 'E', 'F', None, None, None, None]
['A', 'B', 'C', 'D', 'E', 'F', 'G', None, None, None]
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', None, None]
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', None]
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J']
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', None, None, None, None, None, None, None, None, None]
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', None, None, None, None, None, None, None, None]
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', None, None, None, None, None, None, None]
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', None, None, None, None, None, None]
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', None, None, None, None, None]
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', None, None, None, None]
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', None, None, None]
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', None, None]
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', None]
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T']
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
[None, 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
[None, None, 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
[None, None, None, 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
[None, None, None, None, 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
[None, None, None, None, None, 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
[None, None, None, None, None, None, 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
[None, None, None, None, None, None, None, 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
[None, None, None, None, None, None, None, None, 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
[None, None, None, None, None, None, None, None, None, 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
[None, None, None, None, None, None, None, None, None, None, 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
[None, None, None, None, None, None, None, None, None, None, None, 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
[None, None, None, None, None, None, None, None, None, None, None, None, 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
[None, None, None, None, None, None, None, None, None, None, None, None, None, 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
[None, None, None, None, None, None, None, None, None, None, None, None, None, None, 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
['P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', None, None, None, None, None, None, None, None, None, None, None]
['P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', '9', None, None, None, None, None, None, None, None, None, None]
['P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', '9', '8', None, None, None, None, None, None, None, None, None]
['P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', '9', '8', '7', None, None, None, None, None, None, None, None]
['P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', '9', '8', '7', '6', None, None, None, None, None, None, None]
['P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', '9', '8', '7', '6', '5', None, None, None, None, None, None]
['P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', '9', '8', '7', '6', '5', '4', None, None, None, None, None]
['P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', '9', '8', '7', '6', '5', '4', '3', None, None, None, None]
[None, 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', '9', '8', '7', '6', '5', '4', '3', None, None, None, None]
[None, None, 'R', 'S', 'T', 'U', 'V', 'W', 'X', '9', '8', '7', '6', '5', '4', '3', None, None, None, None]
[None, None, None, 'S', 'T', 'U', 'V', 'W', 'X', '9', '8', '7', '6', '5', '4', '3', None, None, None, None]
[None, None, None, None, 'T', 'U', 'V', 'W', 'X', '9', '8', '7', '6', '5', '4', '3', None, None, None, None]
[None, None, None, None, None, 'U', 'V', 'W', 'X', '9', '8', '7', '6', '5', '4', '3', None, None, None, None]
[None, None, None, None, None, None, 'V', 'W', 'X', '9', '8', '7', '6', '5', '4', '3', None, None, None, None]
[None, None, None, None, None, None, None, 'W', 'X', '9', '8', '7', '6', '5', '4', '3', None, None, None, None]
[None, None, None, None, None, None, None, None, 'X', '9', '8', '7', '6', '5', '4', '3', None, None, None, None]
Final:
[None, None, None, None, None, None, None, None, 'X', '9', '8', '7', '6', '5', '4', '3', None, None, None, None]

Flags


CSFlag.jpg
Stacks and Queues
Part of Computer Science Notes

Series on Data Structures


StacksQueues


Stacks and Queues: Python

StacksQueues/Python  · StacksQueues/Python/ArrayStack  · StacksQueues/Python/ArrayQueue  · StacksQueues/Python/ArrayDeque

StacksQueues/Python/LinkedStack


Stacks and Queues: Java

StacksQueues/Java  · StacksQueues/Java/ArrayStack  · StacksQueues/Java/ArrayQueue  · StacksQueues/Java/ArrayQueueFS  · StacksQueues/Java/ArrayDeque

StacksQueues/Java/LinkedStack  · StacksQueues/Java/LinkedQueue  · StacksQueues/Java/LinkedDeque


Applications

Postfix_Expressions#Stacks  · StacksQueues/Subsets  · StacksQueues/Subsets/Java


Flags  · Template:StacksQueuesFlagBase  · e



Retrieved from "https://charlesreid1.com/w/index.php?title=StacksQueues/Python/ArrayQueue&oldid=26912"