ArrayQueue: An Array-Based Queue

Learn how to implement ArrayQueue data structure.

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 a. 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


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 a 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 (mod12)10 + 5 = 15 = 3\ (\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

15mod12=315\mod{12} = 3

More generally, for an integer aa and positive integer mm, amodma\mod{m} is the unique integer r{0,...,m1}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,...,0, . . . ,a.length1− 1. Using modular arithmetic we can store the queue elements at array locations


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 a.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy