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=0.1 required=5.0 tests=AC_FROM_MANY_DOTS,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: Jeff Carter <spam.carter.not@spam.innocon.com>
Subject: Re: What is a queue?
Date: 1999/02/19
Message-ID: <36CD847C.5C50BD27@spam.innocon.com>#1/1
X-Deja-AN: 446091398
Content-Transfer-Encoding: 7bit
References: <36accbc1.0@news.mountain.net> <79q1qc$blj@top.mitre.org>
 <36C19EBE.FF25D409@spam.innocon.com> <7afgd8$fnj@top.mitre.org>
Content-Type: text/plain; charset=us-ascii
Organization: Innovative Concepts, Inc.
Mime-Version: 1.0
Newsgroups: comp.lang.ada
Date: 1999-02-19T00:00:00+00:00
List-Id: <comp.lang.ada>

Michael F Brenner wrote:
> 
>     > Mike wrote a long message about queues, which he defined as
>     > having such operations as Add_To_Left and Add_To_Right.
>     >
>     > All additions to a queue go on the tail, and all removals come from the
>     > head. A structure which allows additions and removals from both ends is
>     > a dequeue (pronounced deck).
> 
> 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, 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.

Well, at a low level, queues, dequeues, and stacks are all I/O-limited
lists, but that does not make a list a queue. It means that a list may
used to implement a queue. Similarly, a dequeue may be used to implement
a queue, but a dequeue is not a queue.

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

I think I mentioned the same kind of discrepencies between ideal
software queues and the people queues one encounters in the real world.

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

-- 
Jeff Carter
E-mail: carter commercial-at innocon [period | full stop] com
"I unclog my nose towards you."
Monty Python & the Holy Grail