Introduction to the Queue Data Structure – Array Implementation

The queue data structure (we will look at queue array implementation in this post) is one of the fundamental data structures in computer science.

Queue is an example of a FIFO data structure.

In this tutorial, we will be exploring the following concepts regarding the queue data structure.

  • Key features and properties.
  • Implementation details.

Without further ado, let’s dive into the content.

What is the Queue Data Structure?

 

queue data structure visual diagram

The queue data structure is like a queue/line.

No, I am not trying to be funny.

The queue data structure ensures that you come out in the order in which you joined the line/queue. For example, if an element was inserted into the queue data structure, it would have to wait until it reaches the front of the queue before it can be removed.

If you are waiting in line for a meal, you would naturally be upset if somebody decides to cut in.

The concept described in the previous paragraph is known as FIFO, and it is a universal concept that is not just used in computer science. For example, FIFO is used in fields such as accounting.

What is a FIFO Data Structure?

FIFO stands for first in, first out.

Woah that sounds so technical!

Believe me, it is a ridiculously easy concept to grasp and understand.

FIFO just means that the items are popped off the queue in the order that it goes in. The first element that was entered is the first to leave the queue.

Conversely, the latest element that was added to the queue is the last element to leave the queue. If more items are added, those items become the last to leave.

A FIFO data structure is one in which data is accessed and removed in the order in which it was inserted.

The opposite of FIFO is LIFO, which stands for last in, first out.

A prime example of a data structure that utilizes the LIFO approach is the stack data structure.

If you still don’t get how the queue data structure works and what FIFO is, we will be examining a real-world example in the next section.

Real World Example of the Queue Data Structure

Imagine that you are standing in line to catch a bus, tram, or watch a movie.

the queue data structure is like waiting in line

You are currently the fifth person in line. This means you will be able to get on after the first four people in front of you have boarded.

You will have to wait until the person in front of you has gotten o.

Likewise, the person in front of you, must also wait until the person in front of them has proceeded to board.

This is where you get the phrase

Sir, please wait in the queue until it is your turn!

Items in the queue are dequeued in the order that they enter the queue. Fair right? Nobody like people that cut in, especially when they had to wait a long time to get close to the front of the line.

Queue Data Structure Practical Use Cases in Programming

Now that we conceptually understand the queue data structure, let us take a look at some use cases in programming.

The queue is used to handle a job or data in the order in which they occur.

For example, let’s say we are gathering data from a device that is sending us data packets consistently via the TCP/IP protocol. And all of a sudden, the connection is becomes unstable for 10 seconds. The data that has not been sent due to connection loss can be stored in a queue so that when the connection is established after 10 seconds, it shoots the packet in the order of occurrence and not in some random order. That way, the timestamp for each packet of data will be in chronological order.

Other examples where the queue data structure would be ideal include

  • Job scheduling – We want to execute each job in the order in which they occur.
  • Network handling – We want to serve the users in the order in which they access the server. E.g. Users waiting in line for tech support on a web hosting site such as bluehost.com

Queue is an Abstract Data Type

The queue is an abstract data type, meaning that it is a data type that is defined by its behaviors.

I have already explained what an abstract data type is multiple times, so if you want to know what it is, I recommend looking it up before proceeding.

The bottom line is this.

As long as our implementation adheres semantically to the definition of the queue data structure, we are free to implement it howsoever we wish.

Queue Variations

Apart from the basic queue implementation, there are also variations and they are

  • Deque (double-ended queue). Not to be confused with the dequeue operation.
  • Circular queue.

In double ended queues, we can insert and delete from the front and the back. In other words, you get the best of both the FIFO and LIFO world, but at the cost of additional memory.

In circular queues, the first element is connected to the last element to make that circular shape.

I smell pointers …

By now, hopefully, it is making sense to you that implementing the queue data structure using linked lists might be more appropriate.

Doing the queue array implementation, however, will work those muscles out and really make sure that the queue concept sticks to you like super glue.

Don’t worry. In a future post, we will be implementing the queue data structure using linked lists.

How to Implement the Queue Data Structure

There are multiple ways of implementing the queue data structure. In this tutorial, we will be using the two most common methods. We can implement the queue using the

  • Array or the
  • Linked list

as the underlying data structure.

