Solved

Urgent! Queue using Linked List?

Posted on 2000-04-25
10
1,585 Views
Last Modified: 2013-12-14
Can anyone help me? Please provide me with a full working set of Java code for implementing a queue using linked list. With 2 threads, one to add to the queue and the other to remove from the queue.
0
Comment
Question by:g7677
  • 4
  • 4
  • 2
10 Comments
 
LVL 7

Expert Comment

by:Sasha_Mapa
Comment Utility
homework?
0
 
LVL 19

Accepted Solution

by:
Jim Cakalic earned 200 total points
Comment Utility
Sasha may not like me for this, but I feel obliged to help when someone asks for help. I understand that sometimes a good example can make a difficult concept understandable. However, instead of just giving you a working implementation, how about we break down the problem so you can get a handle on it? I'll provide enough skeleton code to structure the problem but not enough that you won't have to do some work to complete the implementation. Along the way I hope you read my commentary so that you can get an understanding of the concepts present in this problem.

A queue is a data structure that demonstrates First-In First-Out or FIFO behavior. Regardless of how many items are in the queue, they should be removed from the queue in the same relative order as they were added. There are essentially three operations you need in a minimally functional queue: adding an item, removing an item, and determining whether there is anything in the queue.

Java provides the innate ability to parallelize activities by use of threads. Threads are units of execution. Threads appear to execute simultaneously in the performance of their assigned tasks although, on a single CPU system, they will surely execute consecutively. Threads are given control of the cpu one at a time for a predetermined time or until the thread decides to yield. The maximum amount of time a thread is allowed to run before being interrupted is termed a "timeslice". There is no way to know for certain how much a thread might accomplish before it is preemptively interrupted. Therefore, it is important to protect a data structure that could be accessed or modified by multiple threads so that the data structure remains consistent. The way you do this in Java is by synchronizing on an object. Every object has associated with it a monitor. Only one thread can obtain the monitor at any time. Other threads that wish to obtain the monitor are blocked until the thread owning the monitor releases it. The other threads then compete for the monitor with the thread scheduler (part of the JVM) deciding who wins. The easiest way to implement the synchronization behavior is at the method level.

The Java LinkedList class is not synchronized. Synchronization adds some overhead. It used to be a lot but newer JVM implementations and technologies like HotSpot have substantially reduced this penalty. Still, if you don't need synchronization, why pay for it? As a result, the classes in the Java 2 Collections API aren't synchronized. Vector and Hashtable, being legacy implemenations reworked for conformance with the new Collection interfaces, are synchronized. But our solution requires that we use LinkedList. This is also a more appropriate data structure with which to back a Queue than is Vector. Hashtable is completely inappropriate for this problem (you figure out why).

One way to synchronize a LinkedList is with the Collections.synchronizedList() method which adds a 'synchronization wrapper'. For our purposes, though, it really is much easier to just make the methods of our Queue class synchronized to prevent concurrent access or modification to the state of the queue.

Applying these concepts, here is a simple skeleton for our Queue class:

public class Queue {
    private LinkedList list;

    public Queue() {
        // Create a new LinkedList to back this Queue
        list = new LinkedList();
    }
 
    public synchronized void add(Object o) {
        // Use the LinkedList.add(index, Object) method to add this object
        // to the beginning of the list. Since this method is synchronized
        // any thread wanting to perform any other synchronized operation
        // on the object will be blocked until this method completes.
    }

    public synchronized Object remove() {
        // Use the LinkedList.removeLast() method to get the last object
        // from the list. The last object will be the earliest one added
        // to the list.
    }

    public synchronized boolean isEmpty() {
        // use the LinkedList.isEmpty() method to implement
    }
}

Once the implementation is completed as directed in the comments, you will have a thread-safe Queue class. Now you want to have something that reads the queue and something that writes the queue. You want these operations to be performed 'simultaneously', on two separate threads. Threading can be implemented in Java by either of two ways: extend the Thread class and override the run() method or implement Runnable and provide an implemenation for the run() method declared by that interface. Of the two, it is typically preferrable to implement Runnable. Extending Thread doesn't really buy you anything and it eliminates any possibility that your class could extend anything else.

The responsibility of the queue writer is to put things into the queue. You haven't really defined what should be put in the queue, from whence the items come, or the pace at which items should be added to the queue. I'll leave that for you to figure out. Instead, here is a simple skeleton for the class:

public class QueueWriter implements Runnable {
    private Queue queue;
   
