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: mfb@mbunix.mitre.org (Michael F Brenner) Subject: Re: What is a queue? Date: 1999/02/17 Message-ID: <7afgd8$fnj@top.mitre.org>#1/1 X-Deja-AN: 445483170 References: <36accbc1.0@news.mountain.net> <79q1qc$blj@top.mitre.org> <36C19EBE.FF25D409@spam.innocon.com> Organization: none Newsgroups: comp.lang.ada Date: 1999-02-17T00:00:00+00:00 List-Id: > 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