Stack ကိုအသုံးပြု။ တန်းစီ


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် တိကျသော Adobe က အမေဇုံ DE ရှော Flipkart Goldman Sachs InfoEdge InMobi ကွမ်းခြံကုန်း MAQ Microsoft က မော်ဂန်စတန်လေ Oracle က Walmart ဓာတ်ခွဲခန်းများ
ဆံပင်ကြိုး စုပုံထား

တန်းစီအတွက် စုပုံထား ပြproblemနာ။ ကျွန်ုပ်တို့သည် stack data ဖွဲ့စည်းပုံ၏ standard functions များကို အသုံးပြု၍ တန်းစီ၏အောက်ပါလုပ်ဆောင်မှုများကိုလုပ်ဆောင်ရမည်။

  1. Enqueue: Queue ရဲ့အဆုံးမှာ element တစ်ခုကိုထည့်ပါ
  2. Dequeue: element တစ်ခုကို Queue ရဲ့ start ကနေဖယ်ထုတ်ပါ

နမူနာ

input:
စုစုပေါင်း (5)
စုစုပေါင်း (11)
စုစုပေါင်း (39)
Dequeue () // ပြန်လာသည် 5
စုစုပေါင်း (12)
Dequeue () // ပြန်လာသည် 11
Dequeue () // ပြန်လာသည် 39
output:
5
11
39

algorithm

Queue ကို stack များသုံးပြီးနည်းလမ်းနှစ်ခုရှိပါတယ်။ ပထမတစ်ခုက enqueue operation ကိုစျေးကြီးအောင်လုပ်ပြီး၊ ဒုတိယကတော့ dequeue operation ကိုအကုန်အကျများတယ်။

Stack ကိုသုံးပြီး Queue အတွက် Method 1 (အကုန်အကျများသော Enqueue စစ်ဆင်ရေး)

stack နှစ်ခု st1 နှင့် st2 ဖန်တီးပါ။ မြင်ယောင်ကြည့်ပါ ဆံပင်ကြိုး st1 တွင် st1 ၏ထိပ်သည်စီတန်း၏ရှေ့တွင်ရှိပြီး၊ st1 တွင်အောက်သို့ရွေ့လျားခြင်းသည်တန်းစီတွင်ရှေ့သို့ရွေ့လျားခြင်းနှင့်တူသည်။

စုစုပေါင်း (x)

x ၏တန်း၏နောက်ဖက်သို့ x ကိုတွန်းခြင်းသည် x ကို stack st1 ၏အောက်ဆုံးသို့တွန်းပို့ခြင်းနှင့်အတူတူပင်ဖြစ်သည်။

  1. st1 မှ element အားလုံးကိုဖယ်ရှားပြီး st2 သို့တွန်းပါ။
  2. x ကို st2 သို့နှိပ်ပါ။
  3. element အားလုံးကို st2 မှဖယ်ရှားပြီး st1 သို့ပြန်ပို့ပါ။

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

Stack ကိုအသုံးပြု။ တန်းစီ

Dequeue ()

Element တစ်ခုကိုလူတန်း၏အရှေ့ဘက်မှဖယ်ရှားခြင်းသည် stack st1 ထိပ်ကိုဖယ်ရှားခြင်းနှင့်ဆင်တူသည်။ ထို့ကြောင့် st1 သည်ဗလာမဟုတ်ပါက st1 ထိပ်ကိုပြန်သွားပါ။

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

နည်းလမ်း 1 ၏ယေဘုယျအားအာကာသရှုပ်ထွေး = အို (ဎ)

Stack ကို အသုံးပြု၍ Queue အတွက် JAVA Code

import java.util.Stack;

public class QueueUsingStacks {
    // Costly Enqueue Operation
    private static Stack<Integer> st1;
    private static Stack<Integer> st2;

    private static void enqueue(int x) {
        // remove all the elements from st1 and push them to st2
        while (!st1.isEmpty()) {
            st2.push(st1.pop());
        }

        // push x to st2
        st2.push(x);

        // remove all the elements from st2 and push them back to st1
        while (!st2.isEmpty()) {
            st1.push(st2.pop());
        }
    }

    private static int dequeue() {
        if (st1.isEmpty()) {
            return -1;
        }

        // if st1 is not empty return and remove the top of st1
        return st1.pop();
    }

    public static void main(String[] args) {
        st1 = new Stack<>();
        st2 = new Stack<>();
        
        // Example
        enqueue(5);
        enqueue(11);
        enqueue(39);
        System.out.println(dequeue());
        enqueue(12);
        System.out.println(dequeue());
        System.out.println(dequeue());
    }
}
5
11
39

C ++ ကုဒ်

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