    public QueueWriter(Queue destination) {
        queue = destination;
    }

    public void run() {
        // Loop forever adding items (Objects) to the queue using queue.add(Object).
        // When this method completes, the thread will terminate. It may be desirable
        // to pace adding items to the queue. If so, use the Thread.sleep(long) method
        // to pause the thread's activity for a specified number of milliseconds or
        // Thread.yield() to give up processing to other threads. If you use Thread.sleep()
        // you will be required to catch the checked exception InterruptedException.
    }
}

Notice that in the constructor to the class we are providing the new QueueWriter instance with a reference to the Queue object on which it should write. This is an important part of the ability to coordinate the activities of the writer and reader.

The queue reader takes items out of the queue. Of course, to take items from the queue there must be items in the queue. How does the reader know when there are items in the queue? There are several ways this could occur. The Queue object could accept registration of listeners and inform listener objects by means of a callback when items had been added. Or there could be more explicit communication between the QueueWriter and the QueueReader. But these are really outside the scope of this simple problem. Instead, we'll use a rather inefficient polling technique to determine when items can be removed from the queue.

public class QueueReader implements Runnable {
    private Queue queue;

    public QueueReader(Queue source) {
        queue = source;
    }

    public void run() {
        // Loop here checking the queue for available items using queue.isEmpty(). When
        // that method returns false, there are items in the queue to be read. Each item
        // can then be read using queue.remove() which returns an Object. To do anything
        // useful with the Object, you will have to cast it to its appropriate type. For
        // instance, if you put Strings into the queue, you would have to cast the return
        // of queue.remove() to a String before using it. To mitigate the overhead of the
        // polling method used to determine queue item availability, you should consider
        // using Thread.yield() or Thread.sleep(long) when queue.isEmpty() returns true
        // because that is an indication that the reader is getting ahead of the writer.
        // How long to sleep will be an important decision you might experiment with.
        // Remember that when this method ends, the thread acting as the queue reader
        // will terminate.
    }
}

Now we have a Queue data structure, and QueueReader/QueueWriter which can operate on separate threads. What we need now is something to orchestrate the application -- get it kicked off. For lack of a better name, we'll call this the QueueController. What we need first and foremost in QueueController is a main method so that we can supply this as the entry point of our application to the JVM (java.exe). We'll make instances of Queue, QueueReader, and QueueWriter. But there is still only a single thread to our application. To get the reader and writer to operate in parallel, we still need to tell the JVM that we want different threads to be running each executing the run method of one of our classes. The Thread class is the way to do this.

A Thread instance by itself can't do anything -- it's run method is empty. So you could make a new Thread and start it running by saying:
    Thread t = new Thread();
    t.start();

But the thread will stop immediately because the default run method terminates. What we need to do is create a Thread object and give to it an object that implements the Runnable interface. Then when we tell the thread to start, it will call the run method defined by its Runnable object. How convenient that our QueueWriter and QueueReader implement Runnable! In the main method of our QueueController class, we can then say:
    Queue q = new Queue();
    QueueWriter writer = new QueueWriter(q);
    QueueReader reader = new QueueReader(q);
    Thread t1 = new Thread(writer);
    Thread t2 = new Thread(reader);
    t1.start();
    t2.start();

Now we have two threads running in parallel, one writing objects to the queue and one reading objects from the queue. Remember that this is safe because all the methods defined on our Queue class are synchronized. This forces threads who want to operate on the queue object to get in line and perform their jobs one at a time. Here is the skeleton to QueueController:

public class QueueController {
    public static void main(String[] args) {
        // initialize and start threads
    }
}

