在一次面试中,我被要求使用队列实现优先队列。
面试后我搜索了一下,发现可以使用两个队列来实现,但是我没有找到具体的实现方法。
请问有人能够解释一下吗?
谢谢。
在一次面试中,我被要求使用队列实现优先队列。
面试后我搜索了一下,发现可以使用两个队列来实现,但是我没有找到具体的实现方法。
请问有人能够解释一下吗?
谢谢。
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->
一种基本解决方案
使用两个队列
第二个队列包含第一个队列中各元素的相应优先级。
插入:对于每个元素,将值插入到第一个队列中,其优先级插入到第二个队列中。
时间复杂度O(1)
获取顶部元素:在第二个队列中搜索最高优先级,第一个队列中相应的元素即为优先级队列的顶部元素。
时间复杂度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()
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
Dequeue时间复杂度 - O(1) Enqueue时间复杂度 - O(n)
Java代码
public class _01_MaximumQueue {
/**
* @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");
}
}
}
*First
和*Last
方法。 - Mika Feiler