在一次采访中，我被要求使用队列实现优先级队列，
面试结束后，我在谷歌上搜索了一下，发现它可以使用两个队列来实现，但我没有找到如何实现。。
请任何人给我解释一下。
提前谢谢。
使用优先级队列的主要优点是我们可以在恒定的时间内获得min/max。因此，这是应该满足的第一个标准。我们只考虑关键价值观。我们可以使用两个队列创建一个优先级队列，将它们命名为q1和q2如果输入元素大于q1的顶部，则将其附加到q1-else
如果输入小于q1的顶部，则重复
从q1中移除元素并插入到q2，直到顶部大于元素
现在添加元素
现在将剩余元素插入q2
so like input is 2 4 1 5 3
pass 1)
q1-> 2
q2->
pass 2)
q1-> 2 4
q2->
pass 3)
q1->
q2->1 2 4 // since 1 is less than top of q1 add it to q2 and then pop all the elements to q2
pass 4)
q1->
q2-> 1 2 4 5 //add it to q2 since it is larger than all the elements
pass 5)
q1-> 1 2 3 4 5//pop the elements smaller than q3 and then add the element and append the remaining
q2->
基本解决方案
使用两个队列
- 第一个仅包括所有元素
-
第二个包括第一个队列中元素的相应优先级。
-
插入：对于每个元素，将值插入第一个队列，并将其优先级插入第二个队列
nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp；时间复杂性O(1) -
获取顶部元素：在第二个队列中搜索最高优先级，第一个队列中的相应元素是优先级队列的顶部元素
nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp nbsp；时间复杂性O(n)
-
当然有几个选项。我能想到的第一个只使用1个队列，但假设您知道队列的大小。
复杂度不是很好，插入是线性的，弹出是恒定的。
下面是伪python 3代码。
class PriorityQueue(Queue):
def insert(self, item):
for i in range(self.size):
next = self.pop()
if next < item:
self.enqueue(next)
else:
self.enqueue(item)
self.enqueue(next)
break
for i in range(i, self.size):
self.enqueue(self.pop())
def pop(self):
return self.pop()
我使用了"self.pop"这个名称来从原始队列中获取第一个项目。"self.enqueue"将一个项目放在原始队列的末尾。
工作原理：插入从队列中取出所有较小的项目，并将它们放在最后。当新项目最小时，把那个放在最后。在那之后，把剩下的项目放在最后。
请注意，我没有在代码中放入详细信息，比如队列为空、可能已满的情况。。。这个代码不起作用，但它应该传达这个想法。
Python3:中的工作解决方案
from queue import Queue
class PriorityQueue(Queue):
def insert(self, item):
if self.empty():
self.put(item)
return
i = 0
size = self.qsize()
n = self.get()
while item > n and i < size:
self.put(n)
n = self.get()
i += 1
if i == size:
self.put(item)
self.put(n)
for i in range(size): self.put(self.get())
else:
self.put(item)
self.put(n)
for j in range(i + 1, size): self.put(self.get())
这是我遇到的一些问题。使用2个队列实现maxQueue
排队时间复杂性-O(1)排队时间复杂性-O(n)
java 中的代码
公共类_01_最大队列｛
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
}
public class QueueWithMax<T extends Comparable<T>> {
Queue<T> enteries = new ArrayDeque<T>();
Deque<T> candidatesForMax = new ArrayDeque<T>();
public void enqueue(T x) {
enteries.add(x);
if (candidatesForMax.peekLast().compareTo(x) < 0) {
candidatesForMax.removeLast();
}
candidatesForMax.addLast(x);
}
public T dequeue() {
if (!enteries.isEmpty()) {
T result = enteries.remove();
if (candidatesForMax.peekFirst().equals(result)) {
candidatesForMax.removeFirst();
}
return result;
}
throw new IllegalStateException("called Degueue() on empty Queue");
}
public T max() {
if (!candidatesForMax.isEmpty()) {
return candidatesForMax.peekFirst();
}
throw new NoSuchElementException("No element");
}
}
}