Singly Linked List ကိုအသုံးပြု။ ဦး စားပေးတန်းစီ


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် BrowserStack ပါ Hulu Mahindra Comviva အိတ်ဆောင်ကျောက်မျက် ဆိုးကျိုး
ချိတ်ဆက်စာရင်း ဆံပင်ကြိုး

ဦး စားပေးအတွက် ဆံပင်ကြိုး တစ် ဦး တည်းသုံးပြီး ဆက်စပ်စာရင်း ပြproblemနာရှိပါကကျွန်ုပ်တို့သည်ချိတ်ဆက်ထားသောစာရင်းတစ်ခုကိုအသုံးပြုခြင်းအားဖြင့် ဦး စားပေးတန်းစီကိုအကောင်အထည်ဖော်ရန်လိုအပ်သည်။ ဦး စားပေးတန်းစီတွင်အောက်ပါလုပ်ငန်းများပါဝင်သည်။

  1. push (x, p): ဦး စားပေးတန်းစီအတွက်သင့်လျော်သောအနေအထားမှာ ဦး စားပေး p နှင့်အတူ element တစ်ခုက x ထည့်ပါ။
  2. pop (): အမြင့်ဆုံး ဦး စားပေးနှင့်အတူ element ကိုဖယ်ရှားခြင်းနှင့်ပြန်လာ
  3. peek (): အမြင့်ဆုံး ဦး စားပေးနဲ့ element ကိုပြန်သွားပါ

နမူနာ

input:
တွန်းအားပေး (5, 2)
တွန်းအားပေး (1, 3)
peek ()
တွန်းအားပေး (7, 5)
တွန်းအားပေး (9, 1)
ပေါ့ပ် ()
ပေါ့ပ် ()
peek ()
output:
1
7
1
5

Singly Linked List ကိုအသုံးပြုပြီး ဦး စားပေးတန်းစီများအတွက် Algorithm

အယူအဆမှာချိတ်ဆက်ထားသောစာရင်းကို ဦး စားပေးအစီအစဉ်အတိုင်းအစဉ်လိုက်ထိန်းသိမ်းထားရန်ဖြစ်သည်။ သို့မှသာအမြင့်ဆုံး ဦး စားပေးဒြပ်စင်သည်ရှေ့တန်းတွင်ရှိသည်။

တွန်းအားပေး (x, p)

၎င်း element များကို ဦး စားပေးအစဉ်လိုက်အစဉ်လိုက်စီစဉ်ပေးသောကြောင့် ဦး စားပေးအစီအစဉ်၏အနှောင့်အယှက်မဖြစ်စေရန် ဦး စားပေး p နှင့်အတူပထမ element ကို p ထက်နည်းသော ဦး စားပေးမတိုင်မီထည့်ပါ။ အမှုပေါင်းသုံးခုပေါ်ပေါက်လာသည်။

  1. p ထက်နည်းသော ဦး စားပေးမှုမရှိသော element ကိုချိတ်ဆက်ထားသောစာရင်း၏အဆုံးမှာ element အသစ်ကိုထည့်ပါ။
  2. element အားလုံးသည် p ထက်နည်းသည်။ link list ၏အစတွင် element အသစ်ကိုထည့်ပါ။
  3. အချို့သောဒြပ်စင်များသည် p ထက် ပို၍ ဦး စား ပေး၍ အချို့သည် p ထက် ပို၍ ဦး စားပေးသည်။ ပထမ element သည် p ထက်နည်းသော ဦး စားပေးမတိုင်မီ element အသစ်ကိုထည့်ပါ။

Singly Linked List ကိုအသုံးပြု။ ဦး စားပေးတန်းစီ

အချိန်ရှုပ်ထွေး = အို (ဎ)

Singly Linked List ကိုအသုံးပြုပြီး ဦး စားပေးတန်းစီဘို့ Pseudo ကုဒ်

  1. ဒေတာ = x နှင့် ဦး စားပေး = p နှင့်အတူ node ကိုအသစ်တစ်ခုလုပ်ပါက newNode
  2. အကယ်၍ ခေါင်းသည် null ဖြစ်ပါက၎င်းသည်ပထမဆုံးထည့်သွင်းရမည့် node ဖြစ်သည်။ ထို့ကြောင့် head = newNode နှင့် return ကိုလုပ်ပါ။
  3. node တစ်ခုတည်ဆောက်ခြင်းသည်ခေါင်းနှင့်ညီမျှသည်။
  4. ပထမ ဦး ဆုံး node ကို p ထက်နည်းသော ဦး စားပေးဖြင့် loop တစ်ခုကိုလည်ပတ်ခြင်းဖြင့်ရှာပါ။ temp သည် null မဟုတ်ပါ။ Temp ၏ ဦး စားပေး p သည်ထက်ပိုသည်။ ကြားဖြတ်တိုင်းတွင်, prev.temp နှင့် temp အဖြစ် temp.next အဖြစ် update ကို။
  5. loop ၏အဆုံးပြီးနောက်, temp null သည်ဆိုပါကဆိုလိုသည်မှာ p ထက်နည်းသော ဦး စားပေး node မရှိ, ချိတ်ဆက်စာရင်းရဲ့အဆုံးမှာ newNode ထည့်ပါဆိုလိုသည်မှာ prev.next = newNode လုပ်ပါ။
  6. အကယ်၍ prev သည် null ဖြစ်ပါက node အားလုံးသည် p ထက် ပို၍ ဦး စားပေးသည်ဟုဆိုလိုသည်။ newNode.next = ခေါင်းနှင့်ခေါင်း = newNode လုပ်ပါ။
  7. အခြားတစ်ခုသည် Temp မတိုင်မီ node အသစ်ကိုထည့်ပါ။ ဆိုလိုသည်မှာ newNode.next = temp နှင့် prev.next = newNode ။