I said before that we had two threads running in parallel. Actually, we have three. The main() method is itself running on a thread and it starts two others for the reader and writer. If it is your convention to code a System.exit() as the last thing in your main method, you will find that the application stops almost immediately after started ('java QueueController from the command prompt). The reason for this is that System.exit() causes the JVM to stop all the threads and exit -- just as you requested. If you don't code the exit, main will run off the end of the method and return but the two threads you have started will keep the JVM alive. This demonstrates the difference between a daemon thread and a 'foreground' thread. The JVM considers daemon threads as background non-essential tasks. When the only threads left running in the JVM are daemon threads, it will exit. Since the default for new threads is that they are foreground threads, the application stays alive with the reader and writer performing their jobs.
   
Something for you to consider is that there is no way to shut down this application except to stop it using CTRL-C at the command prompt. Not very pretty. How might you change the implementation to permit gracefully stopping the reader and writer, perhaps ensuring that the reader has had a chance to remove everything from the queue before the application exits?

Given the code skeletons and descriptions I have provided, it should be a simple matter to complete the implementation. I hope that I have provided neither too little nor too much assistance. Good luck.

Best regards,
Jim Cakalic
0
 
LVL 7

Expert Comment

by:Sasha_Mapa
Comment Utility
Jim, I don't "don't like you for this"... if I wasn't as lazy as I am, I would have helped him/her without giving a solution too, what I am not sure about is that he/she will appreciate your effort (Please, please prove me wrong, g7677).
Btw, I'm not sure whether g7677 wanted you to use the already implemented LinkedList class... I think he/she needs to write one himself/herself for the assignment.
0
 

Author Comment

by:g7677
Comment Utility
Hi Jim, thanks for the explanation and the code, I would like to try out and understand it. Btw, I'm a programmer in VC++ but taking a course in Java now, but with a short time for this assignment, I had to resort to this. Thanks alot. I really appreciate it. I would give u the points once I test out the program. Thank you.

Sasha, sorrie I can't prove u wrong as I hadn't got time to do it.

I have been grounding myself for the past 1 week without much progress, with another few days to the deadline, I got to turn to someone for help.

0
 

Author Comment

by:g7677
Comment Utility
Sorrie Jim, is LinkedList a class in Java 2. Cos I using JDK 1.1
0
IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

 
LVL 19

Expert Comment

by:Jim Cakalic
Comment Utility
Yes, I used the LinkedList class from Java 2. But one really isn't that hard to implement. Before you do anything else though, go to the code for Queue and remove the line 'import java.util.LinkedList'. This will only get in the way later.

A linked list is implemented is a serious of data structures that have been chained together. The chaining is accomplished by what is commonly termed a node. Each node retains a reference to one or more other nodes in the list as well as a reference to the user data that is stored in the list at that node.

A linked list with nodes that only know the next node in the list can only be traversed in the forward direction. This is commonly termed a singly-linked list because each node has a single reference to another node. An unfortunate side effect of a singly-linked list is that access to the tail of the list can only be accomplished by traversing the list from the first or head node through all the contained nodes until the tail is reached. Not exactly a high performance operation.

A commonly implemented solution to the tail traversal problem is the doubly-linked list, so named because each node has a two references to other list nodes. One reference is to the next node just like the singly-linked list. The other reference is to the node that precedes it in the list. Because each node has a forward and a backward reference, the list can be traversed in either direction. All that is need to optimize the traversal is for the linked list to retain references to both the node that is the head and the node that is the tail. Then, depending on which way will provide the most optimal traversal, the head or tail is used as the starting point.

The list we will use is not circular -- the head node does not know a previous and the tail node does not know a next. When I say a node 'does not know', I mean that the corresponding node reference is null.

Here is how we will define the node for our doubly-linked list. Each node has a reference to the previous node, a reference to the next node, and a reference to a data object. The only way to construct a Node is to supply values for the next, previous, and data references. We must have all three to properly initialize the state of the object.

class Node {
    Node next;
    Node previous;
    Object data;

    Node(Node n, Node p, Object d) {
        next = n;
        previous = p;
        data = d;
    }
}


The LinkedList class itself is very simple. We'll let the compiler define a default constructor. The class has instance variables that give it references to the current head node, the current tail node, and an integer to maintain a count of the number of nodes in the list. Instance variable initialization will cause these variables to have values of null, null, and 0 respectively. Collectively, these indicate that the list is empty when it is first instantiated.

This simple implementation has only three methods. Adding new nodes will always occur at the head. Future enhancement of the class would allow a client to specify where in the list the insertion should occur. Likewise, removal will always occur at the end of the list. Future enhancements would allow for removal of any node by index and perhaps peeking at nodes without actually removing them. There is also no facility for iterating over the list.

public class LinkedList {
    private Node head;
    private Node tail;
    private int len;

    public void add(Object data) {
        // Always add at the beginning of the list. That means the new
        // node will become the head. As such, it will have no previous
        // and its next will be whatever node was occupying the head
        // at the time of the add request.
        Node node = new Node(head, null, data);
        if (head == null) {
            // First node of empty list is also tail.
            tail = node;
        } else {
            // Fix old head node so previous references new head node.
            head.previous = node;
        }
        // Make new node the current head.
        head = node;
        // Increment the node count.
        len++;
    }

    public Object remove() {
        // Always remove from the tail of the list. If there is no
        // tail node, throw an exception.
        if (tail == null)
            throw new java.util.NoSuchElementException();

        // Get object referenced by current tail node so that we
        // will have it to return later.
        Object data = tail.data;
        // New tail becomes the whatever node the current tail considered
        // its previous (or predecessor in the list).
        tail = tail.previous;
        // Decrement the node count.
        len--;
        if (len == 0) {
            // Count is zero so list is now empty.
            head = null;
        }
        return data;
    }

    public int size() {
        return len;
    }

}


There isn't a whole lot more to say about this. There are several dozen places where you could steal more sophisticated LinkedList code easily found by doing a simple web search. Not much more is really necessary. I encourage you to study this closely so that you understand how it works. It isn't particularly hard. Actually, it would be possible to roll this code into Queue if you wanted to be that enterprising. I'm surprised that you have an assignment to write a Queue and haven't written or been provided a working implementation of LinkedList.

If you have a data structures or algorithm book you can find much better explanations and more sophisticated code there. One that looks to be fairly comprehensive is the Mitchell Waite Data Structures and Algorithms in Java. This book was written to be used in an undergraduate first course on the topic. Interestingly, as I look at the table of contents for that book, I notice that Stacks and Queues are addressed in the chapter preceeding LinkedLists. Go figure.

A final note, the Node and LinkedList classes should appear together in a source file named LinkedList.java. Likewise, with the classes I defined in my previous post, each of the public classes should appear in its own source file -- Queue.java, QueueReader.java, QueueWriter.java, and QueueController.java. All told, 5 source files.

Best regards,
Jim Cakalic
0
 

Author Comment

by:g7677
Comment Utility
OK jim, 1 more problem that I have here,
the following line gives an error.

public synchronized Object remove() {

error = missing return statement

How do I solve this?
0
 
LVL 19

Expert Comment

by:Jim Cakalic
Comment Utility
I assume you mean the Queue.remove method? Look carefully. I didn't write all the code. Some of it was left for you. The error is telling you that Queue.remove should be returning an Object according to its declaration but analysis of the code in the method reveals that it is possible for the method to end without an explicit return.

Your task now is to use the comments primarily in the Queue, QueueWriter, and QueueReader methods to complete the implementation. If you just take the code as posted and compile it, assuming no errors like no return statement in a method (actually no statements at all), it still doesn't do anything.

First, implement the Queue add, remove, and isEmpty methods. These are simple when you think about it. Base the implementations on calls to the LinkedList class that I posted. They all turn out to be one-liners because you are delegating to LinkedList.

Next tackle the QueueWriter run method. This will be an infinite loop that adds an object, maybe some constant String?, to the Queue instance.

Then implement the QueueReader run method. This is pretty much like QueueWriter but instead of adding, you will be removing from the Queue instance. First check whether the Queue is empty. If so, sleep for some small amount of time (in milliseconds). If not, remove one object from the Queue and do something with it. Maybe write the String to System.out so that your program shows some activity.

Finally, use the code in my original post to make the QueueController class. This is the class you will give to the java interpreter when you start the program.

I really can't make it any easier without doing it myself. Even allowing for the fact that I have 15 years developing software and a little over 1 year in Java, the number of lines of source that I found I needed to complete this implementation is a total of 3 lines for the 3 Queue methods, about 13 lines for QueueReader.run because I used Thread.sleep and had to catch an exception, and 5 for QueueWriter.run. LinkedList and QueueController are all in my post. I don't think its unreasonable to ask you to do that much of the job.

Please post back with any questions. I'll be more than happy to respond.

Jim
0
 
LVL 19

Expert Comment

by:Jim Cakalic
Comment Utility
Thanks for the points ... but how did you do? Once you've turned in your project I'd be happy to compare completed implementations with you.

Jim
0
 

Author Comment

by:g7677
Comment Utility
Thanks a lot for the help. A little question, any way to implement as an applet and allow user input and than printing out the queue to the applet?
0

Featured Post

Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

Join & Write a Comment

Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
Java functions are among the best things for programmers to work with as Java sites can be very easy to read and prepare. Java especially simplifies many processes in the coding industry as it helps integrate many forms of technology and different d…
This tutorial explains how to use the VisualVM tool for the Java platform application. This video goes into detail on the Threads, Sampler, and Profiler tabs.
The viewer will learn how to synchronize PHP projects with a remote server in NetBeans IDE 8.0 for Windows.

771 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now