traditional
The autoinclude builtins/pqueue.e also implements more traditional queues and stacks.
A queue (aka FIFO or first in, first out) is exactly like the one in a shop, you don’t expect someone arriving after you to be served before you, nor do you expect to be served before people who where already there, whereas a stack (aka LIFO or last in first out) is exactly like a pile of plates in a kitchen, the ones on the top are regularly removed and replaced, whereas the ones at the bottom could be there for months or even years. Should you ever see the less common acronym LILO (last in last out), it is exactly the same as FIFO, and likewise FILO (first in last out) is the same as LIFO.
You could instead just use a standard sequence, which can be significantly faster (sometimes 15-fold), however the syntax can be a little less clear, and pop is usually two statements, eg/ie
There is nothing particularly clever or exciting about these implementations, and while they do strive to avoid any internal p2js violations, obviously should you modify a (local) variable that also has a copy somewhere in the stack or queue then that is precisely what you should expect, but at least it will be in your code, and therefore your responsibility (mwah-ha-ha-ha-har).
There is no attempt at any special optimisation, instead it relies on those which are inherent in the programming language itself. There are however nearly twice as many routine identifiers defined as strictly necessary, eg new_queue() and new_stack(), purely to try and help make your code a little more readable and self-documenting.
Since they are in fact using the same codebase, you can also "cheat" and peep/pop (but not push, since that gave me jip, and as it was probably not very useful I just ripped it/cheating out) the "wrong end" of both stacks and queues, should you ever feel the need to (and it won’t be subtle, you would have to stamp each and every such statement doing that sort of thing with the builtin constant FIFO_QUEUE or LIFO_QUEUE). On the other hand, should you want to get clever(/fast) you should just use a normal sequence.
Note that unlike priority queues and dictionaries there is no "default" queue or stack, since even the most trivial program simply reads better with explicit names, which as shown in the following example are always the first parameter to these routines, with the obvious exception of new_queue() and new_stack().
These routines are fully supported by pwa/p2js.
For comparison purposes I’ve shown what a priority queue pushing *10s would produce, and of course
the precise order isn’t particularly significant or important, I just wanted to demonstrate mixing.
The routines stack_size(), stack_empty(), and destroy_stack() exist purely to make code more self-documenting, it does no checking and does not really matter should you use them on a queue, or vice versa.
I suppose you could extract an entire queue or stack using popn(qid,queue_size(qid)), manipulate and then use pushn() to restore it, but that’s probably only even half sensible for the most exceptional of cases.
A queue (aka FIFO or first in, first out) is exactly like the one in a shop, you don’t expect someone arriving after you to be served before you, nor do you expect to be served before people who where already there, whereas a stack (aka LIFO or last in first out) is exactly like a pile of plates in a kitchen, the ones on the top are regularly removed and replaced, whereas the ones at the bottom could be there for months or even years. Should you ever see the less common acronym LILO (last in last out), it is exactly the same as FIFO, and likewise FILO (first in last out) is the same as LIFO.
You could instead just use a standard sequence, which can be significantly faster (sometimes 15-fold), however the syntax can be a little less clear, and pop is usually two statements, eg/ie
x = todo[1] and
todo = todo[2..$], or maybe {x,todo} = {todo[1],todo[2..$]},
that is as opposed to just x = pop(todo), and of course if the stack/queue
is not a performance bottleneck, even a tiny bit more code clarity wins hands down.
There is nothing particularly clever or exciting about these implementations, and while they do strive to avoid any internal p2js violations, obviously should you modify a (local) variable that also has a copy somewhere in the stack or queue then that is precisely what you should expect, but at least it will be in your code, and therefore your responsibility (mwah-ha-ha-ha-har).
There is no attempt at any special optimisation, instead it relies on those which are inherent in the programming language itself. There are however nearly twice as many routine identifiers defined as strictly necessary, eg new_queue() and new_stack(), purely to try and help make your code a little more readable and self-documenting.
Since they are in fact using the same codebase, you can also "cheat" and peep/pop (but not push, since that gave me jip, and as it was probably not very useful I just ripped it/cheating out) the "wrong end" of both stacks and queues, should you ever feel the need to (and it won’t be subtle, you would have to stamp each and every such statement doing that sort of thing with the builtin constant FIFO_QUEUE or LIFO_QUEUE). On the other hand, should you want to get clever(/fast) you should just use a normal sequence.
Note that unlike priority queues and dictionaries there is no "default" queue or stack, since even the most trivial program simply reads better with explicit names, which as shown in the following example are always the first parameter to these routines, with the obvious exception of new_queue() and new_stack().
These routines are fully supported by pwa/p2js.
Example:
integer pten = new_queue()
sequence res = {}
for i=1 to 25 do
push(pten,get_prime(i)) -- {2,3,5,7,11,...}
res &= pop(pten)
push(pten,res[$]*10) -- {20,200,30,2000,50,300,...} (kinda, you get the idea)
end for
destroy_queue(pten)
printf(1,"The first 13 primes mixed in with primes*some power of 10 are:\n")
pp(res) -- {2,20,3,200,5,30,7,2000,11,50,13,300,17,70,19,20000,23,110,29,500,31,130,37,3000,41}
-- vs pq: {2,3,5,7,11,13,17,19,20,23,29,30,31,37,41,43,47,50,53,59,61,67,70,71,73,79,83,89,97}
constants
The following constants are automatically defined (in psym.e/syminit).|
| = 0 -- (intended for internal use) |
| FIFO_QUEUE | = 1 |
|
| = 2 |
routines
| integer qid = |
|
| |
| object item = |
pop(integer qid, n=-1, qtype=ANY_QUEUE, bool bPop=true) -- remove next from queue/stack peep(integer qid, n=-1, qtype=ANY_QUEUE) -- inspect head of queue/stack Note that top is a reserved word/predefined function in JavaScript. |
|
|
popn(integer qid, n, qtype=ANY_QUEUE) -- pop() multiple items. peepn(integer qid, n, qtype=ANY_QUEUE) -- peep() multiple items. |
| integer res = |
queue_size(integer qid) -- return the size of a queue stack_size(integer qid) -- return the size of a stack |
| bool res = |
queue_empty(integer qid) -- yields true/false stack_empty(integer qid) -- yields true/false |
|
destroy_queue(integer pqid) -- release a queue for reuse destroy_stack(integer pqid) -- release a stack for reuse |
The routines stack_size(), stack_empty(), and destroy_stack() exist purely to make code more self-documenting, it does no checking and does not really matter should you use them on a queue, or vice versa.
I suppose you could extract an entire queue or stack using popn(qid,queue_size(qid)), manipulate and then use pushn() to restore it, but that’s probably only even half sensible for the most exceptional of cases.