Priority Queue

A priority queue is a more specialized data structure than a stack or a queue.

However, it’s a useful tool in a surprising number of situations. Like an ordinary queue, a priority queue has a front and a rear, and items are removed from the front.

However, in a priority queue, items are ordered by key value so that the item with the lowest key (or in some implementations the highest key) is always at the front. Items are inserted in the proper position to maintain the order.

$ dart 03_stack_queue/priority_queue.dart

import 'dart:io';

class PriorityQueue {
  int maxSize;
  List<int> queueArray;
  int nItems;

  PriorityQueue(int s) {
    maxSize = s;
    queueArray = new List<int>(maxSize);
    nItems = 0;
  }

  /// Insert Data to Queue
  void insert(int item) {
    int j;
    if (nItems == 0) {
      queueArray[nItems++] = item;
    } else {
      for(j = nItems - 1; j >= 0; j --) {
        if(item > queueArray[j]) {
          queueArray[j + 1] = queueArray[j];
        } else {
          break;
        }
      }
      queueArray[j+1] = item;
      nItems ++;
    }
  }

  /// Remove data
  int remove() {
    return queueArray[--nItems];
  }

  int peekMin() {
    return queueArray[nItems - 1];
  }

  bool isEmpty() {
    return nItems == 0;
  }

  bool isFull() {
    return nItems == maxSize;
  }
}

void main() {
  PriorityQueue priorityQueue = new PriorityQueue(5);
  priorityQueue.insert(30);
  priorityQueue.insert(50);
  priorityQueue.insert(10);
  priorityQueue.insert(40);
  priorityQueue.insert(20);

  while(!priorityQueue.isEmpty()) {
    int item = priorityQueue.remove();
    stdout.write('$item ');
  }
}