ပေါ့ပ် ()

ချိတ်ဆက်ထားသောစာရင်း၏ရှေ့ပိုင်းတွင်အမြင့်ဆုံး ဦး စားပေးဒြပ်စင်ပါရှိသည်။ ၎င်းကိုဖယ်ရှား။ ပြန်သွားပါ။

အချိန်ရှုပ်ထွေး = အို (၁)

peek ()

ချိတ်ဆက်ထားသောစာရင်း၏ရှေ့ပိုင်းတွင်အမြင့်ဆုံး ဦး စားပေးဒြပ်စင်ပါရှိသည်။

အချိန်ရှုပ်ထွေး = အို (၁)

Singly Linked List ကိုအသုံးပြုပြီး ဦး စားပေးတန်းစီများအတွက် JAVA Code ကို

public class PriorityQueueUsingSinglyLinkedList {
    // class representing node of a linked list
    static class Node {
        int data;
        int priority;
        Node next;
        
        public Node(int data, int priority) {
            this.data = data;
            this.priority = priority;
        }
    }

    // Variable representing the head of linked list
    private static Node head = null;

    private static void push(int x, int p) {
        // Create a new node
        Node newNode = new Node(x, p);

        // If head is null, this is the first node to be added
        // so make head = newNode
        if (head == null) {
            head = newNode;
            return;
        }

        Node temp = head;
        Node prev = null;

        // search for first node having priority less than p
        while (temp != null && temp.priority > p) {
            prev = temp;
            temp = temp.next;
        }

        if (temp == null) {
            // no node with priority less than this node (Case 1)
            prev.next = newNode;
        } else {
            if (prev == null) {
                // all the nodes have priority less than p (Case 2)
                // add this node at the starting
                newNode.next = head;
                head = newNode;
            } else {
                // Case 3
                // add this node before the node with priority less than p 
                newNode.next = temp;
                prev.next = newNode;
            }
        }
    }

    private static int peek() {
        // head of the linked list contains the maximum priority element
        if (head != null) {
            return head.data;
        }
        return -1;
    }

    private static int pop() {
        // head of the linked list contains the maximum priority element
        if (head != null) {
            int data = head.data;
            // removing the highest priority element
            head = head.next;
            return data;
        }
        return -1;
    }

    public static void main(String[] args) {
        // Example
        push(5, 2);
        push(1, 3);
        System.out.println(peek());
        push(7, 5);
        push(9, 1);
        System.out.println(pop());
        System.out.println(pop());
        System.out.println(peek());
    }
}
1
7
1
5

Singly Linked List ကိုအသုံးပြုပြီး Priority Queue အတွက် C ++ Code

#include<bits/stdc++.h> 
using namespace std;

// class representing a tree node
class Node {
    public:
    int data;
    int priority;
    Node *next;
    
    Node(int d, int p) {
        data = d;
        priority = p;
        next = NULL;
    }
};

// function to create a new node
Node* newNode(int x, int p) {
    Node *node = new Node(x, p);
    return node;
}

// Variable representing the head of linked list
Node *head = NULL;

void push(int x, int p) {
    // Create a new node
    Node *node = newNode(x, p);
    
    // If head is null, this is the first node to be added
    // so make head = newNode
    if (head == NULL) {
        head = node;
        return;
    }
    
    Node *temp = head;
    Node *prev = NULL;
    
    // search for first node having priority less than p
    while (temp != NULL && temp->priority > p) {
        prev = temp;
        temp = temp->next;
    }
    
    if (temp == NULL) {
        // no node with priority less than this node (Case 1)
        prev->next = node;
    } else {
        if (prev == NULL) {
            // all the nodes have priority less than p (Case 2)
            // add this node at the starting
            node->next = head;
            head = node;
        } else {
            // Case 3
            // add this node before the node with priority less than p
            node->next = temp;
            prev->next = node;
        }
    }
}

int pop() {
    // head of the linked list contains the maximum priority element
    if (head != NULL) {
        int data = head->data;
        // removing the highest priority element
        head = head->next;
        return data;
    }
    return -1;
}

int peek() {
    // head of the linked list contains the maximum priority element
    if (head != NULL) {
        return head->data;
    }
    return -1;
}

int main() {
    // Example
    push(5, 2);
    push(1, 3);
    cout<<peek()<<endl;
    push(7, 5);
    push(9, 1);
    cout<<pop()<<endl;
    cout<<pop()<<endl;
    cout<<peek()<<endl;
    
    return 0;
}
1
7
1
5

ကိုးကားစရာ1    ကိုးကား