Cola de prioridad usando la lista doblemente enlazada

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. 

Complete Interview Preparation - GFG

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *