[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
 }
----
[Category Concept] | [Arts and crafts of Tcl-Tk programming]