Thread: Assignment help (splitting queue)

I have a programming assignment that is simulating a queue, such as a waiting room. It is to read a data file (our professor has it and will use it to test) that our program does what it's supposed to. The method I'm currently working on is to split the queue. What it's supposed to do is take the even # nodes and them end up on a 2nd queue while the odd ones end up on the queue they are already on. I will post the code I have so far, its getting me an error with the stack. My idea was to have a temp stack to store the odd ones, and the 2nd queue. I was going to push the odd ones to the temp stack and the even ones to the 2nd queue where they belong. I would then push the odd ones back onto the original queue. It's not liking the initialization of the 2nd queue and stack though.

1st Error is on line that starts with "LinkedQueue<String>" and the error is that the type LinkedQueue<String> is not generic; it can't be parameterized with arguments <String>
2nd Error is on the following line with the LinkedStack and it says that LinkedStack can not be resolved to a type.

public LinkedQueue<String> Split ()) {
		LinkedQueue<String> cust2 = new LinkedQueue<String>();
		LinkedStack<String> temp = new LinkedStack<String>();
		int current = 0;
		int total = size;
 
		while (current <= size)
		{
			temp.push(remove());
			current++;
			cust2.push(remove());
			current++;
		}
 
		while (current != 0)
		{
			arrive(temp.pop());
		}
 
	}

Well, I have a QueueADT for the LinkedQueue and StackADT for the LinkedStack. I have another for LinearNode if you happen to need it. I am going to put my entire code that the split method belongs to as well.

public interface QueueADT<T>
{
    /**  
     * Adds one element to the rear of this queue. 
     * @param element  the element to be added to the rear of the queue  
     */
    public void enqueue(T element);
 
    /**  
     * Removes and returns the element at the front of this queue.
     * @return the element at the front of the queue
     */
    public T dequeue();
 
    /**  
     * Returns without removing the element at the front of this queue.
     * @return the first element in the queue
     */
    public T first();
 
    /**  
     * Returns true if this queue contains no elements.
     * @return true if this queue is empty
     */
    public boolean isEmpty();
 
    /**  
     * Returns the number of elements in this queue. 
     * @return the integer representation of the size of the queue
     */
    public int size();
 
    /**  
     * Returns a string representation of this queue. 
     * @return the string representation of the queue
     */
    public String toString();
 
    public boolean equals(LinkedQueue<T> list);
 
    public LinkedQueue<T> reverse();
}

public interface StackADT<T>
{
    /**  
     * Adds the specified element to the top of this stack. 
     * @param element element to be pushed onto the stack
     */
    public void push(T element);
 
    /**  
     * Removes and returns the top element from this stack. 
     * @return the element removed from the stack
     */
    public T pop();
 
    /**  
     * Returns without removing the top element of this stack. 
     * @return the element on top of the stack
     */
    public T peek();
 
    /**  
     * Returns true if this stack contains no elements. 
     * @return true if the stack is empty
     */
    public boolean isEmpty();
 
    /** 
     * Returns the number of elements in this stack. 
     * @return the number of elements in the stack
     */
    public int size();
 
    /**  
     * Returns a string representation of this stack. 
     * @return a string representation of the stack
     */
    public String toString();
}

public class LinkedQueue {
	private LinearNode<String> headNode;
	private int size;
 
	public LinkedQueue() {
		headNode = null;
		size = 0;
	}
 
	public int count() {
		return size;
	}
 
	public boolean isEmpty() {
		return size == 0;
	}
 
	public void display () {
		LinearNode<String> currentNode = headNode;
 
		while (currentNode != null) {
			System.out.println(currentNode.getElement());
			currentNode = currentNode.getNext();
		}
	}
 
	public void arrive(String personArrived) {
		LinearNode<String> newNode = new LinearNode<String>();
		newNode.setElement(personArrived);
 
		if (headNode == null) {
			headNode = newNode;
			size++;
		} else {
			LinearNode<String> currentNode = headNode;
 
			// Get to the last element
			while (currentNode.getNext() != null)  {
				currentNode = currentNode.getNext();
			}
 
			currentNode.setNext(newNode);
			size++;
		}
	}
 
