N
newsock
What differences between queue, deque and priority_queue? And under what
situations choose one of them to use? Thanks for your help!
situations choose one of them to use? Thanks for your help!
What differences between queue, deque and priority_queue? And under what
situations choose one of them to use? Thanks for your help!
Jerry said:With a queue, you insert items at one and and extract them from the
other end -- i.e. you can ONLY get things out in the order in which
they were inserted.
With a deque, you can insert and/or remove from either end, so you
get a combination of stack behavior (remove the most recently
inserted item)
or queue behavior (as above).
A priority queue is different from either of these. With a priority
queue, you specify an ordering by which items will be sorted. You
insert items and you remove items, but when you remove items, you get
them in sorted order. This is handy for things like tasks that have to
be completed. When a task arises that will need to be done, you put
it into the priority queue. When you're ready to carry out a task,
you
pull one from the priority queue, and you'll get the highest priority
task that's waiting.
...'dequeue' is a particularly confusing choice of name; it stands for
Double-Ended Queue... but also means 'to remove from a queue' when used as a
verb.
Stewart said:While it was 24/10/03 10:41 am throughout the UK, Tim Clacy sprinkled
little black dots on a white screen, and they fell thus:
Where in the world does "dequeue" mean deque?
Stewart.
// A double-ended queue (not to be confused with any common or garden queue
with, of course, also has two ends):
//
template<typename T>
struct dequeue
{
// A single ended queue (hmm, the word oxymoron springs to mind)
//
struct queue
{
Huh?
void enque(T item);
T deque(); // Apparently, self-explanitory (despite the made-up
word 'que')
:
};
};
Mr Grodon; if you can't see any issue here, then I pity the poor souls who
have to fix your code.
Stewart said:While it was 29/10/03 9:03 am throughout the UK, Tim Clacy sprinkled
little black dots on a white screen, and they fell thus:
Huh?
I pity the poor souls, which I believe exist in some programming
circles, who use "deque" as an abbreviation for "dequeue", presumably
unaware of what "deque" really means.
Stewart.
Jerry said:[ ... ]
... are you implying that that there is no ambiguity? In what way is
'deque' sufficiently different from 'dequeue' that there is no
ambiguity? Why not post a .wav file so we can hear the difference?
In pronunciation, ambiguity is removed -- a double-ended queue is
pronounced like "deck" while removing from a queue is pronounced like
"DQ" (i.e. pronounce the names of the letters in quick succession,
much
the way an American teenager would refer to Dairy Queen).
Tim Clacy said:Hmm, trying stringing some real words together to form a complete question
if you don't understand. My point is that all queues have two ends; in fact,
since there is no such thing as a single-ended queue, a double-ended queue
is a complete misnomer. Perhaps 'DualPortBuffer' might have been a better
choice of name.
The lousy choice of name for an abstract-data-type is
further compounded by trying to squeeze in an operation name De-Queue (to
remove from the queue), but due to some unfathomable love of compounded,
lowercase mnemonics as identifier names, we have 'deque'. Why not use real
verbs instead of making your own up?
Anyone software developer from the civilised world who hadn't used STL
before would not understand what on Earth you ranting about with dequeue and
deque... which proves my point convincingly.
Gavin said:Perhaps. Though dual_port_buffer would be more in keeping with the
style of the rest of the language and library.
Huh?
Unless I am missing part of the thread, it was you who brought up the
term 'to dequeue'. The C++ standard doesn't mention the word
(although, obviously the concept will be relevant to C++ programmers
using std::queue and std::deque).
Nobody is inventing verbs. The only invented word here is deque, which
is a noun.
Abreviations and corner cutting are the root of many a programming evil;
T Queue::RemoveFromFront() // Or Get, Pull, Pop... anything except made-up
words likke 'deque' [ ... ]
void Queue::AddToBack() // Or Put, Push, Add... anything except made-up
words like 'enque'
I suspect the American love of acronyms and short-cuts coupled with an
unhealthy disregard for standard spelling has a hand in this shoddy
workmanship; this is the country, after all, that even abbreviates USA to US
and gasoline to gas (the only country in the world where you can get wet
feet from spilling gas).
Jerry said:[ ... ]
Abreviations and corner cutting are the root of many a programming
evil;
They're also the cornerstone not only of programming, but of
intelligence in general -- the brain would be utterly overloaded of it
had to operate only on complete, unambiguous, literal representations
of things. Abbreviations and other methods of compressing the data
are a necessity for the brain to cope. The degree to which one can
compress
ideas determines, to a large degree, the complexity of ideas that can
be grasped and processed.
T Queue::RemoveFromFront() // Or Get, Pull, Pop... anything except
made-up words likke 'deque' [ ... ]
void Queue::AddToBack() // Or Put, Push, Add... anything except
made-up words like 'enque'
English was not handed down from God on stone tablets. Every word is
made up, and virtually everything that gets said on this newsgroup
(among many other places) was thoroughly improper English at one time.
"Add", "Put" and "Push" have no inherent superiority over "enque".
As with science fiction, so with science fact as well. At least 90%
of what's bad in programming has its root in the US, but then at
least 90%
of everything that happens in programming has its root in the US...
In reality, of course, people elsewhere shorten words as well, simply
in other ways -- you can complain about "gas" in the US, but people
in the
UK are no better -- what they put in their cars is "petrol", not
"petroleum".
In the end, I've yet to see a single shred of evidence linking the
readability of a program to the nationality of the programmer.
Getting back to the original subject, enque, deque and dequeue are all
perfectly reasonable terms. Your failure to understand them implies
no ambiguity in the terms themselves.
Stewart said:While it was 24/10/03 10:41 am throughout the UK, Tim Clacy sprinkled
little black dots on a white screen, and they fell thus:
Where in the world does "dequeue" mean deque?
Stewart.
...ut goes without saying that the brain stands a better chance of building
a superior model of the problem if the problem is described in familiar
metaphors, using familiar language.
...other than being real words.
If you are unable to see how the UK abreviation is unambiguous
whilst the US abreviation is comically ambiguous,
then I'm not suprised you are also unable to see any issue with 'dequeue'
and 'deque'.
Your presumption that I'm unable to understand these terms is both incorrect
and presumptuous;
I'm simply pointing out issues with nomenclature. Your
experience must be more limited than mine, since you obviously have never
come across different libraries that use alternative, conflicting
terminolgy.
Jerry said:[ ... ]
...ut goes without saying that the brain stands a better chance of
building a superior model of the problem if the problem is described
in familiar metaphors, using familiar language.
Things that go without saying are mostly indefensible assumptions.
...other than being real words.
You've clearly missed the _entire_ point.
[ ... ]
If you are unable to see how the UK abreviation is unambiguous
whilst the US abreviation is comically ambiguous,
Yes, I'm quite unable to see any such thing. Apparently you live in a
substantially different world than I do though -- in your world,
gasoline is the _only_ petroleum product on the planet, but where I
live, there is a veritable plethora of petroleum products.
then I'm not suprised you are also unable to see any issue with
'dequeue' and 'deque'.
I never said I didn't see any issue with dequeue and deque. In fact,
if
you had the reading skills required to graduate from grade school
when I
was growing up, you'd understand that my original post said quite the
opposite!
Your presumption that I'm unable to understand these terms is both
incorrect and presumptuous;
Perhaps you would do well to go to a different newsgroup, such as one
where they discuss reasoning -- a statement like "Your
presumption...is...presumptuous" shows clear shortcomings in this area
at the present time.
I'm simply pointing out issues with nomenclature. Your
experience must be more limited than mine, since you obviously have
never come across different libraries that use alternative,
conflicting terminolgy.
You _must_ be right. Your logic is so thoroughly iron-clad that
nothing
you say could possibly be presumptuous!
I have to admit that being accused of lack of experience is a welcome
change from the usual. The more common scenario is that some 20-
something type complains about how slowly his 3+ GHz machine boots,
and
I foolishly mention the 20+ minutes it took to do a ground-zero dead
start on a CDC mainframe, or he complains about how many CD-ROMS a
program occupies, and I foolishly mention the time I just about cut my
own foot off after I dropped a large program (a box of Hollerith
cards)
on my toe while I was having a gout attack!
Want to reply to this thread or ask your own question?
You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.