Dados los Nodes con su prioridad, implemente una cola de prioridad usando una lista doblemente enlazada.
Requisito previo: cola de prioridad
- push(): esta función se utiliza para insertar nuevos datos en la cola.
- pop(): esta función elimina el elemento con el valor de prioridad más bajo de la cola.
- peek() / top(): esta función se usa para obtener el elemento de menor prioridad en la cola sin eliminarlo de la cola.
Acercarse :
1. Cree una lista doblemente enlazada que tenga los campos info (mantiene la información del Node), prioridad (mantiene la prioridad del Node), anterior (apunta al Node anterior), siguiente (apunta al siguiente Node).
2. Inserte el elemento y la prioridad en el Node.
3. Organice los Nodes en orden creciente de prioridad.
A continuación se muestra la implementación de los pasos anteriores:
C++
// C++ code to implement priority
// queue using doubly linked list
#include <bits/stdc++.h>
using namespace std;
// Linked List Node
struct Node {
int info;
int priority;
struct Node *prev, *next;
};
// Function to insert a new Node
void push(Node** fr, Node** rr, int n, int p)
{
Node* news = (Node*)malloc(sizeof(Node));
news->info = n;
news->priority = p;
// If linked list is empty
if (*fr == NULL) {
*fr = news;
*rr = news;
news->next = NULL;
}
else {
// If p is less than or equal front
// node's priority, then insert at
// the front.
if (p <= (*fr)->priority) {
news->next = *fr;
(*fr)->prev = news->next;
*fr = news;
}
// If p is more rear node's priority,
// then insert after the rear.
else if (p > (*rr)->priority) {
news->next = NULL;
(*rr)->next = news;
news->prev = (*rr)->next;
*rr = news;
}
// Handle other cases
else {
// Find position where we need to
// insert.
Node* start = (*fr)->next;
while (start->priority > p)
start = start->next;
(start->prev)->next = news;
news->next = start->prev;
news->prev = (start->prev)->next;
start->prev = news->next;
}
}
}
// Return the value at rear
int peek(Node* fr) { return fr->info; }
bool isEmpty(Node* fr) { return (fr == NULL); }
// Removes the element with the
// least priority value form the list
int pop(Node** fr, Node** rr)
{
Node* temp = *fr;
int res = temp->info;
(*fr) = (*fr)->next;
free(temp);
if (*fr == NULL)
*rr = NULL;
return res;
}
// Driver code
int main()
{
Node *front = NULL, *rear = NULL;
push(&front, &rear, 2, 3);
push(&front, &rear, 3, 4);
push(&front, &rear, 4, 5);
push(&front, &rear, 5, 6);
push(&front, &rear, 6, 7);
push(&front, &rear, 1, 2);
cout << pop(&front, &rear) << endl;
cout << peek(front);
return 0;
}
C
// C code to implement priority
// queue using doubly linked list
#include <stdio.h>
#include <stdlib.h>
// Linked List Node
struct Node {
int info;
int priority;
struct Node *prev, *next;
};
// Function to insert a new Node
void push(struct Node** fr, struct Node** rr, int n, int p)
{
struct Node* news
= (struct Node*)malloc(sizeof(struct Node*));
news->info = n;
news->priority = p;
// If linked list is empty
if (*fr == NULL) {
*fr = news;
*rr = news;
news->next = NULL;
}
else {
// If p is less than or equal front
// node's priority, then insert at
// the front.
if (p <= (*fr)->priority) {
news->next = *fr;
(*fr)->prev = news->next;
*fr = news;
}
// If p is more rear node's priority,
// then insert after the rear.
else if (p > (*rr)->priority) {
news->next = NULL;
(*rr)->next = news;
news->prev = (*rr)->next;
*rr = news;
}
// Handle other cases
else {
// Find position where we need to
// insert.
struct Node* start = (*fr)->next;
while (start->priority > p)
start = start->next;
(start->prev)->next = news;
news->next = start->prev;
news->prev = (start->prev)->next;
start->prev = news->next;
}
}
}
// Return the value at rear
int peek(struct Node* fr) { return fr->info; }
int isEmpty(struct Node* fr) { return (fr == NULL); }
// Removes the element with the
// least priority value form the list
int pop(struct Node** fr, struct Node** rr)
{
struct Node* temp = *fr;
int res = temp->info;
(*fr) = (*fr)->next;
free(temp);
if (*fr == NULL)
*rr = NULL;
return res;
}
// Driver code
int main()
{
struct Node *front = NULL, *rear = NULL;
push(&front, &rear, 2, 3);
push(&front, &rear, 3, 4);
push(&front, &rear, 4, 5);
push(&front, &rear, 5, 6);
push(&front, &rear, 6, 7);
push(&front, &rear, 1, 2);
printf("%d\n", pop(&front, &rear));
printf("%d\n", peek(front));
return 0;
}
Java
// Java code to implement priority
// queue using doubly linked list
import java.util.*;
class Solution {
static Node front, rear;
// Linked List Node
static class Node {
int info;
int priority;
Node prev, next;
}
// Function to insert a new Node
static void push(Node fr, Node rr, int n, int p)
{
Node news = new Node();
news.info = n;
news.priority = p;
// If linked list is empty
if (fr == null) {
fr = news;
rr = news;
news.next = null;
}
else {
// If p is less than or equal front
// node's priority, then insert at
// the front.
if (p <= (fr).priority) {
news.next = fr;
(fr).prev = news.next;
fr = news;
}
// If p is more rear node's priority,
// then insert after the rear.
else if (p > (rr).priority) {
news.next = null;
(rr).next = news;
news.prev = (rr).next;
rr = news;
}
// Handle other cases
else {
// Find position where we need to
// insert.
Node start = (fr).next;
while (start.priority > p)
start = start.next;
(start.prev).next = news;
news.next = start.prev;
news.prev = (start.prev).next;
start.prev = news.next;
}
}
front = fr;
rear = rr;
}
// Return the value at rear
static int peek(Node fr) { return fr.info; }
static boolean isEmpty(Node fr) { return (fr == null); }
// Removes the element with the
// least priority value form the list
static int pop(Node fr, Node rr)
{
Node temp = fr;
int res = temp.info;
(fr) = (fr).next;
if (fr == null)
rr = null;
front = fr;
rear = rr;
return res;
}
// Driver code
public static void main(String args[])
{
push(front, rear, 2, 3);
push(front, rear, 3, 4);
push(front, rear, 4, 5);
push(front, rear, 5, 6);
push(front, rear, 6, 7);
push(front, rear, 1, 2);
System.out.println(pop(front, rear));
System.out.println(peek(front));
}
}
// This code is contributed
// by Arnab Kundu
Python3
# Python3 code to implement priority # queue using doubly linked list # Linked List Node class Node: def __init__(self): self.info = 0 self.priority = 0 self.next = None self.prev = None front = None rear = None # Function to insert a new Node def push(fr, rr, n, p): global front, rear news = Node() news.info = n news.priority = p # If linked list is empty if (fr == None): fr = news rr = news news.next = None else: # If p is less than or equal fr # node's priority, then insert at # the fr. if (p <= (fr).priority): news.next = fr (fr).prev = news.next fr = news # If p is more rr node's priority, # then insert after the rr. elif (p > (rr).priority): news.next = None (rr).next = news news.prev = (rr).next rr = news # Handle other cases else: # Find position where we need to # insert. start = (fr).next while (start.priority > p): start = start.next (start.prev).next = news news.next = start.prev news.prev = (start.prev).next start.prev = news.next front = fr rear = rr # Return the value at rr def peek(fr): return fr.info def isEmpty(fr): return fr == None # Removes the element with the # least priority value form the list def pop(fr, rr): global front , rear temp = fr res = temp.info (fr) = (fr).next if (fr == None): rr = None front = fr rear = rr return res # Driver code if __name__=='__main__': push( front, rear, 2, 3) push( front, rear, 3, 4) push( front, rear, 4, 5) push( front, rear, 5, 6) push( front, rear, 6, 7) push( front, rear, 1, 2) print(pop(front, rear)) print(peek(front)) # This code is contributed by rutvik_56
C#
// C# code to implement priority
// queue using doubly linked list
using System;
class GFG {
public static Node front, rear;
// Linked List Node
public class Node {
public int info;
public int priority;
public Node prev, next;
}
// Function to insert a new Node
public static void push(Node fr, Node rr, int n, int p)
{
Node news = new Node();
news.info = n;
news.priority = p;
// If linked list is empty
if (fr == null) {
fr = news;
rr = news;
news.next = null;
}
else {
// If p is less than or equal front
// node's priority, then insert at
// the front.
if (p <= (fr).priority) {
news.next = fr;
(fr).prev = news.next;
fr = news;
}
// If p is more rear node's priority,
// then insert after the rear.
else if (p > (rr).priority) {
news.next = null;
(rr).next = news;
news.prev = (rr).next;
rr = news;
}
// Handle other cases
else {
// Find position where we
// need to insert.
Node start = (fr).next;
while (start.priority > p) {
start = start.next;
}
(start.prev).next = news;
news.next = start.prev;
news.prev = (start.prev).next;
start.prev = news.next;
}
}
front = fr;
rear = rr;
}
// Return the value at rear
public static int peek(Node fr) { return fr.info; }
public static bool isEmpty(Node fr)
{
return (fr == null);
}
// Removes the element with the
// least priority value form the list
public static int pop(Node fr, Node rr)
{
Node temp = fr;
int res = temp.info;
(fr) = (fr).next;
if (fr == null) {
rr = null;
}
front = fr;
rear = rr;
return res;
}
// Driver code
public static void Main(string[] args)
{
push(front, rear, 2, 3);
push(front, rear, 3, 4);
push(front, rear, 4, 5);
push(front, rear, 5, 6);
push(front, rear, 6, 7);
push(front, rear, 1, 2);
Console.WriteLine(pop(front, rear));
Console.WriteLine(peek(front));
}
}
// This code is contributed by Shrikant13
Javascript
<script>
// javascript code to implement priority
// queue using doubly linked list
var front, rear;
// Linked List Node
class Node {
constructor(){
this.info = 0;
this.priority = 0;
this.prev = null;
this.next = null;
}
}
// Function to insert a new Node
function push(fr, rr , n , p) {
var news = new Node();
news.info = n;
news.priority = p;
// If linked list is empty
if (fr == null) {
fr = news;
rr = news;
news.next = null;
} else {
// If p is less than or equal front
// node's priority, then insert at
// the front.
if (p <= (fr).priority) {
news.next = fr;
(fr).prev = news.next;
fr = news;
}
// If p is more rear node's priority,
// then insert after the rear.
else if (p > (rr).priority) {
news.next = null;
(rr).next = news;
news.prev = (rr).next;
rr = news;
}
// Handle other cases
else {
// Find position where we need to
// insert.
var start = (fr).next;
while (start.priority > p)
start = start.next;
(start.prev).next = news;
news.next = start.prev;
news.prev = (start.prev).next;
start.prev = news.next;
}
}
front = fr;
rear = rr;
}
// Return the value at rear
function peek(fr) {
return fr.info;
}
function isEmpty(fr) {
return (fr == null);
}
// Removes the element with the
// least priority value form the list
function pop(fr, rr) {
var temp = fr;
var res = temp.info;
(fr) = (fr).next;
if (fr == null)
rr = null;
front = fr;
rear = rr;
return res;
}
// Driver code
push(front, rear, 2, 3);
push(front, rear, 3, 4);
push(front, rear, 4, 5);
push(front, rear, 5, 6);
push(front, rear, 6, 7);
push(front, rear, 1, 2);
document.write(pop(front, rear)+"<br/>");
document.write(peek(front));
// This code contributed by aashish1995
</script>
Producción:
1 2
Artículo relacionado:
Cola de prioridad usando una lista enlazada individualmente
Complejidades de tiempo y comparación con Binary Heap :
peek() push() pop()
-----------------------------------------
Linked List | O(1) O(n) O(1)
|
Binary Heap | O(1) O(Log n) O(Log n)
Publicación traducida automáticamente
Artículo escrito por rishabh_jain y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA