Version 2 of Stacks and queues

Richard Suchenwirth 2002-05-05 - Stacks and queues are containers for data objects with typical access methods:

push: add one object to the container
pop: retrieve and remove one object from the container

In Tcl it is easiest to implement stacks and queues with lists, and the push method is most naturally just good old lappend, so we only have to code a single generic line for all stacks and queues:

 interp alias {} push {} lappend

if 0 {It is pop operations in which stacks, queues, and priority queues differ:

in a stack, the most recently pushed object is retrieved and removed (last in first out, LIFO)
in a (normal) queue, it is the least recently pushed object (first in first out, FIFO)
in a priority queue, the object with the highest priority comes first.

Priority (a number) has to be assigned at pushing time - by pushing a list of two elements, the item itself and the priority, e.g..

 push toDo [list "go shopping" 2]
 push toDo {"answer mail" 3}
 push toDo {"Tcl coding" 1}  ;# most important thing to do

In a frequent parlage, priority 1 is the "highest", and the number increases for "lower" priorities - but you could push in an item with 0 for "ultrahigh" ;-) Popping a stack can be done like this:}

 proc pop name {
    upvar 1 $name stack
    set res [lindex $stack end]
    set stack [lrange $stack 0 end-1]
    set res
 }

if 0 {Popping a queue is similarly structured, but with so different details that I found no convenient way to factor out things:}

 proc qpop name {
    upvar 1 $name queue
    set res [lindex $queue 0]
    set queue [lrange $queue 1 end]
    set res
 }

if 0 {Popping a priority queue requires sorting out which item has highest priority. Sorting can be done when pushing, or when popping, and since our push is so nicely generic I prefer the second choice (as the number of pushs and pops should be about equal, it does not really matter). Tcl's lsort is stable, so items with equal priority will remain in the order in which they were queued:}

 proc pqpop name {
    upvar 1 $name queue
    set queue [lsort -real -index 1 $queue]
    qpop queue ;# fall back to standard queue, now that it's sorted
 }

A practical application is e.g. in state space searching (see Searching A Star in Space), where the kind of container of the to-do list determines the strategy:

stack is depth-first
(normal) queue is breadth-first
priority queue is any of the more clever ways: A*, Greedy, ...

Category Concept | Arts and crafts of Tcl-Tk programming