Re: What is a queue?

[Jeff Carter <spam.carter.not@spam.innocon.com>]

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