优先级队列构造函数

xoefb8l8  于 2021-07-09  发布在  Java
关注(0)|答案(0)|浏览(148)

我目前很难理解构造函数在优先级队列中的作用。我已经经历并为队列创建了peek、pop、length等方法,但是当涉及到构造函数时,我仍然坚持使用这些方法。这可能是一个精神障碍比什么。
我的班级如下:

public class PQueue<T> {

private PQueueItem<T> head;

public static enum ORDER {
    ASC, DESC;
}

public static ORDER DEFAULT_ORDER;
private ORDER order;

/**
 * The default constructor for a PQueue, with the default order for priorities
 */
public PQueue() {
    // ...add code
}

/**
 * The constructor to make a new PQueue with a given order
 * 
 * @param order
 */
public PQueue(ORDER order) {
    // ...add code
}

/**
 * Remove and return data from the item at the front of the queue
 * 
 * @return
 */
public T pop() {

    if(head == null) {
        return null;
    }
        // temp variable to hold head data
        T e1 = head.getData();
        // gives the next item the head
        head = head.getNext();
        // returns temp variable
        return e1;
}

/**
 * Return the data from the item at the front of the queue, without removing the
 * item itself
 * 
 * @return
 */
public T peek() {
    // returns head data
    if(head == null) {
        return null;
    }
    return head.getData();
}

/**
 * Remove and return the item at the front of the queue
 * 
 * @return
 */
public PQueueItem<T> popItem() {
    if (head == null) {
        return null;
    }
    // temp variable to hold item
    PQueueItem<T> e1 = this.head;
    // gives the next item the head
    this.head = head.getNext();
    // returns temp variable
    return e1;
}

/**
 * Return the item at the front of the queue without removing it
 * 
 * @return
 */
public PQueueItem<T> peekItem() {
    if (head == null) {
        return null;
    }
    return head;
}

/**
 * Insert a new item into the queue, which should be put in the right place
 * according to its priority. That is, is order == ASC, then the new item should
 * appear in the queue before all items with a HIGHER priority. If order ==
 * DESC, then the new item should appear in the queue before all items with a
 * LOWER priority.
 * 
 * @param data
 * @param priority
 */

public void insert(T data, int priority) {
    if (order == ORDER.ASC) {
        // current item
        PQueueItem<T> e1 = head;

        while (e1.getNext() != null) {

            // is inserted item greater than current item
            if (priority > e1.getPriority()) {

                // is inserted item smaller than next item
                if (priority < e1.getNext().getPriority()) {

                    // create and insert new item, reassign links in the list
                    PQueueItem<T> newPQ = new PQueueItem<T>(data, priority);
                    newPQ.setNext(e1.getNext());
                    e1.setNext(newPQ);
                }

                // check to see if priority equates to the next item's priority
                else if (priority == e1.getNext().getPriority()) {

                    // is new item's data alphabetically greater than the next item's data
                    if (((String) data).compareToIgnoreCase((String) e1.getNext().getData()) > 0) {
                        PQueueItem<T> nextPQ = e1.getNext();
                        PQueueItem<T> newPQ = new PQueueItem<T>(data, priority);
                        newPQ.setNext(nextPQ.getNext());
                        nextPQ.setNext(newPQ);
                    } else {
                        PQueueItem<T> newPQ = new PQueueItem<T>(data, priority);
                        newPQ.setNext(e1.getNext());
                        e1.setNext(newPQ);
                    }
                } else {

                    // iterate current item
                    e1 = head.getNext();
                }
            }

            // if item to be inserted is smaller than the current item
            else if (priority < e1.getPriority()) {
                PQueueItem<T> newPQ = new PQueueItem<T>(e1.getData(), e1.getPriority());
                newPQ.setNext(e1.getNext());
                e1.setData(data);
                e1.setPriority(priority);
            }
        }
    } else if (order == ORDER.DESC) {
        PQueueItem<T> e1 = head;
        while (e1.getNext() != null) {

            // is inserted item less than current item
            if (priority < e1.getPriority()) {

                // is inserted item greater than next item
                if (priority > e1.getNext().getPriority()) {

                    // create and insert new item, reassign links in the list
                    PQueueItem<T> newPQ = new PQueueItem<T>(data, priority);
                    newPQ.setNext(e1.getNext());
                    e1.setNext(newPQ);
                }

                // check to see if priority equates to the next item's priority
                else if (priority == e1.getNext().getPriority()) {

                    // is new item's data alphabetically less than the next item's data
                    if (((String) data).compareToIgnoreCase((String) e1.getNext().getData()) < 0) {
                        PQueueItem<T> nextPQ = e1.getNext();
                        PQueueItem<T> newPQ = new PQueueItem<T>(data, priority);
                        newPQ.setNext(nextPQ.getNext());
                        nextPQ.setNext(newPQ);
                    } else {
                        PQueueItem<T> newPQ = new PQueueItem<T>(data, priority);
                        newPQ.setNext(e1.getNext());
                        e1.setNext(newPQ);
                    }
                } else {

                    // iterate current item
                    e1 = head.getNext();
                }
            }

            // if item to be inserted is greater than the current item
            else if (priority > e1.getPriority()) {
                PQueueItem<T> newPQ = new PQueueItem<T>(e1.getData(), e1.getPriority());
                newPQ.setNext(e1.getNext());
                e1.setData(data);
                e1.setPriority(priority);
            }
        }

    }
}

/**
 * Return the length of the queue
 * 
 * @return
 */
public int length() {
    if (head == null) {
        return 0;
    } else {
    int size = 0;
    for (PQueueItem<T> i = head; i.getNext() != null; i = i.getNext()) {
        size++;
    }
    return size;
}
}

public String toString() {
    int i = length();
    PQueueItem<T> current = head;
    StringBuffer sb = new StringBuffer();
    while (i > 0) {
        sb.append(current.toString());
        if (i > 1)
            sb.append(": ");
        current = current.getNext();
        i--;
    }
    return sb.toString();
}

}

另外,当谈到代码时,我做了一些空检查,但是我读到有一种使用optional的方法,它更干净、更好。如果你有什么建议可以告诉我吗?
pqueitem的其他类如下所示:

public class PQueueItem<T> {

private int priority;
private T data;
private PQueueItem<T> next;

public PQueueItem(T data, int priority) {
    this.data = data;
    this.priority = priority;
}
public int getPriority() {
    return priority;
}
public void setPriority(int priority) {
    this.priority = priority;
}
public T getData() {
    return data;
}
public void setData(T data) {
    this.data = data;
}
public PQueueItem<T> getNext() {
    return next;
}
public void setNext(PQueueItem<T> next) {
    this.next = next;
}

public String toString() {
    return String.format("[%s,%d]", data.toString(), priority);
}

}

提前感谢,任何批评都会受到感激。

暂无答案!

目前还没有任何答案,快来回答吧!

相关问题