Re: What is a queue?

[mfb@mbunix.mitre.org (Michael F Brenner)]

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

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