CODEWITHSUNDEEP
javadata-structuresqueue
ring bearer
ring bearer

Reputation: 20783

Queues in Java allows removal of random element. is this bad?

Queue In Java provides FIFO data structure. Per what I learned, queues have some responsibility to adhere to first-in-first-out behavior. In other terms, you may not remove items from the middle of the queue. However, in Java we can remove random queue elements by using an iterator.

Is this a bad design encapsulation-vise? or is the queue data structure supposed to allow this?

Queue<String> queue = new LinkedList<String>();
queue.add("e1");
queue.add("e2");
queue.add("e3");
queue.add("e4");

queue.remove("e3");

Upvotes: 7

Views: 4414

Answers (3)

Stephen C
Stephen C

Reputation: 718798

Per what I learned, queues have some responsibility to adhere to first-in-first-out behaviour.

You have probably been reading a text book or some lecture notes or something that describe how an idealised FIFO queue works. But what you have failed to realise is that not all queues are FIFO. Not in the real world, and not in computer systems. (For instance, if (hypothetically) the President Obama went to a busy MacDonalds restaurant, you would find that he was immediately moved to the front of the queue. That's a queue behaving in a non-FIFO fashion.)

Anyway, the Java Queue is an interface for any kind of queue, not just FIFO queues. It also supports priority queues, and any other queuing semantics you could dream up ... if you care to provide your own implementation class.

The other point is that the remove(E) operation is not providing the "next customer please" operation. It is the equivalent of a customer deciding that they really would prefer a pizza ... and walking out of the door. An idealized queue doesn't support this, but usable library classes do ... because applications need to be able to do this kind of thing.

The bottom line is that Java Collection class hierarchy (including clue Queue) is designed to be useful and easy to use, rather than to rigidly fit someone's abstract model of data structures.

But then Queue may allow a sneakIn method, that lets you sneak in to the middle of a queue - where is that method?

Well, since most real applications don't need it, it isn't there. (If that was a common use-case, such a method would be provided, in specific queue implementation classes even if not in the Queue interface.)

Once again, Java classes and interfaces are specified for their utility and usability in real programs, not (in this case) so they can model POTUS in a burger joint.

Probably I am brain washed by text book definitions and C/C++ labs that I did at school.

An alternative explanation is that you mistook the true purpose of the definitions, etcetera.

Upvotes: 3

Evgeniy Dorofeev
Evgeniy Dorofeev

Reputation: 136012

Java Queue is not necessarily FIFO. Queue API says

Queues typically, but do not necessarily, order elements in a FIFO (first-in-first-out) manner.

It depends on implementation, for instance PriorityQueue is not FIFO but LinkedList that you used is FIFO.

Queue.remove() API does not say it removes a random element, it says

Retrieves and removes the head of this queue.

In your example it had to be

queue.remove();

and it would remove e1

Upvotes: 1

Marc Baumbach
Marc Baumbach

Reputation: 10473

Queue obviously inherits some of this added functionality by being part of the Collection hierarchy. From a polymorphic standpoint, it is beneficial to have Queue act like any other Collection as it increases the portability of the data structure.

From a design perspective, I wouldn't say it's bad necessarily. Imagine a queue/line at a grocery store. There are situations where a customer might need to be removed from the middle of the line. This particular implementation of a queue supports that, which can be useful.

While you could argue that the additional methods could let you shoot yourself in the foot, you could easily create an implementation of Queue that doesn't allow things like remove(Object) or iterator.remove() if you wanted a strict Queue.

Upvotes: 6

Related Questions