Results 1 to 6 of 6
  1. #1
    jefrazie is offline Member
    Join Date
    Oct 2009
    Posts
    7
    Rep Power
    0

    Default Queue implementation - Enqueue problem

    Hi im having a problem getting my enqueue to work when the queue has a value already in it. In other words, i can only add one value to the queue. Everything else about the queue works (im assuming :)).

    I know i need to make the value that is currently in the rear reference the new node, im just drawing a blank. Any help would be greatly appreciated!

    CODE:
    Java Code:
    import java.util.*;
    
    public class Queue
    {
    	int size = 0;
    	node front, rear = null;
    	
    	public boolean isEmpty()
    	{
    		return (front == null); //If true, front points to null
    	}
    
    	
    	public void enqueue(String input) //Adds a value to the rear of the queue
    	{
    		node n = new node();
    		n.string = input;	//Takes passed in value and stores in variable string of object n
    		n.next = null; 
    		
    		if (isEmpty() == true) 
    			front = n; //If empty, points front to object n
    		else
    		        rear = n; //Points rear to newly created node
    		
                    size++; //Increments when value added to queue
    	}
    		
    	public String dequeue() //Takes value from end of queue, removes it and displays it
    	{	
    		String s = null;
    		node temp; //Creates pointer temp pointed to the removed node
    		
    		if (isEmpty() == true) //Checks to see if queue is empty
    			System.out.println("Queue is empty.");
    		else
    		{
    			temp = front; //Copies the head pointer into temp
    			s = temp.string; //Copies the value in the last node of the queue to s
    			front = temp.next; //Make rear point to next node on the list
    			temp = null; //Delete the object temp, nulling object allows garbage collector to delete object
    			
    			size--; //Decrements ever time a value is dequeued
    		}	
    		return s;		
    	}
    	
    	public String first() //Takes value from front of the queue and displays it without removing it
    	{		
    		String s = null;
    		node temp; //Creates pointer temp 
    		
    		if (isEmpty() == true)
    			System.out.println("Queue is empty.");
    		else
    		{
    			temp = front; //Copies the head pointer into temp
    			s = temp.string; //Copies the value in the top node of the queue to s
    		}
    		
    		return s; //Returns the value in s
    	}
    	
    	public int size() //Method to determine the size of the queue
    	{
    		return size;
    	}
    		
    	public String toString()
    	{
    		System.out.println("The queue from first to last contains: ");
    		
    		for (node n = front; n != null; n = n.next) //Loop to access each node and print string
    		{
    			System.out.println(n.string);
    		}
    		return null;
    	}
    }

  2. #2
    CodesAway's Avatar
    CodesAway is offline Senior Member
    Join Date
    Sep 2009
    Location
    Texas
    Posts
    238
    Rep Power
    6

    Default

    Is there a reason you're not using one of the existing java collections? For example, there is an ArrayDeque class (Java 6) that can act as either a queue or stack.
    CodesAway - codesaway.info
    writing tools that make writing code a little easier

  3. #3
    jefrazie is offline Member
    Join Date
    Oct 2009
    Posts
    7
    Rep Power
    0

    Default

    Our assignment is to create the queue implememtation using a linked list queue or array queue. We have to implement all the methods of the interface. I chose linked list since im a bit weak in that area. Ive found an example in my book:

    Java Code:
    public void enqueue (T element)
    {
    	LinearNode<T> node = new LinearNode<T> (element);
    	if (isEmpty())
    		front = node;
    	else
    		rear.setNext(node);
    	rear = node;
    	count ++;
    }
    Im just not sure where they got the ".setNext" method and how its used. Essentially thats what im trying to figure out.

  4. #4
    CodesAway's Avatar
    CodesAway is offline Senior Member
    Join Date
    Sep 2009
    Location
    Texas
    Posts
    238
    Rep Power
    6

    Default

    Quote Originally Posted by jefrazie View Post
    Our assignment is to create the queue implememtation using a linked list queue or array queue. We have to implement all the methods of the interface. I chose linked list since im a bit weak in that area. Ive found an example in my book:

    Java Code:
    public void enqueue (T element)
    {
    	LinearNode<T> node = new LinearNode<T> (element);
    	if (isEmpty())
    		front = node;
    	else
    		rear.setNext(node);
    	rear = node;
    	count ++;
    }
    Im just not sure where they got the ".setNext" method and how its used. Essentially thats what im trying to figure out.
    Oh, ok. Since rear is a Node, it has a "next" member field. The setNext method is a mutator method, which sets the "next" field to the given node.


    In a linked list, you keep track of the front and rear of the list. The front is where you get values from. After the rear is where you add values. So, when you enqueue a value, if the list is empty, you set the front of the list to the added value. Otherwise, you add the new node at the end of the list (i.e. it's the next node after the current rear). Then, you update the rear of the list, setting it to the added node. Finally, you increase the size by one.


    Edit:
    In your code, you set the rear of the list to the added node. Therefore, there can never be more than two elements. The first one and the rear.
    Last edited by CodesAway; 11-05-2009 at 12:45 AM.
    CodesAway - codesaway.info
    writing tools that make writing code a little easier

  5. #5
    jefrazie is offline Member
    Join Date
    Oct 2009
    Posts
    7
    Rep Power
    0

    Default

    Solved!!!!

    I had an initialization problem. Forgot to initialize the rear of my queue!

    Java Code:
    	public void enqueue(String input) //Adds a value to the rear of the queue
    	{
    		node n = new node();
    		n.string = input;	//Takes passed in value and stores in variable string of object n
    		n.next = null; 
    		
    		if (isEmpty() == true) 
    		{
    			front = n; //If empty, points front to object n
    			[COLOR="Red"]rear = n; //If empty, also point rear to object n[/COLOR]
    		}
    		else	
    		{
    			[COLOR="Red"]rear.next = n; //Points rear to newly created node[/COLOR]
    			rear = n; //Copies n into rear
    		}
    		size++; //Increments when value added to queue
    	}
    Also made the rear pointer point to the next node.

    Thanks for the help!!!

  6. #6
    rdtindsm is offline Member
    Join Date
    Feb 2009
    Posts
    92
    Rep Power
    0

    Default

    Computer Science 195 Lab: Queues

    I would hope that your reference would have much the same information and diagrams.

    A list implements a queue by adding items at the end of the list, and removing them from the other end. Lists normally have a sentinel (likely a null pointer - l) at the end of the list. Null value in the sentinel because it's the end of the list and you don't reference another item. You add an item by changing the sentinel to reference the new item, the new item has the sentinel in the next field of the node.

    In the diagram on the posted web site. Just cover up every thing except the first node and imagine the node is pointing to another. Now let the 'Next' reference point to the next node, and that the next node now has the sentinel. Pretty simple in concept. Would think your rear.setNext(node) simply replaces the sentinel in the last (rear) node with a reference to the newly inserted item. If you were inserting a node in the middle of a linked list, you might have a 'node.setPrevious()' and a 'node.setNext()' method. Your Milage May Vary (YMMV) depending on how your queue is implemented.

    For example, your class likely will have class fields pointing to the first and last nodes. It could be that this field is 'rear'. Again, I'm just providing general information, and there are more than one way of implementing. You just have to make the interface work.

Similar Threads

  1. Queue in the GUI
    By jonywalker123 in forum Advanced Java
    Replies: 2
    Last Post: 03-06-2009, 08:33 PM
  2. Problem in Calculator implementation using Stack
    By realahmed8 in forum New To Java
    Replies: 1
    Last Post: 12-19-2008, 11:58 PM
  3. Problem in file implementation
    By BHCluster in forum New To Java
    Replies: 6
    Last Post: 04-21-2008, 03:21 AM
  4. Replies: 0
    Last Post: 04-09-2008, 06:41 PM
  5. Using a queue
    By Krmeus in forum New To Java
    Replies: 0
    Last Post: 12-10-2007, 03:38 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •