BlueJ don't know what i did wrong

[Arne Vajhøj]

Why? why use a Deque instead of a Stack? ... because the documentation
says so? ...

The authors of that documentation is the authors of the code.

It seems reasonable to expect them to know the domain pretty well.

A Stack is an abstraction, it's a very widely understood
abstraction, everyone who has ever read a book on software knows what a
stack is. push, pop, peek, they are Stack methods, you don't need
anything else for a Stack, even peek is questionable. Providing a method
to add something to the bottom of a Stack doesn't make sense in terms of
the 'stackness' of a Stack. It just adds meaningless and unneeded
complexity and confusion, particularly for a beginner to Java.

If you are reading someone else's code and you see

Stack s = new Stack();

you know EXACTLY what to expect. What are you to expect when you see a
Deque ... could be anything.

People reading Java Docs will know what it is.

People with CS background will know what a double ended queue is.

Arne

 

[Arne Vajhøj]

Why? why use a Deque instead of a Stack? ... because the documentation
says so? ... A Stack is an abstraction, it's a very widely understood
abstraction, everyone who has ever read a book on software knows what a
stack is. push, pop, peek, they are Stack methods, you don't need
anything else for a Stack, even peek is questionable. Providing a method
to add something to the bottom of a Stack doesn't make sense in terms of
the 'stackness' of a Stack. It just adds meaningless and unneeded
complexity and confusion, particularly for a beginner to Java.

You are aware that Stack<> provides elementAt, insertElementAt and
removeElementAt?

Arne

 

[Arne Vajhøj]

Can you give me one good reason to use a Deque instead of a Stack when a
stack is what I want apart from "because the documentation says so"

Stack<> extends Vector<> and:
* Vector<> is replaced by ArrayList<>
* it means that there is indexed access to elements

2

Deque<> is an interface:
* it is possible to chose between different implementations
* implementation specific methods hidden

4

Arne

 

[Arved Sandstrom]

On 02/26/2013 05:23 AM, lipska the kat wrote:
[ SNIP ]

What's the contract of Deque ... a double ended queue?
That in itself breaks the (humanly acceptable) contract of Queue.
If a Queue is double ended it's not (conceptually) a Queue is it?

Stack = LIFO
Queue = FIFO

Anything else isn't

[ SNIP ]

lipska

A deque (double ended queue) is a queue generalization. Despite the
name, a deque is not a queue, but a queue is a deque. If you use a deque
as a queue or a stack, then you use it appropriately.

You made a point of using things appropriately by saying "If you use
Vector methods on a Stack then you are intentionally breaking the
contract of Stack". The same applies to stack or queue usages of Deque;
in the latter case since Deque implements Queue, you work through the
lens of Queue. If wanting stack behaviour, you use the Deque methods
that are intended for stack behaviour. Exactly what you were advising.

AHS

 

[Joerg Meier]

Do you know what a stack is ?

Not to put fuel on the fire that is going on elsewhere in the thread, but
it seems to me that Stack/Deque is a bad choice for this, as he needs
random access (because certain units are helped by certain specific other
ones). A map where the helper-reference is the key would imo be the best
choice, with something like

Object[] keys = unitMap.keySet().toArray();
Unit unit = (Unit) unitMap.remove(keys[rng.nextInt(keys.length)]);

for random access. While obviously this doesn't scale terribly well, in
this use case it doesn't have to, and it's a nice concise way for doing
things.

Liebe Gruesse,
Joerg

 

[markspace]

A deque (double ended queue) is a queue generalization.

Also a pun, I think. A deque (pronounced "deck") is something you can
deal from both ends of....

 

[Joerg Meier]

with something like. Object[] keys = unitMap.keySet().toArray();
Unit unit = (Unit) unitMap.remove(keys[rng.nextInt(keys.length)]);

Yea, there needs to be a way of determining if the 'whatever' is there
or if it's been used I think. I presume you would test for null but we
might end up with the same problem the 'thereness' or not is being used
all over the place in conditional tests, I think this just needs to
happen once, probably, anyway ... too busy with other stuff at the
moment to investigate further.

Yes - .remove actually removes the object, so once a card is taken from the
deck, it's gone completely from the map. No need to write that down
anywhere. If for whatever reason you merely wanted to test for it, there is
always .contains().

Liebe Gruesse,
Joerg

 

[Arved Sandstrom]

On 02/26/2013 05:23 AM, lipska the kat wrote:
[ SNIP ]

What's the contract of Deque ... a double ended queue?
That in itself breaks the (humanly acceptable) contract of Queue.
If a Queue is double ended it's not (conceptually) a Queue is it?

Stack = LIFO
Queue = FIFO

Anything else isn't

[ SNIP ]

lipska

A deque (double ended queue) is a queue generalization. Despite the
name, a deque is not a queue, but a queue is a deque.

You have this the wrong way round I'm afraid.
A Deque 'is a' Queue because it extends Queue, you can call Queue
methods on Deque but you cannot call Deque methods on Queue.
A Queue is most definitely NOT a Deque.

