Search⌘ K
AI Features
Home
Courses
Data Structures with Generic Types in Python

ArrayQueue: An Array-Based Queue

Explore the ArrayQueue data structure that efficiently implements a FIFO queue using a circular array and modular arithmetic. Learn how to add and remove elements in constant time, manage resizing, and maintain proper queue order with practical Python examples.

We'll cover the following...

ArrayQueue operations

In this lesson, we present the ArrayQueue data structure, which implements a FIFO (first-in-first-out) queue; elements are removed (using the remove() operation) from the queue in the same order they are added (using the add(x) operation).

Notice that an ArrayStack is not a good choice for an implementation of a FIFO queue because we must choose one end of the list upon which to add elements and then remove elements from the other end. One of the two operations must work on the head of the list, which involves calling add(i, x) or remove(i) with a value of i = 0. This gives a running time proportional to nn.

To obtain an efficient array-based implementation of a queue, we first notice that the problem would be easy if we had an infinite array aa. We could maintain one index j that keeps track of the next element to remove and an integer n that counts the number of elements in the queue. The queue elements would always be stored in

a[j],a[j+1],...,a[j+n−1]a[j],a[j+1],...,a[j+n−1]

Initially, both j and n would be set to 00. To add an element, we would place it in a[j + n] and increment n. To remove an element, we would remove it from a[j], increment j, and decrement n.

Of course, the problem with this solution is that it requires an infinite array. An ArrayQueue simulates this by using a finite array aa and modular arithmetic. This is the kind of arithmetic used when we are talking about the time of day. For example 10:0010:00 plus five hours gives 3:003:00. Formally, we say that

10+5=15=3 (mod 12)10 + 5 = 15 = 3\ (\text{mod\ } 12)

We read the latter part of this equation as “1515 is congruent to 33 modulo 1212”. We can also treat mod as a binary operator, so that

15 mod 12=315\ \text{mod}\ 12 = 3

More generally, for an integer aa and positive integer mm, a mod ma\ \text{mod}\ m is the unique integer r∈{0,...,m−1}r \in \{0,...,m − 1\} such that a=r+kma = r + km for some integer kk. Less formally, the value rr is the remainder we get when we divide a by mm. In many programming languages, including Java, the mod operator is represented using the %\% symbol

Note: %\% is sometimes referred to as the brain-dead mod operator, since it does not correctly implement the mathematical mod operator when the first argument is negative.

Modular arithmetic is useful for simulating an infinite array, since i mod a.length always gives a value in the range 0,...,a.length−10, . . . , \text{a.length} − 1. Using modular arithmetic we can store the queue elements at array locations

a[j%a.length],a[(j+1)%a.length],⋯ ,a[(j+n−1)%a.length]a[j\%\text{a.length}],a[(j+1)\%\text{a.length}],\cdots,a[(j+n−1)\%\text{a.length}]

This treats the array a like a circular array in which array indices larger than a.length − 1 “wrap around” to the beginning of the array.

The only remaining thing to worry about is taking care that the number of elements in the ArrayQueue does not exceed the size of aa.

Python 3.10.4
class ArrayQueue(BaseSet):
    def __init__(self, iterable=[]):
        self._initialize()
        self.add_all(iterable)
        
    def _initialize(self):
        self.a = new_array(1)
        self.j = 0
        self.n = 0

Visual demonstration

A sequence of add(x) and remove() operations on an ArrayQueue is illustrated below. A sequence of add(x) and remove(i) operations on an ArrayQueue. Arrows denote elements being copied. Operations that result in a call to _resize() are marked with an asterisk.

To implement add(x), we first check if a is full and, if necessary, call _resize() to increase the size of aa. Next, we store xx in a[(j + n) % a.length] and increment nn.

Python 3.10.4
class ArrayQueue(BaseSet):
    def __init__(self, iterable=[]):
        self._initialize()
        self.add_all(iterable)
        
    def add(self, x):
        if self.n + 1 > len(self.a): self._resize()
        self.a[(self.j+self.n) % len(self.a)] = x
        self.n += 1
        return True

To implement remove(), we first store a[j] so that we can return it later. Next, we decrement nn and increment jj (modulo a.length) by setting j = (j + 1) mod a.length. Finally, we return the stored value of a[j]. If necessary, we may call _resize() to decrease the size of aa.

Python 3.10.4
class ArrayQueue(BaseSet):
    def __init__(self, iterable=[]):
        self._initialize()
        self.add_all(iterable)
        
    def remove(self):
        if self.n == 0: raise IndexError()
        x = self.a[self.j]
        self.j = (self.j + 1) % len(self.a)
        self.n -= 1
        if len(self.a) >= 3*self.n: self._resize()
        return x

