Queues in Java & Python

Copy Link LinkedIn Message Facebook Email X

Imagine you are heading downtown and decide to take the bus. You walk to the bus stop, where there are people already waiting. Where do you stand? If people arrive after you do, where do they stand?

Now, imagine the bus arrives, and people begin getting on the bus. Who gets on first?

Normally, when you get to the bus stop, you stand at the end of the line. People who arrive after you stand behind you.

When the bus arrives, the first person in line gets on the bus first, followed by the next person, and so on, until everyone is on the bus.

What is a Queue

In computer science, a queue is an abstract data structure that mimics a line of people at a bus stop. New data (for example, a new person waiting for the bus) enters the queue at the end. Conversely, you remove data from the queue (for example, people boarding the bus) from the front of the queue in the order of arrival.

This type of behavior is called FIFO, which stands for "First In, First Out". As with LIFO structures, this reflects how the structure works -- the first data item added to the queue is also the first item removed.

Why use a Queue

Queues are used to store and retrieve data in a specific order. They are often used to manage incoming requests from the network or from other programs -- requests are added to a queue as they arrive and removed from the queue when there are resources to handle them.

Use Cases for a Queue

Queues are often used by network applications to manage incoming requests. The random and sometimes chaotic nature of network traffic means programs need some way to respond to requests in an organized manner. Web browsers and API handlers use queues to store incoming data requests as they arrive and dispatch them to handlers when resources are available.

Queues are also used to manage communication between your programs and your operating system. When you read or write data to a file on disk, the operating system adds those requests to a queue and often immediately returns to your program. Those file I/O requests are processed and removed from the queue when it has the resources to do so. This is why, if you insert a USB key into your machine and copy files to it, you should never just pull the key out. The operating system may still have data to write stored in the queue.

Benefits of a Queue

Without queues, the modern network infrastructure would be impossible. Queues give web browsers and other network applications a way to manage and respond to random incoming requests in a controlled manner.

Queues also play a key role in gaming applications. During the game loop, keyboard, mouse, and game controller input is received from one or more input queues. This input is used to update the state of the game, which is then used to redraw game objects on the screen. The loop then repeats by receiving more input from the queue.

Queue Implementation

As with the stack, a queue has terminology associated with it:

• Each queue has a front and an end.
• Adding data to the queue is called enqueuing the data. Data is enqueued at the end of the queue.
• Removing data from the queue is called dequeuing the data. Data is dequeued from the front of the queue.

It is important to note that data is added and removed from opposite ends of the queue. This means that both the front and end of the queues can change. This will be key as you learn how to implement a queue.

Queues are abstract data structures and are built using other structures. As with stacks, you can use arrays or linked lists as the basis for a queue.

Java Queue Implementation with Linked Lists

Using a linked list as the basis for a queue means you can add as much data to a queue as you want and rely on the linked list methods to perform the proper checks as you add and remove data.

Since queue operations occur at both ends of the underlying data structure, you need to define whether the head of the list represents the front or end of the queue. For this example, you define the head of the list as the end of the queue (where data is added):

// java
public class QueueLL<T extends Comparable<T>> {
    
    // Used to store the data in the queue
    LinkedList<T> queue;
    
    public QueueLL(){
        if (this.queue == null)
            this.queue = new LinkedList<>();
    }
    
    public void enqueue(T data){
        this.queue.addHead(data);
    }
    
    public T dequeue(){
        return this.queue.removeTail();
    }
}

Adding data to the head of the list occurs at $`O(1)`$, while removing data from the tail occurs at $`O(n)`$. You can improve this by using a double-ended linked list. You also rely on the linked list to ensure valid references, although you can add your own checks for empty queues.

Python Queue Implementation with Linked Lists

As with stacks, you use existing list methods .append() and .pop() to add and remove data from the queue. However, since this queue implementation removes data from the front of the list, you use self.__queue.pop(0) to specify which item to remove. You may also want to add a check for an empty queue to avoid an IndexError exception.

# python
class Queue:

    def __init(self, data=None):
        self.__queue = []
        if data:
            self.__queue.append(data)

    def enqueue(self,data):
        self.__queue.append(data)

    def dequeue(self):
        return self.__queue.pop(0)

Java Queue Implementation with Arrays

