使用链表实现优先队列 [英] Use a linked list to implement a Priority Queue

问题描述

我已经使用链表实现了一个优先级队列.在这个优先级队列中，最小的 int 值具有最高的值，因此通过调用 remove 方法将删除最小的方法.

I have implemented a priority queue using a linked list. In this priority queue the smallest int value has the highest value and therefore by calling the remove method the smallest method will be removed.

节点类代码

public class Node {

    public int iData;
    public Node next;

    public Node(int x) {
        iData = x;
    }

    public void displayNode() {
        System.out.println(iData + " ");
    }

}

链接列表代码

public class LinkList {

    private Node first;

    public LinkList() {
        first = null;
    }

    public boolean isEmpty() {
        return first == null;
    }

    public void insert(int x) {
        Node newNode = new Node(x);
        Node previous = null;
        Node current = first;

        while (current != null && x < current.iData) {
            previous = current;
            current = current.next;
        }

        if (previous == null) {
            newNode.next = first;
            first = newNode;
        }

        else {
            previous.next = newNode;
            newNode.next = current;
        }
    }

    public Node remove() {
        Node previous = null;
        Node current = first;
        Node temp = current;

        while (current.next != null) {
            previous = current;
            current = current.next;
        }

        previous.next = null;

        return temp;
    }

    public void display() {
        Node current = first;

        while (current != null) {
            current.displayNode();
            current = current.next;
        }

        System.out.println(" ");
    }

}

优先队列代码

public class PriorityQ {

    private LinkList list;

    public PriorityQ() {
        list = new LinkList();
    }

    public void insert(int x) {
        list.insert(x);
    }

    public void remove() {
        list.remove();

    }

    public void displayList() {
        System.out.println("Largest Value to Smallest");
        list.display();
    }

}

目前工作正常，但是我不确定链接列表类中的 remove 方法是否是删除元素的最佳方法.所以我正在寻找建议.

It is working fine at the moment, however i am not sure if my remove method in the link list class is the best way to go about removing elements. So i am looking for suggestions.

推荐答案

remove() 应该从列表中删除第一个元素，对吗?你为什么要为此循环任何东西?

remove() is supposed to remove the first element from the list, right? Why do you loop anything for that?

由于您的列表是单链接的(仅指向节点中的下一个元素)，您需要做的就是:

Since your list is singly-linked (only pointing to next elements in the Node) all you need to do is:

1. 将 first 存储在一个临时变量中(如果它是 != null)

1. Store the first in a temporary variable (if it's != null)

然后更新 first 指向列表中的第二项(first.next 如果 != null)

Then update first to be pointing to the 2nd item in the list (first.next if != null)

然后返回临时变量.

这篇关于使用链表实现优先队列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！