The underlying data structure is simply the data structure that is used to store the variables behind the scene. For example, in the linked list, the underlying data structure will be nodes. Please do note that arrays can also be used as underlying data structure for both the queue and linked list.

In the same way, we can also use the linked list or nodes as the underlying data structure for the queue.

This involves setting the head as the first item of the queue. We are only able to interact with the head. The head only has a pointer to the next node.

For your education, using the linked list as the underlying data structure is recommended. I will mention this many times to drill this into your head, because it it so important.

More often than not, the linked list is the preferred underlying data structure for implementing the queue, because array need to be constantly resized.

If you don’t know what a linked list is, I recommend reading an introduction to the linked list before proceeding.

Why do arrays need to be resized? Because they are static data structures, meaning they are fixed in size upon creation. If the collection becomes too large for the array to hold, we need to create a new array and copy the contents over.

Queue Interface

For us to implement the queue, we need a basic interface. The basic queue should have the following methods.

  • enqueue(T data): Add an item to the end of the queue. Remember, you need to wait in line until it is your turn. No cutting in line okay? 🙂
  • dequeue(): Not to be confused with deque (double-ended queue), dequeue removes the first element from the queue. In certain implementations, the item that was removed is also returned.
  • front(): Get the first element of the queue without removing it.
  • size(): Get the size of the queue.
  • isEmpty(): Returns true if list is empty. Otherwise, return false.

For the sake of being able to view what is in the queue, we will also be implementing a print() method to print out the items inside of the queue.

queue data structure UML class diagram

Queue Array Implementation

As mentioned in a previous section, we will begin investigating how to implement the queue data structure using the array implementation.

We are going to be using our brain, so put on your thinking caps.

In the array implementation, the front index or the reference variable that keeps track of the first item (the first non-null item) of the array.

Because the array is a static data structure, we won’t be able to reduce the size of the array at run time. Instead, we will set the deleted elements to null and increment the front index.

Front Index when Adding items to the Queue

What is the fundamental concept behind a queue? The consumer of the queue API should only be able to interact with the first element in the queue.

Here is the first question:

How do we access items inside of an array?

By index, right? I.e.

// index is a numeric value
itemInArray = array[index];

Let’s connect our train of thoughts.

We access items in the array by its index value. In the queue data structures, users can only interact with the first element in the queue.

Therefore, we need to keep track of the index of the first item in the array.

If you followed and understood the train of thoughts discussed above, this should hopefully make sense to you.

Because we are only able to remove items from the front of the array, we need to keep track of this index.

No, the front index is not always zero.

You will soon find out why.

For now, below is a visual example to illustrate what we discussed in the current section. queue array implementation front index does not change when adding item

Front Index when Removing Items from the Queue

When working on the queue array implementation, it is important to increment the front index.

Because arrays are static data structures, we cannot remove the first item from the array. Rather, we are setting the value to null.

This is under the assumption where arrays are static data structures, unlike the arrays in some sort of dynamic programming language such as JavaScript.

Therefore, the front index will be shifted like this when removing items from the array.

queue array implementation removing items requires front index to be incremented

Queue Data Structure Enqueue Method

Enqueue adds data to the start of the queue data structure. In the queue array implementation, as mentioned in previous sections, we need to keep track of the front index. Sorry for sounding like a broken record, but this is very important and I want you to get this.

To find the index of the last element, we need to add the front index to the size to find out the index of the last element. If you don’t understand this, try wrapping your mind around it and figure out why. If after a while, you are still stuck, read on. It will soon be unveiled to you.

Because array indexes are zero-based, we need to subtract one from the result of the previous operation.

Zero-based simply means that instead of counting from 1,2,3 like most humans do, we start counting from zero.

Therefore, array indexes will start from zero, like this.

0, 1, 2, 3, 4 ...

Look at the example below.

create new queue here;

---------------

queue.enqueue(1);
// queue with initSize of 7.
// [1, null, null, null, null, null, null];         
// size = 1
// front = 0

---------------

queue.enqueue(2);
// [1, 2, null, null, null, null, null];         
// size = 2
// front = 0

---------------

queue.enqueue(3);
// [1, 2, 3, null, null, null, null];         
// size = 3
// front = 0;

---------------