These are first year comp sci concepts really.

[ SNIP ]

You want to read up on generalization and specialization.

AHS

 

[Arved Sandstrom]

On 26/02/13 09:59, Arved Sandstrom wrote:
On 02/26/2013 05:23 AM, lipska the kat wrote:
[ SNIP ]

What's the contract of Deque ... a double ended queue?
That in itself breaks the (humanly acceptable) contract of Queue.
If a Queue is double ended it's not (conceptually) a Queue is it?

Stack = LIFO
Queue = FIFO

Anything else isn't
[ SNIP ]


lipska

A deque (double ended queue) is a queue generalization. Despite the
name, a deque is not a queue, but a queue is a deque.

You have this the wrong way round I'm afraid.
A Deque 'is a' Queue because it extends Queue, you can call Queue
methods on Deque but you cannot call Deque methods on Queue.
A Queue is most definitely NOT a Deque.

These are first year comp sci concepts really.

[ SNIP ]

You want to read up on generalization and specialization.

On the other hand and discussing C++;

http://www.brpreiss.com/books/opus4/html/page158.html

Specialization
The more general abstraction is the base class and the restricted
abstraction is the derived class. E.g., when using specialization we
would derive the class Queue from the class Deque thus:
class Queue : public Deque { ... };
The Queue class interface should restrict access to only those base
class member functions that are appropriate.

Generalization
The more restricted abstraction is the base class from which the more
general abstraction is derived. E.g., when using generalization we would
derive the class Deque from the class Queue thus:
class Deque : public Queue { ... };
The Deque class inherits and generalizes the interface of the Queue class.

appears to be at odds with my earlier assertion

So, does either definition make your assertion

"a deque is not a queue, but a queue is a deque"

true?

No it does not

In the Java programming language, and where Deque extends Queue

a Deque *is* a Queue

and

a Queue *is not* a Deque

regardless of which definition of Specialization and Generalization you
use.

lipska

I'm happy with the definition that for example Knuth or Sedgwick use
(and about a million other people), where a deque is called a
generalization of a queue or a stack. The reason a deque is called a
generalization of a queue or a stack is because it is in fact more
general than a queue or a stack, and combines features of both.

Since a whole raft of CS authorities and other programming commentators
are happy to call the deque a generalization of a queue or stack when
writing about data structures, I'm pretty happy to accept this as a
definition.

Don't get Java interface implementation aka UML realization mixed up
with generalization. Deque is a generalization of Queue and Stack
because it has characteristics of both; that's why you can use a Deque
as either a Queue or a Stack. The business of Java interface Deque
extending Java interface Queue, since doing things like that is the
closest thing that Java has to multiple inheritance, is actually
generalization, where Queue is the specialization of Deque.

AHS

 

[Arved Sandstrom]

On 27/02/13 10:45, Arved Sandstrom wrote:
On 02/26/2013 07:30 AM, lipska the kat wrote:
On 26/02/13 09:59, Arved Sandstrom wrote:
On 02/26/2013 05:23 AM, lipska the kat wrote:

[snip]

I'm happy with the definition that for example Knuth or Sedgwick use
(and about a million other people), where a deque is called a
generalization of a queue or a stack. The reason a deque is called a
generalization of a queue or a stack is because it is in fact more
general than a queue or a stack, and combines features of both.

Since a whole raft of CS authorities and other programming commentators
are happy to call the deque a generalization of a queue or stack when
writing about data structures, I'm pretty happy to accept this as a
definition.

Yep, I agree, my stubborn determination to prove you wrong about this
issue clouded my judgment. On this I concede. I am human, I am
imperfect, I make mistakes.

However

I simply cannot agree with your assertion that

"a deque is not a queue, but a queue is a deque."

Enter the following into your favorite IDE

java.util.Queue queue = null;
java.util.Deque deque = null;

queue = deque;
//This compiles: Because we can store a reference to a Deque into a
//reference to a Queue, a Deque *is a* Queue

deque = queue;
//This does not compile: Because we can't store a reference
//to a Queue into a reference to a Deque, a Queue *is not* a Deque

If a Queue were a Deque then we could call Deque methods on a Queue
Can we call Deque methods on a Queue? well I can't, can you?

I'd be interested to hear your thoughts on this.

lipska

I'm not sure I agree with one of my original statements either, now that
I really think things through.

We're talking several different notions of "generalization". These
conflict pretty badly. Sticking with generalization as in generalization
& specialization, and supertypes and subtypes, on second thought I'd
have to agree with you.

A deque is a generalization of queue and stack in the sense that it is
more general; it has the operations to support use as either a queue or
a stack. It's multiple inheritance (conceptually if not for real) that
gives us this mix.

This was an interesting discussion. I now want to go and pound nails
into my forehead. Just goes to show that a body needs to be really
careful about CS statements like "a deque is a generalization of queue
and stack", because in UML/OO terms it's actually not.

AHS