算法4 Java解答 2.4.21
Page content
2.4.21
问题：
2.4.21 Elementary data structures. Explain how to use a priority queue to implement the stack, queue, and randomized queue data types from Chapter 1
分析：
题目要求使一个优先队列。
假设使用MaxPQ优先队列的操作有 insert delMax isEmpty size
Stack：
那么对于Stack LIFO 的实现我们需要指定被后插入的元素的priority比之前插入的元素priority大。
Queue:
对于Queue FIFO 的实现，需要后插入元素的priority小于之前插入元素的priority。
randomized queue：
随机队列需要指定一个随机的priority，其余实现和处理Queue的方法一样。
问题是怎么样生成一个不重复的随机数呢？我的思路是使用一个Set保存随机数。
public int random() {
int num = 0;
while (!numSet.contains(num)) {
num = StdRandom.uniform(1, Integer.MAX_VALUE);
numSet.add(num);
break;
}
return num;
}
另外要提到的是对于使用MaxPQ实现的Stack和Queue，插入删除元素的时间复杂度都是lgN。
class IKey implements Comparable<IKey>{
Key value;
int priority;
@Override
public int compareTo(IKey another) {
return compare(this.priority, another.priority);
}
public int compare(int x, int y) {
return (x < y) ? -1 : ((x == y) ? 0 : 1);
}
}
参考：
https://stackoverflow.com/questions/4873472/how-to-implement-stack-using-priority-queue
