From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,e105067bce4d170b
X-Google-Attributes: gid103376,public
From: robert_dewar@my-dejanews.com
Subject: Re: What is a queue?
Date: 1999/02/18
Message-ID: <7afvvg$9iu$1@nnrp1.dejanews.com>#1/1
X-Deja-AN: 445546972
References: <36accbc1.0@news.mountain.net> <79q1qc$blj@top.mitre.org>
 <36C19EBE.FF25D409@spam.innocon.com> <7afgd8$fnj@top.mitre.org>
X-Http-Proxy: 1.0 x4.dejanews.com:80 (Squid/1.1.22) for client 205.232.38.14
Organization: Deja News - The Leader in Internet Discussion
X-Article-Creation-Date: Thu Feb 18 03:04:21 1999 GMT
Newsgroups: comp.lang.ada
X-Http-User-Agent: Mozilla/4.04 [en] (OS/2; I)
Date: 1999-02-18T00:00:00+00:00
List-Id: <comp.lang.ada>

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