In contrast, an array-based queue implementation is much more complex than either the linked list queue or the array-based stack. Since queues operate on both ends of the structure, you need to track both the front and end of the queue using int indexes. There is an added complication you will see as you dig into the code:

// java
public class QueueArray<T extends Comparable<T>> {

    // Used to store the data in the queue
    T[] queue;

    // Where is the front and end of the queue?
    int front, end;

    // How many items are in the queue?
    int count;

    // Create a new queue with a given size
    public QueueArray(int size){
        this.queue = (T[]) new Comparable[size];
        this.front = 0;
        this.end = 0;
        this.count = 0;
    }

    // Create a new queue with a default size
    public QueueArray(){
        this.queue = (T[]) new Comparable[10];
        this.front = 0;
        this.end = 0;
        this.count = 0;
    }

    public void enqueue(T data) throws Exception {
        if (this.count == this.queue.length){
            throw new Exception("Queue overflow");
        } else {
            this.queue[this.end++] = data;
            this.count += 1;
            if (this.end > this.queue.length){
                this.end = 0;
            }
        }
    }

    public T dequeue() throws Exception {
        T returnData;
        if (this.count == 0){
            throw new Exception("Queue underflow");
        } else {
            returnData = this.queue[this.front++];
            this.count -= 1;
            if (this.front > this.queue.length){
                this.front = 0;
            }
        }
        return returnData;
    }
}

In addition to the front and end of the queue, you also track how many items are in the queue in count. Why? Here's an example of QueueArray used in a program:

// java
QueueArray<Integer> myQueue = new QueueArray<Integer>(10);

// Add seven items to the queue
for (int i=0; i<7; i++)
	myQueue.enqueue(i);

// Removed five items from the queue
for (int j=0; j<5; j++)
	System.out.println(myQueue.dequeue());

// Add four more items to the queue
for (int k=0; k<4; k++)
	myQueue.enqueue(k);

After declaring a new QueueArray object to hold Integer values, you run three loops:

• The first loop adds seven items to the queue.
• The second loop removes five items from the queue, leaving two behind.
• The last loop adds four items to the queue for a total of six.

Since the QueueArray holds ten items, this should be fine. But what happens to both front and end indices during these operations:

• Both front and end start as 0.
• During the first loop, end increments seven times, so it is now 7.
• During the second loop, front increments five times, so it is now 5.
• During the third loop, end increments four more times, which would normally be 11.

The last operation would mean end will no longer be a valid index, even though there are only six items in the queue. If you remove all six of those items, then front would also be incremented to 11, which is also invalid, even though there is nothing in the queue.

The solution is a technique called a circular array, which is also called a circular buffer, a cyclic buffer, or a ring buffer. In our case, a buffer and an array are the same thing. Source: Wikipedia

In a circular array, whenever the index gets to the end of the array, it wraps around back to the beginning. Conceptually, you can think of the array as a circular structure:

If you'd like to continue learning about Queues in Java, check out the following resources in the Java 301 course:

• Queues in Java
• Video: Java Queues
• Custom Queue implementation in Java

If you'd like to continue learning about Queues in Python, check out the following resource in the Python 301 course:

• Python Queue & Python Stack

This means that you check each index as it increments -- when it becomes larger than the size of the array, you set it equal to zero so it wraps to the beginning again.

This also means that, unlike a stack, you can't use the front and end indices to tell you when the queue is full -- you need to use a separate count variable to track how much data is in the queue. Each time data is added to or removed from the queue, you increment or decrement count accordingly. Before adding or removing data, you ensure count is valid to make sure the operation is successful.

Now that you've seen some basic implementation details, what are these structures used for?

Uses for Queues

Queues are used every time you type or move your mouse. Each time you type on your keyboard, you create an event, which is added to a queue of incoming events. These events also include things like mouse movements, mouse clicks, timers expiring, incoming emails, video call requests, network messages, and other things.

Each of these events is placed in a queue and removed by a program that knows how to handle each one. For example, an incoming email may generate a notification which you can respond to or ignore. Keyboard and mouse input are handled by the currently active program.

You'll also use queues for our own purposes later.

Summary: Queues

Queues allow you to store data in a specific order and then retrieve it in the same order. This First In First Out characteristic makes queues ideal for use in web servers to handle incoming requests and programs that need to respond to random and sometimes chaotic user input.