Linked List Queue Using Java

You learned in your Java programming class that Java has several Java collection classes that create and manipulate data structures, and you learned in Chapter 6 that the LinkedList class is one of those collection classes.

However, Java does not have a QueueLinkedList class. Therefore, you need to define your own QueueLinkedList class to create a queue that is formed using a linked list. The good news is that the QueueLinkedList class contains only three member methods , and each has a simple definition.

The QueueLinkedList class requires that you define a constructor, an enqueue() member method, and a dequeue() member method. The constructor initializes the linked list, and the enqueue() and dequeue() member methods place data on the queue and remove data from the queue.

The QueueLinkedList class inherits the LinkedList collection class and uses member methods of the LinkedList class to create and manipulate the queue. This simplifies the task of defining member methods for the QueueLinkedList class.

The purpose of the constructor is to create and initialize the linked list. The LinkedList class constructor performs these tasks , which means the QueueLinkedList class constructor needs to call the LinkedList class constructor. This is done by entering the super() statement in the QueueLinkedList constructor definition as shown next :

 public QueueLinkedList()  {  super();  } 

The definition of the enqueue() member method places data at the back of the queue. Fortunately, the LinkedList class defines the addLast () member method, which does just that. Therefore, the enqueue() member method must simply call the addLast() member method to place data at the end of the linked list.

The next code snippet is the definition of the enqueue() member method. The enqueue() member method requires one argument, which is the data that is placed on the queue. We use an integer in this example, but you can use data of any data type.

The data is assigned to a wrapper class and then passed to the addLast() member method. As you ll recall from your Java class, a wrapper class is a class that has member methods defined to manipulate a primitive data type. The Integer() wrapper class is used in this example because we are using an integer. Java also has wrapper classes for other primitive data types.

You must use a wrapper class because the addLast() member method expects to receive an object and not a primitive data type. Therefore, you need to pass the primitive data type (variable x in this example) to the constructor of the wrapper class. The constructor assigns the value of the primitive data type to a data member of the wrapper class.

Notice in the parameter of the addLast() member method that the new operator declares the instance of the wrapper class ( Integer ) and returns a reference to the instance, which is passed to the addLast() member method.

 public void enqueue(int x)  {  addLast(new Integer(x));  } 

The definition of the dequeue() member method is a little more complicated than the other member methods of the QueueLinkedList class. The purpose of the dequeue() member method is to remove data from the front of the queue, so the first task the dequeue() member method performs is to determine if there is any data on the queue. It does this by calling the size () member method of the LinkedList class. This is similar to calling the isEmpty() member method of the QueueLinkedList class in a C++ program.

The size() member method returns a zero if the linked list is empty. The dequeue() member method then returns the zero to the statement that called the dequeue() member method. A nonzero value is returned by the size() member method if there is data on the linked list.

If there is data on the linked list, the dequeue() member method removes the data from the first node on the linked list and assigns it to a variable called temp . The temp variable refers to an instance of the Integer wrapper class. However, the removeFirst() member method returns the value of the node, which is an integer in this example. Therefore, the value returned by the removeFirst() member method must be cast as an instance of the Integer wrapper class ( Integer ) before it is assigned to the temp variable.

You do this because in the next statement, you call the intValue() member method of the Integer wrapper class to retrieve the data member of the wrapper class, which is the value that is returned by the dequeue() member method.

Here is the definition of the dequeue() member method:

 public int dequeue()  {  if(size() == 0)  {   return 0;  }  Integer temp = (Integer)removeFirst();  return temp.intValue();  } 

Now that you understand how to define the QueueLinkedList class, let s use a queue in a Java application. The next piece of code is the complete Java application. It begins with the definition of the QueueLinkedList class, which you learned about in this section.

At the end of the application is the main() method. The first statement in the main() method declares an instance of the QueueLinkedList() class called queue . This is the same statement that is used in the C++ version of this application.

The enqueue() member method is called three times, placing the values 10, 20, and 30 on the queue. The result is a queue that looks like Figure 8-4. The application then removes the first data element from the queue and displays it on the screen by calling the dequeue() member method. The value returned by the dequeue() method is then displayed on the screen by calling the System.out.println() method.

Here s what is displayed on the screen.

10

Next, the application places three more values on the queue by calling the enqueue() member method, which places 40, 50, and 60 on the queue. Figure 8-6 shows the queue.

Figure 8-6: The queue after all values are placed on the queue

The last step in the application is to display each node on the linked list. Here s the output of the following program:

20

30

40

50

60

 import java.util.*; class QueueLinkedList extends LinkedList {  public QueueLinkedList()  {   super();  }  public void enqueue(int x)  {  addLast(new Integer(x));  }  public int dequeue()  {  if(size() == 0)  {   return 0;  }  Integer temp = (Integer)removeFirst();  return temp.intValue();      } } public class QueueLinkedListDemo {  public static void main(String[] args)  {  QueueLinkedList queue = new QueueLinkedList();  queue.enqueue(10);  queue.enqueue(20);  queue.enqueue(30);  System.out.println(queue.dequeue());  queue.enqueue(40);  queue.enqueue(50);  queue.enqueue(60);  while(queue.size() > 0)  {  System.out.println(queue.dequeue());  }  } }