How to resolve the algorithm Priority queue step by step in the Action! programming language

Published on 12 May 2024 09:40 PM
#Action!

How to resolve the algorithm Priority queue step by step in the Action! programming language

Table of Contents

Problem Statement

A priority queue is somewhat similar to a queue, with an important distinction: each item is added to a priority queue with a priority level, and will be later removed from the queue with the highest priority element first. That is, the items are (conceptually) stored in the queue in priority order instead of in insertion order.

Create a priority queue.   The queue must support at least two operations:

Optionally, other operations may be defined, such as peeking (find what current top priority/top element is), merging (combining two priority queues into one), etc.

To test your implementation, insert a number of elements into the queue, each with some random priority. Then dequeue them sequentially; now the elements should be sorted by priority. You can use the following task/priority items as input data:

The implementation should try to be efficient.   A typical implementation has   O(log n)   insertion and extraction time,   where   n   is the number of items in the queue.
You may choose to impose certain limits such as small range of allowed priority levels, limited capacity, etc.   If so, discuss the reasons behind it.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Priority queue step by step in the Action! programming language

Source code in the action! programming language

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

You may also check:How to resolve the algorithm Table creation/Postal addresses step by step in the Visual FoxPro programming language
You may also check:How to resolve the algorithm Program termination step by step in the VBA programming language
You may also check:How to resolve the algorithm Image convolution step by step in the Wren programming language
You may also check:How to resolve the algorithm N'th step by step in the RPL programming language
You may also check:How to resolve the algorithm Pinstripe/Display step by step in the Locomotive Basic programming language