我正在尝试通过修改以前实现的接受泛型的队列来构建优先级队列。我创建了一个名为优先级队列(接受泛型(的类，该类扩展了我的队列类(接受泛型(。最后一个类是主要焦点，队列
我有一个测试类来测试我的比较器是否有效。我还设置了一个测试用例，以便我可以确保我的优先级队列在实现它时正常工作。
我的类用于测试我的比较器是否工作以及我的优先级队列在实现时是否工作：
public class TestCustomer {
public static void main(String args[]) {
Customer customer1 = new Customer(3000, 20, 5);
Customer customer2 = new Customer(5000, 15, 7);
Customer customer3 = new Customer(5000, 20, 5);
Customer customer4 = new Customer(3000, 3, 5);
Customer customer5 = new Customer(3000, 3, 8);
// comparator test
Customer.WorthComparator worth = new Customer.WorthComparator();
Customer.LoyaltyComparator loyal = new Customer.LoyaltyComparator();
Customer.WorthPoliteComparator polite = new Customer.WorthPoliteComparator();
assert worth.compare(customer1, customer2) == -1;
assert worth.compare(customer2, customer3) == 0;
assert worth.compare(customer2, customer1) == 1;
assert loyal.compare(customer1, customer2) == 1;
assert loyal.compare(customer2, customer1) == -1;
assert loyal.compare(customer1, customer3) == 0;
assert polite.compare(customer3, customer2) == -1;
assert polite.compare(customer2, customer3) == 1;
assert polite.compare(customer1, customer2) == -1;
assert polite.compare(customer2, customer3) == 1;
assert polite.compare(customer1, customer4) == 0;
// priority queue test
PriorityQueue<Customer> pQueueW = new PriorityQueue<Customer>(worth);
PriorityQueue<Customer> pQueueL = new PriorityQueue<Customer>(loyal);
PriorityQueue<Customer> pQueueP = new PriorityQueue<Customer>(polite);
// push -- type T, pass in a val // judgement upon worth
//PUSH customers for Worth
pQueueW.push(customer1);
pQueueW.push(customer2);
pQueueW.push(customer4);
assert pQueueW.pop() == customer2;
//PUSH customers for Loyalty
pQueueL.push(customer1);
pQueueL.push(customer2);
pQueueL.push(customer3);
assert pQueueL.pop() == customer1;
//PUSH customers for Polite
pQueueP.push(customer2);
pQueueP.push(customer4);
pQueueP.push(customer5);
assert pQueueP.pop() == customer2;
assert pQueueP.pop() == customer5;
//
}
}
我的优先级队列类只是扩展了队列并使用其推送功能。我需要创建一个方法来调用队列中的弹出式音乐：
import java.util.Comparator;
public class PriorityQueue<T> extends Queue<T>
{
Comparator<T> compare;
public PriorityQueue(Comparator<T> comp)
{
compare = comp;
}
//@Override
public void push(T val)
{
super.push(val); //right now this is just a normal Queue as it will do what its parent did.
}
我的客户类有一个用于创建客户的构造函数。这也是我实现我的不同比较器来创建客户排序的地方：
import java.util.Comparator;
public class Customer
{
int netWorth;
int yearsWithCompany;
int politeness;
public Customer(int netWorth,int yearsWithCompany,int politeness)
{
this.netWorth = netWorth;
this.yearsWithCompany = yearsWithCompany;
this.politeness = politeness;
}
/**
compares clients based on thier net worth
*/
public static class WorthComparator implements Comparator<Customer>
{
*/
public int compare(Customer c1, Customer c2)
{
int net1 = c1.netWorth;
int net2 = c2.netWorth;
if (net1 == net2) {
return 0;
}
else if (net1 < net2) {
return -1;
}
else {
return 1;
}
}
}
/**
compares clients based on thier loyalty
*/
public static class LoyaltyComparator implements Comparator<Customer>
{
/**
*/
public int compare(Customer c1, Customer c2)
{
int years1 = c1.yearsWithCompany;
int years2 = c2.yearsWithCompany;
if (years1 == years2) {
return 0;
}
else if (years1 < years2) {
return -1;
}
else {
return 1;
}
}
}
/**
compares clients based on thier net worth.
If there is a tie, politeness is used.
*/
public static class WorthPoliteComparator implements Comparator<Customer>
{
/**
*/
public int compare(Customer c1, Customer c2)
{
if (c1.netWorth == c2.netWorth)
{
if (c1.politeness < c2.politeness) {
return -1;
}
else if (c1.politeness > c2.politeness) {
return 1;
}
else {
return 0;
}
}
else if (c1.netWorth > c2.netWorth){
//int politeness = WorthComparator.compare(c1, c2);
//return politeness;
return 1;
}
else {
return -1 ;
}
}
}
}
我的队列类被实现为充当常规队列。我现在正在修改它，以便我可以将其转换为优先级队列。队列类如下所示： 公共类队列 {
public class QNode<T> {
private QNode<T> node;
private T val;
public QNode(QNode<T> node, T val) {
this.node = node;
this.val = val;
}
}
protected QNode<T> head;
protected QNode<T> rear;
protected QNode<T> temp;
public Queue()
{
head = null;
rear = null;
}
public void push(T val) // T = Customer type -- val is a customer
{
// if I wanted to get the contents out of val, which is a customer
// who has a net worth, years loyal, and politeness
// how would I access let's say, the netWorth from val?
// first node created
if (head == null && rear == null){
head = new QNode<T>(rear, val);
rear = head;
}
}
public T pop()
{
if (head == null){
throw new QueueUnderFlowException();
}
else if(head == rear) {
T temp_hold = head.val;
head = null;
rear = null;
return temp_hold;
}
else {
T oldN = head.val;
this.head = this.head.node;
return oldN;
}
}
/**
returns true if the queue is empty
*/
public boolean isEmpty()
{
if (head == null) {
return true;
}
else {
return false;
}
}
}
如果您的Queue是泛型的，则不能直接引用Customer的属性。您必须通过Queue知道的某些接口/基类来访问它们。由于Queue并不真正关心客户的净资产，而是关心不同客户之间的排序，因此有两种经典的方法可以做到这一点。
首先，您可以让Queue处理Comparable对象：
public class Queue<T extends Comparable<T>> {
// code...
并使Customer的净资产具有可比性：
public class Customer implements Comparable<Customer> {
@Override
public int compareTo(Customer other) {
return Integer.compare(netWorth, other.netWorth);
}
// rest of the code...
}
或者，如果你不想把这种自然顺序强加给Customer类，Queue类可以采用Comparator，例如Comparator.comparingInt(Customer::getNetWorth())构造时。