Finally, the _resize() operation is very similar to the _resize() operation of ArrayStack. It allocates a new array, bb, of size 2n2n and copies

a[j],a[(j+1)%a.length],⋯ ,a[(j+n−1)%a.length]a[j],a[(j+1)\%\text{a.length}],\cdots,a[(j+n−1)\%\text{a.length}]

onto

b[0],b[1],⋯ ,b[n−1]b[0],b[1],\cdots,b[n−1]

and sets j = 0.

Python 3.10.4
class ArrayQueue(BaseSet):
    def __init__(self, iterable=[]):
        self._initialize()
        self.add_all(iterable)
        
    def _resize(self):
        b = new_array(max(1, 2*self.n))
        for k in range(self.n):
            b[k] = self.a[(self.j+k) % len(self.a)]
        self.a = b
        self.j = 0

Summary

The following theorem summarizes the performance of the ArrayQueue data structure:

Theorem: An ArrayQueue implements the (FIFO) Queue interface. Ignoring the cost of calls to _resize(), an ArrayQueue supports the operations add(x) and remove() in O(1)O(1) time per operation. Furthermore, beginning with an empty ArrayQueue, any sequence of mm add(i, x) and remove(i) operations results in a total of O(m)O(m) time spent during all calls to _resize().

Python 3.10.4
"""Some base classes inherited by others"""
class BaseCollection(object):
    """Base class for everything"""
    def __init__(self):
        super(BaseCollection, self).__init__()
    
    def size(self):
        """This implementation works for almost every class in ODS"""
        return self.n
    
    def __len__(self):
        return self.size()
    
    def __str__(self):
        return "[" + ",".join([str(x) for x in self]) + "]"
    
    def __repr__(self):
        return self.__class__.__name__ \
            + "(["+ ",".join([repr(x) for x in self]) +"])"
class BaseSet(BaseCollection):
    """Base class for Set implementations"""
    def __init__(self):
        super(BaseSet, self).__init__()
                
    def add_all(self, a):
        for x in a:
            self.add(x)
            
    def __in__(self, x):
        return self.find(x) is not None
    def __eq__(self, a):
        if len(a) != len(self): return False
        for x in self:
            if not x in a: return False
        for x in a:
            if not x in self: return False
        return True
    def __ne__(self, a):
        return not self == a
class BaseList(BaseCollection):
    """Base class for List implementations"""
    def __init__(self):
        super(BaseList, self).__init__()
        
    def append(self, x):
        self.add(self.size(), x)
    def add_all(self, iterable):
        for x in iterable:
            self.append(x)
    def clear(self):
        """This can be overridden with more efficient implementations"""
        while self.size() > 0:
            self.remove(self.size()-1)
    def add_first(self, x):
        return self.add(0, x)
        
    def remove_first(self):
        return self.remove(0)
        
    def add_last(self, x):
        return self.add(self.size(), x)
    
    def remove_last(self):
        return self.remove(self.size()-1)
        
    def insert(i, x):
        self.add(i, x)
 
    def __iter__(self):
        """This implementation is good enough for array-based lists"""
        for i in range(len(self)):
            yield(self.get(i))
    def __eq__(self, a):
        if len(a) != len(self): return False
        it1 = iter(a)
        it2 = iter(self)
        for i in range(len(a)):
            if it1.next() != it2.next(): return False
        return True
    def __ne__(self, a):
        return not self == a
    
    def index(self, x):
        i = 0
        for y in self:
            if y == x:
                return i
            i += 1
        raise ValueError('%r is not in the list' % x)
    
    def remove_value(self, x):
        try:
            return self.remove(self.index(x))
        except ValueError:
            return False
    def __getitem__(self, key):
        return self.get(key)
    def __setitem__(self, key, value):
        return self.set(key, value)
    def __delitem__(self, i):
       self.remove(i)

Explanation

Let’s start our explanation from the start of main() in the main.py file.

  • Line 37: Here, two integer variables, m and n, are defined and initialized with the values 10000 and 50, respectively. m represents the maximum number of integers that can be added to the queue, and n represents the maximum size of the queue.
  • Line 39: It creates a queue q of type ArrayQueue that stores type Integer objects.
  • Line 41–47: It adds integers to the queue one at a time, from 0 up to 9999. After each addition, it checks whether the queue size is greater than the maximum allowed size n. If it is, the oldest element is removed from the queue, and an assertion checks if the removed element is equal to i - n. This check verifies that the queue has maintained the correct order of elements, and the assert statement will throw an exception if this is not the case.
  • Line 49–51: It removes the elements that are in range of q.size() while iterating the for loop.