?

Log in

No account? Create an account
Previous Entry Share Next Entry
Stacks and Queues...
blaisepascal
To me, a "stack" is a data structure in which the most recently added item is the most accessible. If you put on a stack, in order, the Ace, 3, 5, and 7 of clubs, you have to first deal with the 7 before you deal with the 5, then the 3, and finally the Ace. It's referred to as a "LIFO" structure: Last In, First Out. The name comes with the physical analogy to a stack of items, where you have to deal with the stuff on the top before you can get to the lower stuff. The appropriate terms that go with a stack are: items are "on" a stack, the single accessible item is at the "top", and one "pushes" an item onto a stack and "pops" an item from the top of a stack.

Alternatively, a "queue" is a data structure in which the first added item is the most accessible. If you put the same four cards in a queue, you'd deal with the Ace before the 3, then the 5, and finally the 7. It's referred to as a "FIFO" structure: First In, First Out. The name comes with the physical analogy of people in a line (or "queue", if you are British) waiting to be served. The appropriate terms that go with a queue are: items are "in" a queue, the single accessible item is at the "head", and new items are added to the "tail", Unlike "push" and "pop" for stacks, there aren't any standardized terms for adding and removing items from a queue, although "enqueueing and "dequeueing" are common.

Perl uses "push" and "pop" to refer to one end of a list, and "unshift" and "shift" to refer to the other end, so one can use unshift and shift (pr push and pop) for a stack, or unshift and pop (or push and shift) for a queue. There is also a data structure called a "double-ended queue" (or dequeue) in which you can operate on both ends, but have no easy access to the middle. "Priority queues" exist in which the order isn't strictly according to order of entry, but rather the cool items get to go first. Some very efficient sorting techniques are based on the idea of adding everything to a priority queue then removing them in sorted order.

Stacks and Queues are complementary data structures, and using one or the other makes a big difference in what you are doing. As a classic example, when searching something which has a tree-like structure (like where a file is on a disk, or what is a winning move in a game, etc) the standard algorithm is to add the root node to a stack or a queue, and then loop through every item on the stack or queue, generating new nodes to search based on the current node and adding those new nodes to the stack or the queue. If you use a stack, you perform a "depth-first" search, while if you use a queue, you perform a "breadth-first" search.

I quess what I'm getting at is (a) I can't seem to let some things go, and (b) when you are calling on people in the order in which they raised their hand, you are using a queue and not a stack.

  • 1
Wait, I'm confused, who is it that calls queues stacks?

Anarchist Nomad, the first responder to this entry, was chairing a meeting of about 50 people on Monday (of which I was one). During this meeting, he amazed people by being able to keep track (w/o written notes) of the people who had requested an opportunity to speak, and the order in which they had done so. He would, between each speaker, recite (or at least count, with pointing) the full list of 8-10 people remaining queued to speak, as well as adding people to the queue as needed.

Several times during the meeting he referred to this list of people waiting to speak as the "stack", as that is apparently what he learned was the terminology during the 5 years he spent as an anarchist organizer (which still sounds like an oxymoron to me).

I attempted to correct him at one point, calling out "queue" after he said "stack", and was misinterpreted by the meeting as a whole: Nomad is currently a Lecturer in Recent Runes at Oxford (well, not really Recent Runes, but he does work in the High Energy Magic Physics Building), and so it was interpreted as me correcting him to the proper Britishism.


  • 1