Queues

While the Java standard library provides a Queue interface, the language designers prioritized compatibility with the Collection interface. As a result, the API is poluted with several methods that should not be part of a queue interface. Here we will introduce our own simplified interface that includes only the relevant methods.

Queues

Queues

The queue interface represents a queue of items. We are limited to adding items to the back of the queue and removing items from the front of the queue. In order to access the last item in the queue, we would first need to remove all of the items the entered the queue before it.

The PureQueue interface has four methods:

• Object peek() — returns the item at the front of the queue without making any changes to the queue.
• Object poll() — removes the item at the front of the queue and returns it
• void offer(Object item) — adds an item to the back of the queue
• boolean isEmpty() — returns true if there are no items in the queue

public interface PureQueue {

Object peek();

Object poll();

void offer(Object item);

boolean isEmpty();

}

Interactive Walkthrough

Click on an icon below or the play button above to start!

Adapting an ArrayList to implement the PureQueue interface can be done, but the performance of either the offer() or poll() method would be O(n) since adding to or removing from the front of an ArrayList requires shifting all of the other elements in the list.

CircularQueues

CircularQueues

A circular queue is an implementation of the queue interface that makes use of an array to store the elements. It has a fixed capacity that is allocated when the queue is created. As items are added to the queue, the index indicating the location of the back of the queue is updated. As items are removed from the queue, the index indicating the location of the front of the queue is updated. Note: it is possible to implement a circular queue using a list of nodes that are created when the queue is instantiated. The last node in the list just points to the first node.

public interface PureQueue {

Object peek();

Object poll();

boolean offer(Object item);

boolean isEmpty();

}

Interactive Walkthrough

Click on an icon below or the play button above to start!

Solve: CircularQueue Offer

Created By: Chris Taylor

/ Version: 2023.8.0

Implement the CircularQueue class that extends the AbstractCircularQueue class and implement the boolean offer(Object item) method.

The following attributes are available from the AbstractCircularQueue class:

• Object[] items - It's length determines the capacity of the queue. You may assume it is not null
• boolean isEmpty - true when queue is empty
• int frontIndex - index to the front of the queue
• int backIndex - index to the back of the queue

WorkingPrevious

More Practice

Need more practice? Head over to the practice page.