How to Implement Priority Queue Class Using Array

Items are popped from the front of a queue one by one, just like waiting in line.

A queue stores data in sequence and contains two functions: push and pop. Push places an item at the end of the queue; pop removes the item at the front and returns it. A priority queue behaves similarly, with one difference: push adds items to the queue in a certain order. Arrays are not ideal for a priority queue; they lack flexibility, making it difficult to sort the queue. However, they are useful for learning the concept.

Instructions

1. Choose the data type your priority queue holds. If this is your first time writing a priority queue, choose something simple, such as an integer.

2. Create an array to serve as your queue. If your data type is integer, and you wish to hold 10 items, your array will be created using code like this:

   int[] arr = new int[10];

   Keep in mind that 0 is the first index of any array. To access the first index of arr, you would refer to arr[0], and arr[9] would access the last index of arr. In this case, arr[10] causes an error.

3. Determine the sorting function. It will be used later to push items in the correct order. This function takes two inputs, then compares them. If the first input has a higher value, the function returns 1; if both inputs have the same value, it returns 0; and if the first input has a lower value, it returns -1. If this is your first time writing a sorting function, and your data type of choice is integer, you should start with numerical order, in which lower numbers have a lower value. Sorting by numerical value, the code will look like this:

   if (first > second) return 1;

   if (first == second) return 0;

   if (first < second) return -1;

   This also works for other number data types, such as doubles and floats. If you are using strings, you could sort by alphabetical order.

4. Start the push function. This takes one input, the item to push on the queue, and outputs nothing. In Java, if your data type is integer, your code will look like this:

   public void push(int in)

   Your code will look similar in most other programming languages, including C and C++. "Void" means that this function will output nothing.

5. Create an array of the same size as the array you use for your queue. If your current array can hold 10 integers, you will create an array like this:

   int[] secondArray = new int[10];

   This second array will later become your queue. If the last entry in your array is full, this means that you have used every entry in the array; you should instead create an array that is one entry larger.

6. Compare the input to each item in your array, starting with the first, using the sort function. Always make push's input the first item you place in the sort function. To compare push's input and the first item from arr, your code will look like this:

   sort(in, arr[0]);

   Here, "in" is the name given to the input variable from step 4.

   If this returns -1, put push's input in the second array:

   secondArray[0] = in;

   Otherwise, copy the item from the first array into the second array:

   secondArray[0] = arr[0];

   Then compare push's input to the next item in the first array:

   sort(in, arr[1]);

   Continue this until push's input is inserted in the second array or until there are no more items in the first array. In the latter case, place push's input as the next item in the second array.

7. Copy the rest of the items from the first array into the second array. Now that push's input has been placed in the second array, you have no need for the sort function. From now on, use the second array rather than the first; the first array is now outdated. With this, the push function is complete.

8. Write the pop function. This takes no inputs, but it outputs one item from your queue. If your data type is integer, your code will look like this:

   public int pop()

   The second word, "int," means that this function will output an integer.

9. Create a second array of the same size as your current array. Then, copy the second item from the first array into the first entry in the second array, the third item into the second array's second entry, and so on and so forth, until there are no more entries. Do not copy the first item in the first array. If your array contains 4 items, your code will look like this:

   secondArray[0] = arr[1];

   secondArray[1] = arr[2];

   secondArray[2] = arr[3];

   Recall that the first index of an array is 0. This means that secondArray[0] is the first item of secondArray, and arr[1] is the second item of arr.

10. Return the first item from the first array. Your code will look like this:

    return arr[0];

    As with the push function, the second array is now your queue. The pop function is now complete.

References

• The LEDA Tutorial: Chapter 4. Priority queues

Resources

• JavaClass.info: Priority Queue in Java