Data Structures

Home   Index

Queue

A queue is an abstract data type that functions with a first in, first out policy. A priority queue is a queue that checks its elements for “VIP” points. If an element that has been added has more “VIP” points than the next element in the queue, it goes in front of it, until it is either in the front of the queue or the next element in front of it has the same or more “VIP” points.
Create an array of fixed length. Set a variable “front” to 0 indicating the start of the queue. Set a variable “end” to 0 indicating the end of the queue. It is important to leave an element unassigned in the queue, called the sentinel, so that you can tell the difference between an empty queue and a full queue. You can then create these methods:

Java example of a queue

import java.lang.String;
import java.lang.Boolean;

public class Queue
{
    private String[] _array;
    private int _max;
    private int _front = 0;
    private int _end = 0;

    public Queue()
    {
        _array = new String[11];
        _max = 11;
    }

    public Queue(int size)
    {
        _array = new String[size + 1];
        _max = size + 1;
    }
    
    public Boolean Enqueue(String element)
    {
        if (this.Size() < this._max - 1)
        {
            if (this._end == this._max - 1)
            {
                this._array[this._end] = element;
                this._end = 0;
                return true;
            }
            else
            {
                this._array[this._end] = element;
                this._end++;
                return true;
             }
        }
        return false;
    }
    
    public String Dequeue()
    {
        if (!this.IsEmpty())
        {
            if (this._front == this._max - 1)
            {
                this._front = 0;
                return this._array[this._max - 1];
            }
            else
            {
                this._front++;
                return this._array[this._front - 1];
            }
        }
        return "";
    }
    
    public int Size()
    {
        if (this._end >= this._front)
        {
            return this._end - this._front;
        }
        else
        {
            return (this._max - this._front) + this._end;
        }
    }
    
    public Boolean IsEmpty()
    {
        if (this._front == this._end) return true;
        return false;
    }
    
    public String Peek()
    {
        if (!this.IsEmpty()) return this._array[this._front];
        return null;
    }
    
    public String ToString()
    {
        String elements = "The elements in this queue are [";
        if (this._end >= this._front)
        {
            for (int i = this._front; i < this._end; i++)
            {
                if (i != 0) elements += ", ";
                elements += this._array[i];
            }
        }
        else
        {
            for (int i = this._front; i < this._max; i++)
            {
                if (i != this._front) elements += ", ";
                elements += this._array[i];
            }
            for (int i = 0; i < this._end; i++)
            {
                elements += ", " + this._array[i];
            }
        }
        elements += "]";
        return elements;
    }
}
Previous   Next