Introduction
- This series is going to be dedicated to learning and understanding data structures and algorithms in Java. All the information I am using is coming from the book,
Data Structures and Algorithms in Java by Michael T. Goodrich and Roberto Tamassiaand the California State Polytechnic University course, which is free and can be found HERE,shout out professor Tang. Please do not buy the book it is expensive and can be found online for MUCH cheaper.
YouTube version:
- YouTube version of this blog post can be found HERE
GitHub code
- GitHub for the code can be found HERE
Queues
- Another fundamental data structure is the
Queue, like a stack a queue is considered an abstract data type. The big difference between a stack and a queue is a queue is a collection of objects that are inserted and deleted according to thefirst-in, first-out(FIFO) principle. This means that elements can be inserted at any time, but only the element that has been in the queue the longest can be removed. We usually say that elements enter the queue from thebackand are removed from thefront. A common mental model to have when working with queues is a line up at the grocery store.
Methods
- The queue supports a total of 5 total methods:
1) enqueue(e) : Adds element e to the back of the queue
2) dequeue() : removes and returns the first element from the queue(or null if the queue is empty)
3 first() : returns the first element of the queue.
4) size() : returns the number of elements in the queue
5) isEmpty() : returns the number of elements in the queue
- Since a queue is an abstract data type we need to formalize these methods and we will do so with a Java interface.
public interface Queue <E>{
int size();
boolean isEmpty();
E first();
void enqueue(E e);
E dequeue();
}
Notice that with this interface we are using generics which allows more flexibility when defining types.
For this queue data structure lets assume that elements are inserted into a array and the first element is at index 0, the second is at index 1 and so on. Which seems fairly obvious, however, things become a little less clear if we stop to think about how the
dequeue()method would work. As we remove elements from the front of the queue, we have to keep updating the front, but how do we do the updating? The first solution that comes to mind is to remove whatever is in index 0 and then have a loop shift all other elements to the correct position. This solution does work but it runs inO(N)time and remember when dealing with data structure operations we want our method implementations to run inO(1)orO(logN)time. So, to optimize our run time and have it run inO(1)we will implement a circular array.
Using Circular Arrays
- Basically a circular array is just a normal array but as we reach the end the array our index will wrap back around to the front of the array. To create a circular array all we have to do is implement one simple equation:
f= (f+1)%N
- Where
fis used to represent the front of the queue andNis the length of the array. If you are unfamiliar with%it is called themodulo operatorand will return the remainder of two operators. For example, if we have10 % 10the answer will be 0 and if we have11 % 10the answer will be 1. We will talk more about this equation later on.
Implementing the queue
- To implement and create a queue we will follow 4 easy steps:
1) create the class and instance variables
2) create the constructors
3) implement the interfaces
4) implement the methods
1) Create the class and instance variables
- Our class will have 4 instance variables:
1) data : used to hold a reference to the array used for data storage
2) f : used to hold a reference to the front of the queue
3) size : used to determine how many elements are in our queue
4) CAPACITY : used as a default capacity value for our array. Technically, it this is a class variable and not an instance variable.
public class ArrayQueue <E>{
private E[] data;
private int f;
private int size = 0;
private static final int CAPACITY = 1000;
}
- As you can see with
CAPACITYthe static modifier makes it a class variable and not an instance variable.
2) Create the constructors
- Now we will create the constructors, we will create two constructors to give our class a little bit of flexibility when it comes to array size.
public class ArrayQueue <E>{
//...
public ArrayQueue(){
this(CAPACITY);
}
public ArrayQueue(int capacity){
data = (E[]) new Object[capacity];
}
}
- If the line
(E[]) new Object[capacity];confuses you read THIS stack overflow for clarification. But essentially we have to do our little(E[]) new Object[capacity];hack because oftype erasuresand that fact we can not directly instantiate a type parameter.
3) implement the interfaces
- This step is very straight forward, all we do is implement the interface that we created earlier.
public class ArrayQueue <E> implements Queue<E> {
@Override
public int size() {
return 0;
}
@Override
public boolean isEmpty() {
return false;
}
@Override
public E first() {
return null;
}
@Override
public void push(E e) {
}
@Override
public E pop() {
return null;
}
}
4) Implement the methods
- The first 3 methods,
size(),isEmpty()andfirst()are the easiest to implement:
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public E first() {
if(isEmpty()) return null;
return data[f];
}
- The only method that might be slightly confusing is
first()and all we have to remember is thatfrepresents the front of the queue and will be shifting as we remove elements from the queue.
enqueue(E e)
- This is the first method that needs a little explaining:
@Override
public void enqueue(E e) throws IllegalStateException{
if(size == data.length) throw new IllegalStateException("QUEUE IS FULL");
int back= (f +size) % data.length;
data[back] = e;
size++;
}
The goal of the enqueue method is to add a new element to the back of the queue. We need to determine the proper index at which to place the new element. Although, we do not explicitly maintain an reference variable for the back of the queue(like most other queue implementations do), we can compute the next opening with this equation:
int back= (f +size) % data.length;Then we simply assign the
eelement to its proper indexdata[back] = e;and increase the size of the queuesize++;
dequeue()
- When this method is called the current value of
fdesignates the index of the value that we want to remove and return. We keep a local reference to the element that will be returned,answer, before setting its cell of the array back to null. Then the index f is updated to reflect the removal of the first element, and the presumed promotion of the second element to become the new first. In most cases we would just increment the index by one, but because of the possibility of a wrap around configuration (circular array) we will rely on modular arithmetic the equation:f = (f +1) % data.length;
@Override
public E dequeue() {
if(isEmpty()) return null;
E answer = data[f];
f = (f +1) % data.length;
size--;
return answer;
}
Analyzing the efficiency of an array based queue
In our array based queue implementation each of the methods execute a fixed number of operations, thus making each method run in
O(1)constant time(Which is what we want for data structure operations).The space usage is
O(N), where N is the size of the array, determined at the time the queue is created and independent from from the number of elements actually in the queue.
Conclusion
- Thank you for taking the time out of your day to read this blog post of mine. If you have any questions or concerns please comment below or reach out to me on Twitter.
Top comments (0)