queue.dequeue();
// [null, 2, 3, null, null, null, null];
// size = 2
// front = 1

---------------

queue.dequeue();
// [null, null, 3, null, null, null, null];
// size = 1
// front = 2

Because the queue data structure is FIFO, we add items to the end of the queue. That way, elements that are added first are the first to leave.

After you have fully grasped how to calculate the last index of the underlying array in the queue array implementation, the rest of the operation is very simple.

start enqueue(data):
    queueArray[size + front - 1] = data;
    front++;
end enqueue;

Queue Data Structure Dequeue Method

I will emphasize this again: the dequeue() method must not be confused with deque, which is a shorthand way of saying double-ended queue. Soon, I will write a tutorial on the double-ended queue.

Because the queue data structure is FIFO, we remove items at the front of the queue.

Why, because the items at the front of the queue have been waiting the longest to get out of this line!

Imagine if you had to wait in line for like an hour and some guy behind you, who only waited 20 minutes gets to check out first, wouldn’t you be pissed?

I sure would!

The dequeue() method removes the first item in the queue.

In the queue array implementation, we keep track of which item is the first item in the queue by its index. If we keep track of the front index meticulously, the removal process is simple.

start dequeue():

    if queue is empty
        // handle exception
    end if;
    
    dataToReturn = queueData[front];
    
    queueData[front] = null;
    
    size--;
    front++;
    
    return dataToReturn;
end dequeue;

After handling the case for when the queue is empty, if we want our dequeue() implementation to also return the value that was deleted, we must set dataToReturn as the value that will be deleted.

Afterwards, we decrease the size index because one element is being removed from the queue. Then we increase the front index.

In case you don’t remember the stuff we went through in the previous section, because arrays are static data structures, in reality, we are setting the value to null. After setting the value to null, we increment the front index so that it now points at the first NON null element in the queue. Like the following.

Queue with elements [10,11,12]

// [10, 11, 12, null, null, null, null];         
// size = 3
// front = 0;

---------------

queue.dequeue();  // returns 10
// [null, 11, 12, null, null, null, null];
// size = 2
// front = 1

---------------

In the example above, when we dequeue, we are incrementing the front index so that its value increases from zero to one.

It now points at the first item in the queue, which is 11.

Notice that the size is decremented, and that the previous first element of the queue (10) is now set to null.

Queue Data Structure Front Method

By now, you should understand how to get the first item of the queue, and that is what front does.

Please note that the front() method does not dequeue the item from the queue. All we need to do is handle the case where the queue is empty.

Afterwards, just simply return the item that is located at the front index of the underlying array.

begin front():
    if isEmpty():
        // handle error. Returning null is an option.
    end if;
    return queueData[front];
end front;

Growing the Queue Size Dynamically

One of the downsides of the queue array implementation is the fact that arrays are not dynamic data structures.

Once the underlying array reaches full capacity, we need to increase the size of the array.

This takes O(N) time and space complexity, because we need the old container to hold the existing data. Afterwards, we need to transfer the existing data into the new container and set the underlying array to the larger queue that was created.

If we were implementing the queue using linked list, this would not be a problem.

After each enqueue() operation, we should check the queue to see if we need to resize the array.

But how do we check to see if the array is full?

Remember that the queue data structure operates under strict assumptions.

  1. Data is added only to the end of the queue.
  2. Data is only accessed/removed from the front of the queue.

Therefore, it is safe to assume that the list is full when

queueData[initSize - 1] != null;

Where initSize is the size of underlying queue array.

Now that we know how to check for a full queue, let’s take a look at the actual resizing operation.

Did I mention to you that with the check above, the queue can potentially not be full?

This can occur in the following case

[null, null, null, 4, 5, 6, 7, 8, 9, 10]

Technically, the last element is not null. But somewhere, we dequeued three elements in total.

An actual full list will be a list with no null values.

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Case One: Queue is not full

When the queue is not full, regardless of whether we increase the size of the list, we need to place all the items towards the front of the list.

In another word, we should make the following transition.

Queue with elements [10,11,12]

// [10, 11, 12, null, null, null, null];         
// size = 3
// front = 0;

---------------

queue.dequeue();  // returns 10
// [null, 11, 12, null, null, null, null];
// size = 2
// front = 1

---------------

On each iteration, we are performing the following swap.

