Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > queue, deque, priority_queue

Reply
Thread Tools

queue, deque, priority_queue

 
 
newsock
Guest
Posts: n/a
 
      10-24-2003
What differences between queue, deque and priority_queue? And under what
situations choose one of them to use? Thanks for your help!


 
Reply With Quote
 
 
 
 
Jerry Coffin
Guest
Posts: n/a
 
      10-24-2003
In article <47_lb.190847$0v4.14787426@bgtnsc04-
news.ops.worldnet.att.net>, http://www.velocityreviews.com/forums/(E-Mail Removed) says...
> What differences between queue, deque and priority_queue? And under what
> situations choose one of them to use? Thanks for your help!


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.

--
Later,
Jerry.

The universe is a figment of its own imagination.
 
Reply With Quote
 
 
 
 
Tim Clacy
Guest
Posts: n/a
 
      10-24-2003
Jerry Coffin wrote:
> In article <47_lb.190847$0v4.14787426@bgtnsc04-
> news.ops.worldnet.att.net>, (E-Mail Removed) says...
>> What differences between queue, deque and priority_queue? And under
>> what situations choose one of them to use? Thanks for your help!

>
> 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.


 
Reply With Quote
 
Stewart Gordon
Guest
Posts: n/a
 
      10-27-2003


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:

<snip>
> ...'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.


Where in the world does "dequeue" mean deque?

Stewart.

--
My e-mail is valid but not my primary mailbox. Please keep replies on
on the 'group where everyone may benefit.
 
Reply With Quote
 
Tim Clacy
Guest
Posts: n/a
 
      10-29-2003
Stewart Gordon wrote:
> 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:
>
> <snip>
>> ...'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.

>
> Where in the world does "dequeue" mean deque?
>
> Stewart.



.... 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?


I'm somewhat suprised that anyone could actually defend the unispired choice
of names used in this context; have you escaped from somewhere that had soft
walls?


// 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
{
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.


Tim


 
Reply With Quote
 
Stewart Gordon
Guest
Posts: n/a
 
      10-30-2003


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:
<snip>
> // 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.


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.
 
Reply With Quote
 
Tim Clacy
Guest
Posts: n/a
 
      10-31-2003
Stewart Gordon wrote:
> 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:
> <snip>
>> // 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?


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?

>
>> 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.

>
> 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.


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.


Tim


 
Reply With Quote
 
Tim Clacy
Guest
Posts: n/a
 
      10-31-2003
Jerry Coffin wrote:
> In article <3f9f827d$0$257$(E-Mail Removed)>,
> (E-Mail Removed)amdk says...
>
> [ ... ]
>
>> ... 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).



Abreviations and corner cutting are the root of many a programming evil; one
of the objectives of using a high-level language over machine code is to
provide unambiguous, maintainable, sources instead of crude error-prone
mnemonics. Since most high level languages allow use of mixed case and have
limits for identifier names more than 8 letters, why would anyone not use:

struct DoubleEndedQueue
{
:
};

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).


Tim


 
Reply With Quote
 
Gavin Deane
Guest
Posts: n/a
 
      10-31-2003
"Tim Clacy" <(E-Mail Removed)> wrote in message news:<3fa22a96$0$265$(E-Mail Removed)>...
> Stewart Gordon wrote:
> > 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:
> > <snip>
> >> // 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?

>
> 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.


Perhaps. Though dual_port_buffer would be more in keeping with the
style of the rest of the language and library.

> 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?


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.

> >> 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.

> >
> > 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.

>
> 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.


I would hope that any software developer who had never used STL
before, then came across std::deque, might look it up to find out what
it is. I believe 'deque' is used as a noun to mean 'double ended
queue' (misnomer or otherwise) outside of just the C++ standard
library. I have never encountered the verb 'deque' as an abbreviation
for 'dequeue' outside of your code above.

GJD
 
Reply With Quote
 
Tim Clacy
Guest
Posts: n/a
 
      10-31-2003
Gavin Deane wrote:
> "Tim Clacy" <(E-Mail Removed)> wrote in message
> news:<3fa22a96$0$265$(E-Mail Removed)>...
>> Stewart Gordon wrote:
>>> 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:
>>> <snip>
>>>> // 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?

>>
>> 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.

>
> Perhaps. Though dual_port_buffer would be more in keeping with the
> style of the rest of the language and library.
>
>> 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?

>
> 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.



I had muddled deque and dequeue... which kind of proves the point. To
clarify, these are the words in question:

queue - noun
deque - noun (made up name)
dequeue - verb (or noun depending on library)
enqueue - verb (verb)

My original point was simply if 'queue' is a Queue ADT, then one might
reasonably expect a double-ended Queue to be called 'dequeue'... but no, a
double-ended Queue ADT is called deque... because 'dequeue' has already been
used up as a verb. I find it all quite a laughable shambles; this is the
kind of mess that is inevitable when you favour mnemonics of meaningful
names.

However, the plot thickens... If you google C++ deque dequeue, you'll find
many examples of libraries using 'dequeue' as a name of the double-ended
queue ADT... and also STL tutorials using dequeue as the double-ended queue
ADT!


>>>> 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.
>>>
>>> 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.

>>
>> 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.

>
> I would hope that any software developer who had never used STL
> before, then came across std::deque, might look it up to find out what
> it is. I believe 'deque' is used as a noun to mean 'double ended
> queue' (misnomer or otherwise) outside of just the C++ standard
> library. I have never encountered the verb 'deque' as an abbreviation
> for 'dequeue' outside of your code above.
>
> GJD



 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Using priority_queue Aguilar, James C++ 13 07-19-2004 06:37 PM
std::priority_queue derivable? red floyd C++ 2 06-16-2004 04:33 PM
reserve with std::priority_queue Tino C++ 3 05-28-2004 09:14 PM
priority_queue<> underlying container Dave C++ 7 04-22-2004 05:17 PM
clearing a priority_queue Tino C++ 4 07-09-2003 10:05 PM



Advertisments