Priority queue: Difference between revisions
Content deleted Content added
Added solution for Action! |
|||
Line 431: | Line 431: | ||
Priority : 4 : Feed cat |
Priority : 4 : Feed cat |
||
Priority : 5 : Make tea |
Priority : 5 : Make tea |
||
</pre> |
|||
=={{header|Action!}}== |
|||
The user must type in the monitor the following command after compilation and before running the program!<pre>SET EndProg=*</pre> |
|||
{{libheader|Action! Tool Kit}} |
|||
<lang Action!>CARD EndProg ;required for ALLOCATE.ACT |
|||
INCLUDE "D2:ALLOCATE.ACT" ;from the Action! Tool Kit. You must type 'SET EndProg=*' from the monitor after compiling, but before running this program! |
|||
DEFINE PTR="CARD" |
|||
DEFINE NODE_SIZE="5" |
|||
TYPE QueueNode=[ |
|||
BYTE priority |
|||
PTR data ;CHAR ARRAY |
|||
PTR nxt] |
|||
QueueNode POINTER queueFront,queueRear |
|||
BYTE FUNC IsEmpty() |
|||
IF queueFront=0 THEN |
|||
RETURN (1) |
|||
FI |
|||
RETURN (0) |
|||
PROC Push(BYTE p CHAR ARRAY d) |
|||
QueueNode POINTER node,curr,prev |
|||
node=Alloc(NODE_SIZE) |
|||
node.priority=p |
|||
node.data=d |
|||
node.nxt=0 |
|||
IF IsEmpty() THEN |
|||
queueFront=node |
|||
queueRear=node |
|||
RETURN |
|||
FI |
|||
curr=queueFront |
|||
prev=0 |
|||
WHILE curr#0 AND curr.priority<=p |
|||
DO |
|||
prev=curr |
|||
curr=curr.nxt |
|||
OD |
|||
IF prev=0 THEN |
|||
queueFront=node |
|||
ELSEIF curr=0 THEN |
|||
queueRear.nxt=node |
|||
queueRear=node |
|||
ELSE |
|||
prev.nxt=node |
|||
FI |
|||
node.nxt=curr |
|||
RETURN |
|||
PTR FUNC Pop() |
|||
QueueNode POINTER node |
|||
IF IsEmpty() THEN |
|||
PrintE("Error: queue is empty!") |
|||
Break() |
|||
FI |
|||
node=queueFront |
|||
queueFront=node.nxt |
|||
RETURN (node) |
|||
PROC TestIsEmpty() |
|||
IF IsEmpty() THEN |
|||
PrintE("Queue is empty") |
|||
ELSE |
|||
PrintE("Queue is not empty") |
|||
FI |
|||
RETURN |
|||
PROC TestPush(BYTE p CHAR ARRAY d) |
|||
PrintF("Push priority=%B task=%S%E",p,d) |
|||
Push(p,d) |
|||
RETURN |
|||
PROC TestPop() |
|||
QueueNode POINTER node |
|||
node=Pop() |
|||
PrintF("Pop priority=%B task=%S%E",node.priority,node.data) |
|||
Free(node,NODE_SIZE) |
|||
RETURN |
|||
PROC Main() |
|||
AllocInit(0) |
|||
queueFront=0 |
|||
queueRear=0 |
|||
Put(125) PutE() ;clear screen |
|||
TestIsEmpty() |
|||
TestPush(3,"Clear drains") |
|||
TestPush(4,"Feed cat") |
|||
TestPush(5,"Make tea") |
|||
TestPush(1,"Solve RC tasks") |
|||
TestPush(2,"Tax return") |
|||
TestIsEmpty() |
|||
TestPop() |
|||
TestPop() |
|||
TestPop() |
|||
TestPop() |
|||
TestPop() |
|||
TestIsEmpty() |
|||
RETURN</lang> |
|||
{{out}} |
|||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Priority_queue.png Screenshot from Atari 8-bit computer] |
|||
<pre> |
|||
Queue is empty |
|||
Push priority=3 task=Clear drains |
|||
Push priority=4 task=Feed cat |
|||
Push priority=5 task=Make tea |
|||
Push priority=1 task=Solve RC tasks |
|||
Push priority=2 task=Tax return |
|||
Queue is not empty |
|||
Pop priority=1 task=Solve RC tasks |
|||
Pop priority=2 task=Tax return |
|||
Pop priority=3 task=Clear drains |
|||
Pop priority=4 task=Feed cat |
|||
Pop priority=5 task=Make tea |
|||
Queue is empty |
|||
</pre> |
</pre> |
||