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

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 parlance, 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] -- may get slow
    set stack [lreplace $stack [set stack end] end] ; # TRICKY: Making sure list is not shared.
    set res
 }

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 queue [lreplace $queue [set queue 0] 0]
    set res
 }

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
 }

NEM The versions of pop presented here, while simple, exhibit very poor performance on even medium-sized lists (e.g. popping all elements of a 10000 list takes over a minute on my dual-core 2GHz machine). See Implementing FIFO queues for some excellent code that reduces this runtime to sub-second by avoiding the costly lrange calls.

TV Very poor indeed. Ripping through a 10,000 long pointer list somewhere in memory may take under a few milliseconds I'd imagine is reasonably possible.

NEM Yes. These simple implementations do tons of array copying, which kills performance. See Performance of Various Stack Implementations for some notes on different approaches. RS added the K-alike improvements from that page.

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, ....

Recent-use lists: A variation that can be used both in a stack or queue fashion is a list of values in order of their last use (which may come handy in an editor to display the last edited files, for instance). Here, pushing has to be done by dedicated code because a previous instance would have to be removed:

 proc rupush {listName value} {
      upvar 1 $listName list
      if {![info exist list]} {set list {}}
      set pos [lsearch $list $value]
      set list [lreplace $list $pos $pos]
      lappend list $value
 }
 % rupush tmp hello
 hello
 % rupush tmp world
 hello world
 % rupush tmp again
 hello world again
 % rupush tmp world
 hello again world

The first element is the least recently, the last the most recently used. Elements are not removed by the popping, but (if necessary) when re-pushing. (One might truncate the list at front if it gets too long).

AJD Yet-another implementation of lshift:

 proc K {x y} {set x}
 proc lshift { arry args } {
        upvar $arry a
        if {![info exists a]} { error "no such variable $arry" }
        if {[llength $args]} {
                if {[llength $args] != 1} { error "Usage: lshift arryName ?var?" }
                upvar [lindex $args 0] res
        }                
        set startlen [llength $a]
        set res [lindex $a 0]
        set a [lrange [K $a [set a {}]] 1 end]
        if {[llength $args]} {
                return $startlen
        } else {
                return $res
        }
 }
 # ...
 while {[lshift args _]} { func $_ } ;# usage 1
 set elem [lshift elems] ;# usage 2

...similar proc's can be defined for the list-as-stack functions lpop, lunshift (lprepend?) and lpush (Oh, heck, that already exists ;). As a final thought, we can combine the above typical usage of K for object lifetime management with an idea from Perl:

 proc reset { varname } {
        upvar $varname var
        set tmp $var
        set var ""
        return $tmp
 }
 # ...
 set a [lrange [reset a] 1 end]

...possibly something to code up in C and add to TclX. This is a little too esoteric for the main core.

by booksandlibros - 2015-01-11

One other possibility is to use upvar. The important concept is to have the procedures behave as though they are on the same stack space. Yes, it will be slow.

proc push {inlist var} {
        upvar $inlist l
        return [ lappend l $var ]
}

proc pop {inlist} {
        upvar $inlist l
        if [llength $l] {
                lset l [lreplace $l end end]
        }
}

# Added this on 2015-01-11. Just in case you want the last value back.
proc popback {inlist} {
        upvar $inlist l
        # The documentation says I don't have to do this check for an empty list
        set  retval [lindex $l end]
        lset l [lreplace $l end end]
        return $retval
}

Are the concepts here that could be migrated into the stack and queue containers implemented in Tcllib's stack and queue?

RS replies: The concepts are old, and can be found in any CS textbook. The Tcllib modules are more heavyweight dedicated objects, while this educational page just deals with lists and access functions to them.

(insert ref to tcllib stack and queue documentation)

See cd for a simple stack example.