It is Saturday October 12, 2019 in the Twin Cities of Minneapolis and St. Paul and we are receiving the first snowfall of the season. Seems like a couple days ago the temperature dropped 50 degrees F in a single day in Colorado producing a big snow storm. We are getting the remnants of it.
I took some days off and traveled with friends and family to Europe. We visited Rome, Naples, Sicily, Bruges and Amsterdam. The temperatures in Italy were in the 80s, while the weather in Belgium and the Netherlands was in the 40s and rainy. We saw, ate and had a great time. That said; it is good to be back home.
We picked up some souvenirs and chocolates. We have a relatively fancy espresso coffee maker at home. We purchased it several years ago. It makes great coffee. It also grinds the beans. Given that my parents were born in Italy I used a traditional espresso machine when I was growing up. We had to get one on this trip.
The new espresso machine needs coffee to be ground. We had to order a grinder for such purpose. The grinder was ordered from Amazon when we got back. It was delivered yesterday evening.
The task at hand is to implement a set of operations on a circular queue implemented with a single linked list. It does not seem to be something too practical behind showing ones understanding of linked lists and circular queues.
The top diagram illustrates a single link queue. It implements a First In First Out (FIFO) data structure. It is important to remember that to be FIFO implies that adding elements (enqueue) must be done at the tail of the queue.
The middle diagram illustrates a queue implemented with nodes that have a value and a pointer to the next element. The head points to the first element inserted in the queue which will be the first being removed (dequeue) and the tail points to the last element in the queue which was the one that was inserted (enqueue) last.
The bottom diagram illustrates a circular queue. I did not display the values of the pointers.
We have been requested to implement the following methods and data structures to support the circular queue:
enqueue()
dequeue()
display()
peek()
After I was done with the whiteboard and was implementing the code and the testing scaffold, I added the isEmpty() method.
When we start we have the head and tail pointing to null to indicate the circular queue is empty.
We start with the implementation of the enqueue() method. I tested each method using the diagram on the left middle side of the white board.
We first allocate a node for the value to be inserted. We then test if the queue is empty. Inserting an element in an empty queue seems to be slightly different than when inserting a node in a non-empty queue.
We then move to the display() method. We check if the queue is empty and return a blank string. For efficiency we then instantiate a StringBuilder object. We then set a pointer p used to traverse the queue.
The loop is used to append (I used add by mistake. It is difficult to remember the methods of all classes especially when one uses different programming languages on a daily base) the value of the current node to the string builder object. We then point to the next element in the circular queue. The loop ends when we reach the head of the queue.
Finally we return the string representation of the StringBuilder object.
The peek() method is quite simple. If the head of the queue is null we return a blank string; otherwise we return the string associated with the value of the head element.
The dequeue() method starts by checking if the queue is empty. If so, we return an empty string. We set a pointer to the head of the queue (I missed declaring the pointer h).
If the head is different than the tail the queue has more than one element. We update the head and set the tail accordingly. If the queue has one element (we had already checked for an empty queue) we set the head and the tail to be null to indicate this condition. Finally we return the string value of the head element which was removed from the queue.
/*
* Test scaffolding.
*/
public static void main(String[] args) {
// **** instantiate a circular queue ****
CircularQ cq = new CircularQ();
// **** enqueue ****
System.out.println("main <<< enqueue: " + cq.enqueue(1));
System.out.println("main <<< enqueue: " + cq.enqueue(2));
System.out.println("main <<< enqueue: " + cq.enqueue(3));
System.out.println("main <<< enqueue: " + cq.enqueue(4));
System.out.println();
// **** peek and dequeue elements from the circular queue ****
for (int i = 0; i < 5; i++) {
// **** display the circular queue ****
System.out.println("main <<< display: " + cq.display());
// **** check if circular queue is empty ****
System.out.println("main <<< isempty: " + cq.isempty());
// **** peek head of queue ****
System.out.println("main <<< peek: " + cq.peek());
// **** dequeue head of queue ****
System.out.println("main <<< dequeue: " + cq.dequeue());
// ???? ????
System.out.println();
}
}
We start by instantiating a circular queue. We then insert for values. We could have done this in a loop. As we insert a value we display it.
We then enter a loop and cycle five times. Note that we only inserted four elements into the queue. We are doing this to make sure that the different methods behave properly when the queue is empty.
In the loop we display the contents of the queue, check if the queue is empty (this method was not required but I decided to implement it. We could have looped until the queue became empty but I just called it to test its operation.
Next we peek to display the head of the queue. Finally we remove the element at the head of the queue. The peek value should match the element removed from the queue. We just have a visual indication. We could have verified the actual values.
main <<< enqueue: 1 main <<< enqueue: 2 main <<< enqueue: 3 main <<< enqueue: 4 main <<< display: 1, 2, 3, 4 main <<< isempty: false main <<< peek: 1 main <<< dequeue: 1 main <<< display: 2, 3, 4 main <<< isempty: false main <<< peek: 2 main <<< dequeue: 2 main <<< display: 3, 4 main <<< isempty: false main <<< peek: 3 main <<< dequeue: 3 main <<< display: 4 main <<< isempty: false main <<< peek: 4 main <<< dequeue: 4 main <<< display: main <<< isempty: true main <<< peek: main <<< dequeue:
The execution of the code seems to match our expectations. Node that the display() method does not display a ‘,’ after the last element has been displayed. We could just have displayed the ‘,’ but this way our solution looks more polished.
/*
* Queue node.
*/
static class Node {
// **** members ****
int data;
Node next;
// **** constructor ****
public Node(int data) {
this.data = data;
next = null;
}
}
The Node class is used to implement the node elements in the queue. It contains an integer and a next field.
The only method we have implemented is the constructor.
/*
* Circular queue.
*/
static class CircularQ {
// **** members ****
Node head;
Node tail;
// **** constructor ****
public CircularQ() {
head = null;
tail = null;
}
}
This class implements the circular queue. We have a head and a tail pointer. The constructor initializes both pointers to null. The other methods have been omitted. We will now cover each one separately.
// **** enqueue ****
public int enqueue(int data) {
// **** allocate node for data ****
Node node = new Node(data);
// **** check for an empty circular queue ****
if ((head == null) &&
(tail == null)) {
head = node;
// tail = node;
// tail.next = head;
}
// **** circular queue NOT empty ****
else {
tail.next = node;
// tail = node;
// tail.next = head;
}
// **** ****
tail = node;
tail.next = head;
// **** ****
return node.data;
}
This method is used to insert or enter an element into the circular queue. We allocate the Node and perform some checks. Inserting an element into an empty queue is slightly different than inserting an element into a non-empty queue.
I commented some lines that duplicated. When using a whiteboard it is difficult to optimize code. It involves a lot of erasing and rewriting.
You may node that we return the value of the inserted node. This was done to simplify displaying the value just inserted.
// **** display ****
public String display() {
// **** check if circular queue is empty ****
if (head == null)
return "";
// **** ****
StringBuilder sb = new StringBuilder();
// **** traverse the circular queue ****
Node p = head;
do {
// **** append the data to the string ****
if (p.next != head)
sb.append(p.data + ", ");
else
sb.append(p.data);
// **** move to the next element in the circular queue ****
p = p.next;
} while (p != head);
// **** return string with data ****
return sb.toString();
}
The display method checks if the circular queue is empty. If so it returns a blank string.
We instantiate a StringBuilder object and then get ready to traverse the queue using the Node pointer.
In the loop we add the value of the current node and then point to the next node in the circular queue. When we reach the head of the queue we exit the loop.
Finally we return the string value of the StringBuilder object.
// **** peek ****
public String peek() {
// **** check if circular queue is empty ****
if (head == null)
return "";
else
return String.valueOf(head.data);
}
The peek() method display the head element in the circular queue. If the head is null (empty queue) we return an empty string. Otherwise we return a string with the value of the head element.
// **** dequeue ****
public String dequeue() {
// **** check if queue is empty ****
if (head == null)
return "";
// **** ****
Node h = head;
// **** check if queue has more than one node ****
if (head != tail) {
head = head.next;
tail.next = head;
}
// **** queue has one node only ****
else {
head = null;
tail = null;
}
// **** ****
return String.valueOf(h.data);
}
The dequeue() method is used to remove the element at the head of the circular queue. If the head is null, the queue is empty so we return an empty string.
We then set the h variable to point to the head element in the queue. This is done because we will be updating the head pointer before returning from the method.
If the queue has more than one node, we update the values appropriately. The same occurs when the queue is empty. We then return the value (as a string) of the node we just removed from the head of the circular queue.
// **** isempty ****
public Boolean isempty() {
return head == null;
}
This additional method is used to test if the circular queue is empty. We just return the result of testing if the head pointer is null.
The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this or any other post in this blog, or if you would like me to help with any phase in the SDLC (Software Development Life Cycle) of a product or service, please do not hesitate and leave me a note below. Requests for help will remain private.
Keep on reading and experimenting. It is the best way to learn and refresh your knowledge!
John
Follow me on Twitter: @john_canessa