How to do a non destructive queue examination in Java

Question

Hello, I am helping my son with a college programming class, and I guess I need the class too. He has completed the assignment, but I don't believe he is doing it the best way. Unfortunately I can't get it to work with my better way. It's clearly better, because it doesn't work yet.

He is being asked to implement some methods for a class that extends another class.

He was told he must use the following class definition, and he cannot change anything in ListQueue.

public class MyListQueue <AnyType extends Comparable<AnyType>> extends ListQueue<AnyType>

Heres what is in ListQueue

// Queue interface
//
// ******************PUBLIC OPERATIONS*********************
// void enqueue( x )      --> Insert x
// AnyType getFront( )    --> Return least recently inserted item
// AnyType dequeue( )     --> Return and remove least recent item
// boolean isEmpty( )     --> Return true if empty; else false 
// void makeEmpty( )      --> Remove all items
// ******************ERRORS********************************
// getFront or dequeue on empty queue

/**
 * Protocol for queues.
 */

OK I feel pretty good about traversing a linked list in Pascal or C (showing my age) but have never worked in an OOP language before.

When I attempt something like this

dummyQueue = this.front.next;

I get the following error. * front has private access in ListQueue *

Which I agree with, but other than dequeueing an item, how can I traverse the list, or otherwise get access to front, back, next and previous which are all in ListQueue.

An education would be appreciated.

Thanks, David

Answer 1

If I understand you correctly, you're doing something like this:

MyListQueue<String> dummyQueue = new MyListQueue<String>();
dummyQueue = this.front.next;

If so, one of the main tenets of OOP is encapsulation, i.e. data hiding. The idea is that users outside of the class don't have access to the inner state of the class.

If you're looking to determine the size of the Queue and you can't modify either the interface or the implementation, one thing you could do is create a delegate Queue that overrides enqueue and dequeue to increment and decrement a counter.

Answer 2

If you decide for a queue, you usually only want to enqueue and dequeue elements. You want to know if the queue is empty and want to look at the front element if you need it or leave it for someone else. A queue is a sort of buffer that avoids blocking, if the sender is faster then the receiver. With a queue, the receiver can decide when to read the next entry. A queue may implement some (priority based) sorting and decide, which element is the front element.

If you need other operations like traversing the list, then a queue might not be the best choice. Look at other collection types, maybe at ArrayList.

Some things can be done though, you can subclass ListQueue and override some methods. So if you want an additonal size() method, this could be a solution:

public class MyListQueue <T extends Comparable<T>> extends ListQueue<T> {

  private size = 0;

  public void enqueue(T element) {
    size++;
    super.enqueue(element);
  }

  public T dequeue() {
    if (isEmpty()) {
       return null; // that's a guess...
    }
    size--;
    super.dequeue(element);
  }

  public int size() {
    return size;
  }
}

I've replaced AnyType with T which is more common.

Answer 3

You asked, "Other than dequeueing an item, how can I traverse the list, or otherwise get access to front, back, next and previous which are all in ListQueue."

In the purest sense, you should not be able to.

An idealized queue promises only a few things:

• Push items into the back
• Pop items from the front
• (Possibly) Inspect front item, if not empty
• (Possibly) A definition space predicate for pop and inspect, determining whether the queue is empty

I'll assume for the moment that the queue is not meant to be used with either concurrent readers (accessing the front at the same time) or with concurrent readers and writers (accessing the back and front at the same time).

Given that definition, there's no reason to want to look "inside" the queue. You put things in one side and take things out the other side. If you take bounding of queue size into account, you may need an additional definition space predicate for the push operation to determine whether the queue is full. "Being full" only makes sense if the queue is bounded. "Being empty" is only relevant if the thread calling pop or inspect doesn't wish to block.

Beyond that, there's the pragmatic idea of a queue. We can assume it's a sequence of items that -- barring concurrency concerns -- has an observable non-negative size and may even allow visiting each item in the sequence. Some queues even go so far as to allow removal or rearrangement of items at positions other than the front of the sequence. At that point, though, we're not really discussing a queue anymore. We're discussing the sequence that underlies the queue. If we need this kind of access, we don't need a queue. We need a sequence of which we want to offer a queue-like view to other parts of the program.

That's why queues are not usually concrete types in data structure libraries. In C++, type std::queue is a decorator around some other container type. In Java, java.util.Queue is an interface. Scala take a different approach: class scala.collection.mutable.Queue is an extension of type MutableList. That's similar to the approach mandated in your son's assignment, but it's not clear whether your ListQueue ever intended to allow outsiders (including subclasses) to take advantage of its "list nature" -- penetrating the queue view to use the sequence within.

Do you have a requirement to be able to visit anything but the head of your queue? Needing to do so limits your choices as to what kinds of queues your consuming functions can accommodate. It seems like we're learning the wrong lessons with this assignment.