[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
 }
----
[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.
----
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.

----

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.
----
See [cd] for a simple stack example.
----
See also [Implementing FIFO queues]
----
[[
[Arts and crafts of Tcl-Tk programming] |
[Category Concept] |
[Category Data Structure] |
]]