	public void front() throws EmptyCollectionException {
		if (headNode != null) {
			System.out.println(headNode.getElement() + " is the next customer");
		} else {
			throw new EmptyCollectionException("Linked Queue");
		}
	}
 
	public void pass() throws EmptyCollectionException {
		if (headNode != null) {
			LinearNode<String> oldHead = headNode;
			oldHead.setNext(null);
			headNode = headNode.getNext();
 
			if (headNode.getNext() != null) {
				LinearNode<String> currentNode = headNode;
 
				while (currentNode.getNext() != null) {
					currentNode = currentNode.getNext();
				}
 
				currentNode.setNext(oldHead);
			} else {
				headNode.setNext(oldHead);
			}
		} else {
			throw new EmptyCollectionException("Linked Queue");
		}
	}
 
	public void remove() throws EmptyCollectionException {
		if (headNode != null) {
			headNode = headNode.getNext();
		} else {
			throw new EmptyCollectionException("Linked Queue");
		}
	}
 
	public boolean lookup (String name) {
		if (headNode == null) {
			return false;
		}
 
		LinearNode<String> currentNode = headNode;
 
		while (currentNode != null) {
			if (currentNode.getElement().equals(name)) {
				return true;
			} else {
				currentNode = currentNode.getNext();
			}
		}
 
		return false;
	}
 
	public void Bump (int n) 
	{
		LinearNode<String> current = headNode;
        int i = 1;
        while (i != n) 
        {
            current = current.getNext();
        }
 
        headNode.setElement(current.getElement());
	}	
 
	public LinkedQueue<String> Split ()) {
		LinkedQueue<String> cust2 = new LinkedQueue<String>();
		LinkedStack<String> temp = new LinkedStack<String>();
		int current = 0;
		int total = size;
 
		while (current <= size)
		{
			temp.push(remove());
			current++;
			cust2.push(remove());
			current++;
		}
 
		while (current != 0)
		{
			arrive(temp.pop());
		}
 
	}

Is this what you're looking for?

import java.util.Arrays;
 
public class ArrayStack<T> implements StackADT<T>
{
    private final static int DEFAULT_CAPACITY = 100;
 
    private int top;  
    private T[] stack;
 
 
    public ArrayStack()
    {
        this(DEFAULT_CAPACITY);
    }
 
 
    public ArrayStack(int initialCapacity)
    {
        top = 0;
        stack = (T[])(new Object[initialCapacity]);
    }
 
 
    public void push(T element)
    {
        if (size() == stack.length) 
            expandCapacity();
 
        stack[top] = element;
        top++;
    }
 
 
    private void expandCapacity()
    {
        stack = Arrays.copyOf(stack, stack.length * 2);   
    }
 
 
    public T pop() throws EmptyCollectionException
    {
        if (isEmpty())
            throw new EmptyCollectionException("stack");
 
        top--;
        T result = stack[top];
        stack[top] = null; 
 
        return result;
    }
 
 
    public T peek() throws EmptyCollectionException
    {
        if (isEmpty())
            throw new EmptyCollectionException("stack");
 
        return stack[top-1];
    }
 
 
    public boolean isEmpty()
    {
        if (top == 0)
        	return true;
        else
        	return false;
    }
 
 
    public int size()
    {
        int size = top;
        return size;
    }
 
    public String toString()
    {
       String s = "";
    	for (int i = 0; i < stack.length; i++)
       {
    	   s += stack[i];
       }
 
    	return s;
    }
}

--- Update ---

The professor put in the instructions something (about the split method) that left me wondering if it should be coded a bit differently in the LinkedQueue part...

So in the driver, it might look something like this:
LinkedQueue<String> customers = new LinkedQueue<String>();
// a bunch of arrive/inserts
LinkedQueue<String> cust2 = customers.split();
// now cust2 list has ~half the customers and customers has the rest

So the LinkedQueue would need to implement the QueueADT interface then? Her instructions were: This assignment will require you to modify the LinkedQueue class and QueueADT interface, and write a driver program to test the class.

We covered the Stacks/Queue a bit in Java 2 but our teacher didn't explain it and just expected us to know it so now I'm paying for it this time around, so I apologize for any stupid mistakes or lack of knowledge.