[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 [lreplace $stack end-1 end]
return $res
}
======
Popping a '''queue''' is similarly structured, but with so different details
that I found no convenient way to factor out things:
Might have been the old style, but everything here seems a bit over done. I reworked the qpop slightly for clarity.
[MarcDouglas] 2020-02-23
======
proc qpop name {
upvar 1 $name queue
set res [lindex $queue 0]
set queue [lreplace $queue 0 0]
return $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 ''milli''seconds 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.
----
See also [Implementing FIFO queues]
[Containers]
<<categories>> Arts and crafts of Tcl-Tk programming | Concept | Data Structure