queue array implementation shuffling to place null values towards the back

In another word, start swapping items from the start index.

Now this part is tricky:

When do we stop iterating through the array?

It might be easy to assume that we iterate until the index is equal to the size of the array. And a fair assumption that is. However, this is not the correct approach.

Let’s look at a simple example.

[null, null, null, 4, 5, 6, 7, 8, 9, null]

What is the size of this queue? It is six, because we have six non-null elements. front is equal to three.

If we iterate up until the index equals size, we will end up with the following result.

[4, 5, 6, null, null, null, 7, 8, 9, null]

So what is the answer?

The answer is to iterate through all the non-null values.

How do we obtain the index of the item right after the last null-item?

Simple: front + size

In the example above, that would be 3 +6 = 9.

So therefore, we iterate through items between the index values of 3 and 8, which are

[4, 5, 6, 7, 8, 9]

Afterwards, we need to set the front index to zero.

The code to do the reshuffling is straightforward, but for the sake of completeness, let’s walk through the logic below.

if size is less than initSize:
    index = 0;
    // set i to equal the first non-null item of the array.
    frontIndex = front;
    endIndex = size + front;
    
    while frontIndex is less than endIndex:
        queueData[index] = queueData[i];
        queueData[frontIndex] = null;
    
        frontIndex++;
        index++;
    end while;
end if;

We will continue to perform the swap until we reach the end of the list and have the following result.

[4, 5, 6, 7, 8, null, null, null]

If you are having difficulty visualizing or understanding the swap process, I recommend coding the result or taking the code from GitHub and running it through a debugger. Alternatively, try writing down the state of the array on each step of the iteration down on a piece of paper.

Case Two: Queue is full

When the queue is full, we need to increase the size of the array. This is the reason why the queue array implementation is not the best approach. In my opinion, implementing the queue using the linked list is much more efficient. We will be covering the linked list implementation in the next tutorial.

How do we determine whether the queue is full?

If the underlying array does not contain null values, the queue is full.

By comparing the size of the array with the initialized size (initSize). If the size is equal to or greater than the initialized size (initSize) of the array, it is an indicator that the array is going to overflow. Therefore, we need to resize the array.

Afterwards, it is just simply a matter of creating a new array with a greater size. For the sake of clarity, my implementation simply doubles the size on each resize.

After creating the array, we just need to insert all the values into the new array.

This means we don’t have to figure out the range by adding front index value to the size. We just need to iterate for all values less than index value of the initialized size (initSize).

if size of array is greater than or equal to initSize:
    // Set initial size of array to double the current value
    initSize *= 2
    // copy elements into the new array.
    index = 0;
    array = array of size initSize;
    i = front;
    lastIndex = size + front;
    // Iterate through all non-null values
    while i is less than lastIndex:
        arr[index] = queueData[i];
    index++;
    // Lastly replace existing queue data
    // with newly created array
    queueData = arr;
end if;

Conclusion

We have gone through all the basic operations of the queue data structure.

Please note that the implementation process that we discussed above is simply one way of implementing the queue data structure.

Now that you have implemented the queue data structure on your own, you should have a solid understanding how it works.

After the queue array implementation, I recommend implementing the queue using the linked list as the underlying data structure.

This should come much more naturally now that we are starting to understand the fundamentals.

In the upcoming post, I will show you how to implement the queue using the linked list. Afterward, we will look at the double ended queue.

Taking time to master the fundamentals is the shortcut to developing a solid understanding of data structures.

Although this might seem painful and unnecessary at first, trust me when I say that we are going somewhere!

In time, you will reap a harvest, that will put you way ahead of those that decided to take a “shortcut” and stunt their growth by skipping ahead.

Source Code

The queue array implementation source code is available on GitHub in the following languages

Once again, if the content helped you, please share this post so that other people can benefit from reading.

Thank you for reading!

If there is anything else I can do to improve the quality of this post, please leave a comment and let me know.

Take care and happy coding!

– Jay

About the Author Jay

I am a programmer currently living in Seoul, South Korea. I created this blog as an outlet to express what I know / have been learning in text form for retaining knowledge and also to hopefully help the wider community. I am passionate about data structures and algorithms. The back-end and databases is where my heart is at.

follow me on:
16 Shares