// Costly Enqueue Operation

stack<int> st1;
stack<int> st2;

void enqueue(int x) {
    // remove all the elements from st1 and push them to st2
    while (!st1.empty()) {
        int curr = st1.top();
        st1.pop();
        st2.push(curr);
    }
    
    // push x to st2
    st2.push(x);
    
    // remove all the elements from st2 and push them back to st1
    while (!st2.empty()) {
        int curr = st2.top();
        st2.pop();
        st1.push(curr);
    }
}

int dequeue() {
    if (st1.empty()) {
        return -1;
    }
    
    // if st1 is not empty return and remove the top of st1
    int top = st1.top();
    st1.pop();
    return top;
}

int main() {
    // Example
    enqueue(5);
    enqueue(11);
    enqueue(39);
    cout<<dequeue()<<endl;
    enqueue(12);
    cout<<dequeue()<<endl;
    cout<<dequeue()<<endl;
    
    return 0;
}
5
11
39

Stack ကိုသုံးပြီး Queue အတွက်နည်းလမ်း 2 (အကုန်အကျ Dequeue စစ်ဆင်ရေး)

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

စုစုပေါင်း (x)

x ၏တန်း၏နောက်ဖက်သို့ x ကိုနှိပ်ခြင်းသည် x ကို stack_st1 ထိပ်သို့ပို့ခြင်းနှင့်ဆင်တူသည်။ ဒီတော့ x ကို st1 ရဲ့ထိပ်ကိုနှိပ်ပါ။

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

Dequeue ()

element တစ်ခု၏ Que ၏ရှေ့မှ element တစ်ခုကိုဖယ်ရှားခြင်းသည် stack_st1 ၏အောက်ခြေရှိ element တစ်ခုကိုဖယ်ရှားခြင်းနှင့်ဆင်တူသည်။ st1 ဟာအချည်းနှီးမဖြစ်ဘူးဆိုလျှင်

  1. st1 မှ element အားလုံးကိုဖယ်ရှားပြီး st2 သို့တွန်းပါ။
  2. st2 ၏ထိပ်ကို Pop နှင့် variable ကိုထိပ်တွင်သိမ်းထားပါ။
  3. element အားလုံးကို st2 မှဖယ်ရှားပြီး st1 သို့ပြန်ပို့ပါ။
  4. အပေါ်သို့ပြန်သွားပါ

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

Stack ကိုအသုံးပြု။ တန်းစီ

နည်းလမ်း 2 ၏ယေဘုယျအားအာကာသရှုပ်ထွေး = အို (ဎ)

Java Code ကို

import java.util.Stack;

public class QueueUsingStacks {
    // Costly Dequeue Operation
    private static Stack<Integer> st1;
    private static Stack<Integer> st2;

    private static void enqueue(int x) {
        // push x to top of st1
        st1.push(x);
    }

    private static int dequeue() {
        if (st1.isEmpty()) {
            return -1;
        }

        // if st1 is not empty
        // remove all the elements from st1 and push them to st2
        while (!st1.isEmpty()) {
            st2.push(st1.pop());
        }

        // pop the top of st2 and store it in a variable top
        int top = st2.pop();

        // remove all the elements from st2 and push them back to st1
        while (!st2.isEmpty()) {
            st1.push(st2.pop());
        }
        
        // return top
        return top;
    }

    public static void main(String[] args) {
        st1 = new Stack<>();
        st2 = new Stack<>();

        // Example
        enqueue(5);
        enqueue(11);
        enqueue(39);
        System.out.println(dequeue());
        enqueue(12);
        System.out.println(dequeue());
        System.out.println(dequeue());
    }
}
5
11
39

C ++ ကုဒ်

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

// Costly Dequeue Operation

stack<int> st1;
stack<int> st2;

void enqueue(int x) {
    // push x to top of st1
    st1.push(x);
}

int dequeue() {
    if (st1.empty()) {
        return -1;
    }
    
    // if st1 is not empty
    // remove all the elements from st1 and push them to st2
    while (!st1.empty()) {
        int curr = st1.top();
        st1.pop();
        st2.push(curr);
    }
    
    // pop the top of st2 and store it in a variable top
    int top = st2.top();
    st2.pop();
    
    // remove all the elements from st2 and push them back to st1
    while (!st2.empty()) {
        int curr = st2.top();
        st2.pop();
        st1.push(curr);
    }
    
    // return top
    return top;
}

int main() {
    // Example
    enqueue(5);
    enqueue(11);
    enqueue(39);
    cout<<dequeue()<<endl;
    enqueue(12);
    cout<<dequeue()<<endl;
    cout<<dequeue()<<endl;
    
    return 0;
}
5
11
39

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