Queue Story

How do you implement a queue?

I can vividly remember the moment I became a computer scientist. I was in a first data structure class taught by Andrzej Proskurowski at the University of Oregon. Gray light through the windows washed most of the color out of the room (we are talking about Eugene, Oregon, here). I was just getting comfortable with data structures as a concept separate from programming, but I was still squirming a bit sitting there, since Andrzej was a pretty aggressive professor.

Andrzej had the size and energy of a hummingbird, but muscled like a gymnast. He had a thick black goatee and an even thicker Polish accent. He kept us all on our toes with the simple trick of calling everyone by name after hearing the names exactly once. He had just presented a linked list implementation of queues in Pascal using a header record. I followed pretty well, a first for me, when I got a conviction that there was a shorter implementation.

I could see nothing but my notebook as I scrambled to code in my head and then on paper a version that used a footer record instead. Sure enough, I could slice one line out of one of the routines. After class I hustled over to the computer center to try it out. Bingo! It ran. I rushed over to Andrzej's office to show him my gem. He was skeptical at first, but we went over it and he congratulated me on my success. It was the first time I'd spoken to a professor one-on-one. I was overwhelmed.

I have since given up computer science for software engineering, but writing this has given me a renewed sense of how important that little bit of transformation was for me. When I came to Smalltalk, I was crestfallen when I discovered that no such effort was necessary to implement queues. I could just use an OrderedCollection.

Operation       Message

add             addFirst:
remove          removeLast:
empty           isEmpty

As with stacks, you lose a little by translating the queue operations into messages to OrderedCollection protocol, but not nearly enough to make up for the cost of adding a new class.

---

Implement queues using an OrderedCollection.

I have used OrderedCollections as queues a couple of ways in my career. The most common is in implementing level-order traversal, where you need to visit all the depth 1 nodes before you visit the depth 2 nodes and so on. The code looks like this:

Node>>levelOrderDo: aBlock
        | queue |
        queue := OrderedCollection with: self.
        [queue isEmpty] whileFalse:
                [| current |
                current := queue removeLast.
                aBlock value: current.
                queue addAllFirst: current children]

-- from a posting by KentBeck