队列
队列与堆栈一样，是列表的特化。它是建立在先进先出的基础上的——先进先出，这意味着先进先出。换句话说，队列中“最年长”的人先离开，为了更好地理解，请考虑银行队列。
⚠️
队列应用：操作系统中的进程管理；并发编程中任务之间的通信；计算机网络（打印）；响应 Web 服务器上的请求
队列本身只允许在末端直接操作数据。
public interface Queue<E> {
void enqueue(E value); //enfileira
E dequeue(); //remove e desenfileira
E first(); //retorna primeiro elemento
int size(); //algumas literaturas se chama lenght()
boolean isEmpty();
}
登录后复制
登录后复制
登录后复制
优先队列
这类似于日常排队的行为，但现在考虑一下您在银行排队，一位女士进入队列，每个人都让她先进，因为她年纪更大，所以有更大的优先级。
在优先级队列数据结构中，每个节点都有一个Key-Value，Key是存储其优先级的键，Value是节点的值。默认情况下，Java 中的 Key 最初是数字，程序员可以稍后更改。
Key和Value的集合称为Entry，所以这个E.D的接口发生了变化。其他细节是：Key一旦定义，就不能更改。如果两个节点的 Key 中的优先级值相同，则程序员选择规则。
public interface PriorityQueueOg<K,V> {
void insert(K key, V value);
Entry<K,V> remove();
int size();
boolean isEmpty();
}
登录后复制
登录后复制
登录后复制
在接下来的结构中，我们将使用 Node 和 Entry 类、first、last 和 size 属性以及 CompareTo
优先级队列分为两种：已排序（Sorted Priority Queue）和未排序（Unorted Priority Queue）
排序优先级队列
有序列表负责将节点插入到正确的位置，因此删除很容易，只需删除第一个（如果执行 E.D 的程序员定义最高优先级元素应该位于开头）
为了知道哪个节点具有最高优先级，我们使用compareTo，这是一个集合函数，通过它的返回，我们可以获得执行此 E.D 的关键结果，如果返回是：
-
否定：如果调用该方法的对象比作为参数传递的对象“小”。
-
零：如果对象相等。
-
正： 如果调用该方法的对象比作为参数传递的对象“更大”。
插入
要进入，您必须检查一些事项
第一步 → 创建一个新节点
Node newNode = new Node(key, value)
登录后复制
登录后复制
登录后复制
第二步 → 检查 Queue 是否为空，如果是，则将 Head 和 Last 作为新节点，考虑到它将是唯一的
public interface Queue<E> {
void enqueue(E value); //enfileira
E dequeue(); //remove e desenfileira
E first(); //retorna primeiro elemento
int size(); //algumas literaturas se chama lenght()
boolean isEmpty();
}
登录后复制
登录后复制
登录后复制
第三步 → 如果它不是列表中的唯一元素，则必须检查新节点是否比第一个节点具有更高的优先级。
public interface PriorityQueueOg<K,V> {
void insert(K key, V value);
Entry<K,V> remove();
int size();
boolean isEmpty();
}
登录后复制
登录后复制
登录后复制
第三步 → 然后与列表中的最后一个元素进行比较
Node newNode = new Node(key, value)
登录后复制
登录后复制
登录后复制
第四步 → 如果没有其他的，就只剩下中间了！为此，我们需要制作一个辅助节点放在 newNode (nN) 的前面并比较两者，当 auxNode 指向空时，或者当 nN 大于 auxNode 时（较大，因此它），比较结束排在后面）。这个 while 用于 aux 四处比较两个节点的值，当找到时，将 nN 放在 auxNode 后面
if(isEmpty()){
first = newNode;
last = newNode;
}else{
登录后复制
登录后复制
消除
Sorted 中的删除方法要简单得多，因为正如已经提到的，队列已经为其组织好了。
第一步 → 由于每个 Remove 方法都会返回要删除的元素，因此该步骤将创建一个 Entry （为什么不是节点？）
if(compare(newNode, first)<0){
//Se o nN for menor que o F
//Levando em consideração que a prioridade maior é 0
//Se o nN for menor que F, ele será o de maior prioridade pegando o lugar do primeiro
newNode.next = first;
first.previous = newNode;
first = newNode;
}
登录后复制
登录后复制
第二步 → 然后，由于您已经要消除第一个节点，只需将 First 指向 First 旁边的节点即可
}else if(compare(newNode, last)>=0){
//Se o nN for maior que o L
//Significa que o número de nN é maior que L
//Então bota o nN para ultimo
newNode.previous=last;
last.next=newNode;
last = newNode;
}else{
登录后复制
登录后复制
第三步 → 检查队列中是否只有一个元素，因为如果是，队列将为空！然后你必须将 F 和 L 设置为 null
}else{
//se nao for nada, está no meio
//entao temos que achar entre qual dos meios
Node auxNode = first;
while(compare(newNode, auxNode)>0 && auxNode.next!=null){
//enquanto o newNode tiver prioridade maior que o auxiliar
//e o auxiliar tiver um proximo
auxNode = auxNode.next;
}
newNode.next = auxNode;
newNode.previous = auxNode.previous;
}
}
登录后复制
登录后复制
第四步 → 如果它不是唯一的元素，则意味着还有其他元素！因此，当您在步骤 2 中删除第一个时，之前的第一个仍然与前一个连接，所以我们必须：
Entry<K,V> max = maxPriority();
登录后复制
登录后复制
最大优先级
返回列表中优先级最高的元素的方法，由于我们是按顺序排列的，因此它只返回第一个元素。
first = first.next;
登录后复制
渐近分析
| Método |
O(_) |
| size |
O(1) |
| isEmpty |
O(1) |
| insert |
O(n) |
| remove |
O(1) |
| maxPriority |
O(1) |
未排序的优先级队列
无序队列和有序队列有很大不同！让我们从他的方法开始：
插入
要添加到unsorted、like和disordered中，你不需要担心这个新元素会在哪里，只需将它添加到最后即可！
第一步→检查列表是否为空，因为如果是，则要添加的节点将是第一个（First）和最后一个（Last）
public interface Queue<E> {
void enqueue(E value); //enfileira
E dequeue(); //remove e desenfileira
E first(); //retorna primeiro elemento
int size(); //algumas literaturas se chama lenght()
boolean isEmpty();
}
登录后复制
登录后复制
登录后复制
第二步→如果不为空，只需在最后添加这个节点即可！
public interface PriorityQueueOg<K,V> {
void insert(K key, V value);
Entry<K,V> remove();
int size();
boolean isEmpty();
}
登录后复制
登录后复制
登录后复制
最大优先级
Unsorted 中的移除比 Sorted 中的那几行代码要复杂得多......
“为什么？”你问，我们应该使用一种名为 maxPriority 的方法（在其他版本中也简单得多），其目标是找到具有最高优先级的节点。以前是用简单的几行代码来教导的，现在，因为我们不知道这个最高优先级的节点实际上在哪里，所以我们必须遍历整个队列来寻找它！因此，在我们研究remove本身之前，我们先看看maxPriority。
第一步 → 每当我们想要遍历一个数据结构时，我们需要两个节点：一个是始终前进的辅助节点，另一个是我们想要实现的节点（在本例中是 MaxPriority）
Node newNode = new Node(key, value)
登录后复制
登录后复制
登录后复制
第二步 → 这两个将在一个节点内运行，只有当 aux 达到 null（队列末尾）时才结束。比较这些节点，如果为负数，说明aux小于max，所以max最大，更新max节点的值，然后让aux运行。
if(isEmpty()){
first = newNode;
last = newNode;
}else{
登录后复制
登录后复制
消除
第一步 → 在所有 emove 中，创建一个变量来存储将被删除的节点。在这种情况下，您已经知道哪一个将被删除，因为您正在调用 maxPriority
方法
if(compare(newNode, first)<0){
//Se o nN for menor que o F
//Levando em consideração que a prioridade maior é 0
//Se o nN for menor que F, ele será o de maior prioridade pegando o lugar do primeiro
newNode.next = first;
first.previous = newNode;
first = newNode;
}
登录后复制
登录后复制
第二步 → 然后检查它是否是唯一的元素，如果是，则 F 和 L 为空！
}else if(compare(newNode, last)>=0){
//Se o nN for maior que o L
//Significa que o número de nN é maior que L
//Então bota o nN para ultimo
newNode.previous=last;
last.next=newNode;
last = newNode;
}else{
登录后复制
登录后复制
第3步→如果不是唯一的，还有其他选择：如果max是最后一个，则消除最后一个，如果是第一个，则消除第一个，如果不是两个两个，则在中间！
}else{
//se nao for nada, está no meio
//entao temos que achar entre qual dos meios
Node auxNode = first;
while(compare(newNode, auxNode)>0 && auxNode.next!=null){
//enquanto o newNode tiver prioridade maior que o auxiliar
//e o auxiliar tiver um proximo
auxNode = auxNode.next;
}
newNode.next = auxNode;
newNode.previous = auxNode.previous;
}
}
登录后复制
登录后复制
第四步 → 如果它在中间，则必须移除人群中的最大值，当没有其他人指向它时，就会发生这种情况。
Entry<K,V> max = maxPriority();
登录后复制
登录后复制
渐进分析
| Método |
O(_) |
| size |
O(1) |
| isEmpty |
O(1) |
| insert |
O(1) |
| remove |
O(n) |
| maxPriority |
O(n) |
以上是优先队列！我们来分解一下，了解一下数据结构的这一部分。的详细内容。更多信息请关注PHP中文网其他相关文章！
