Priority queue: Difference between revisions

===Using ordered list (plus merge function)===

<syntaxhighlight lang="m2000 interpreter">

form 80, 42

Module OrdrerQueue (filename$) {

// f=-2 or use empty filename for screen

open filename$ for output as #f

zz=list

pq=List

flush

// subs can read from module's stack

println( "Add items to pq queue")

Data 4 ,"Feed cat",5 , "Make tea", 3, "Clear drains",1 , "Solve RC tasks"

AddItems(pq)

println("Add items to zz queue")

AddItems(zz, 2 , "Tax return", 1 ,"Solve RC tasks#2")

println( "Peek top from zz queue")

PeekTop(zz) // Solve RC tasks#2

println( "Merge two priority lists")

merge(pq, zz, false)

println("Peek top from pq queue")

PeekTop(pq) // Solve RC tasks

println("Add items to pq queue")

AddItems(pq, 1 ,"Solve RC tasks#3")

println("Peek top from pq queue")

PeekTop(pq) // Solve RC tasks

println("Pop one from pq until empty queue")

while len(pq)>0

PopOne(pq)

end while

println( "Pop one from zz until empty queue")

while len(zz)>0

PopOne(zz)

end while

close #f

sub AddItems(pq)

local s, z

while not empty

read z

if not exist(pq, z) then s=stack:append pq, z:=s else s=eval(pq)

read what$: stack s {data what$}

stack new {println( "add item",z,what$)}

end while

sort descending pq as number

Println()

end sub

sub merge(pq, qp, emptyqueue)

local needsort=false

local kqp=each(qp, -1, 1), k$

while kqp

local t=eval(kqp)

k$= eval$(kqp!)

if not exist(pq, eval$(kqp!)) then

p=stack

append pq, val(eval$(kqp!)):=p

needsort=true

else

local p=eval(pq)

end if

stack p {

if emptyqueue then

data !t

delete qp,eval$(kqp!)

else

data !stack(t)

end if

}

end while

if needsort then sort descending pq as number

end sub

sub PeekTop(pq)

Local k=len(pq)

if k=0 then exit sub

k=val(eval$(pq, k-1))

if exist(pq, k) then local s=eval(pq): println( k,stackitem$(s, 1))

End sub

Sub PopOne(pq)

Local k=len(pq)

if k<0 then exit sub

k=val(eval$(pq, k-1))

if exist(pq, k) then

local s=eval(pq)

println( k,stackitem$(s, 1))

if len(s)=1 then

delete pq, k

else

stack s {drop}

end if

end if

end sub

Sub println()

if empty then print #f, "": exit sub

while not empty

if islet then print #f, letter$;

if empty else print #f, " ";

if isnum then print #f, number;

if empty else print #f, " ";

end while

if f=-2 and pos=0 then exit sub

print #f, ""

end sub

}

OrdrerQueue ""

</syntaxhighlight>

{{out}}

<pre>Add items to pq queue

add item 4 Feed cat

add item 5 Make tea

add item 3 Clear drains

add item 1 Solve RC tasks

Add items to zz queue

add item 2 Tax return

add item 1 Solve RC tasks#2

Peek top from zz queue

1 Solve RC tasks#2

Merge two priority lists

Peek top from pq queue

1 Solve RC tasks

Add items to pq queue

add item 1 Solve RC tasks#3

Peek top from pq queue

1 Solve RC tasks

Pop one from pq until empty queue

1 Solve RC tasks

1 Solve RC tasks#2

1 Solve RC tasks#3

2 Tax return

3 Clear drains

4 Feed cat

5 Make tea

Pop one from zz until empty queue

1 Solve RC tasks#2

2 Tax return

</pre>