Re: What is a queue?

[robert_dewar@my-dejanews.com]

In article <7afgd8$fnj@top.mitre.org>,
  mfb@mbunix.mitre.org (Michael F Brenner) wrote:
> Thanks for the alternative to the first definition, which
> has some strengths.
>
> However, there is nothing wrong with implementing
> a general-purpose extensible array of data and
> putting and taking from either end

No, but there is a lot wrong with calling this a queue.
As was pointed out this is a dequeue, and confusing the
two data structures and their terminology is a bad idea.

Also, although conceptually a queue is a special case of
a dequeue with only a limited subset of the functionality
in use, it is a bad idea to use it this way for two
reasons.

If you really want a queue, it is merely confusing and
error prone to provide operations that have nothing to do
with a queue.

It may be substantially less efficient to implement a
general dequeue than a queue. In particular there are data
structures suitable for queue implementation that are not
suitable for dequeue use.


, so you get two-sided queue,
> which can serve as the implementation of both of your

definitions
> (dequeue and queue), as well as the implementation of a

stack.
>
> When three structures are this closely related, it makes

sense
> to do the extensible data structures with my more

flexible
> definition, and then provide application-level restricted
> packages that provide only certain operations.
>
> In one sense, the exclusive definition is written for

that
> higher level and the inclusive defintion was intended for

that
> lower implementation level, because the programmer may

spend
> quite a bit more time on that level than on the outer

levels.
>
> I was at the grocery store today and the clerk opened up

an
> new line and the back half of the queue wound around to

that
> new line, effectively taking from both ends of the queue
> at the same time.
>
> And many algorithms require PEEKING at various

intermediate
> elements of a two-sided queue without deleteing them from

the
> queue. For example, a 10-line windowed grep, which

searches
> for a pattern and prints the file name and the previous
> 10 lines and the next 10 lines for each line that matches
> the pattern.
>
> Thanks again for pointing out that there are several ways

of
> defining things, and several ways of implementing various
> data structures.
>
> Mike
>
>

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own