အခန်း ၅ ။ Queue

ဒီအခန်းမှာတော့ ကျွန်တော် Queue အကြောင်းကို အဓိက ရှင်းပြသွားပါမယ်။ Queue တစ်ခု ကို ဘယ်လို ရေးရသလဲ နောက်ပြီးတော့ ဘာတွေ ပါဝင်တယ်ဆိုတာတွေကို လေ့လာနိုင်မှာပါ။

Queue

ကျွန်တော်တို့ Stack နဲ့ ပတ်သက်ပြီးတော့ လေ့လာပြီးပါပြီ။ အခု Queue အကြောင်းလေ့လာရအောင်။ Stack ဟာ First In Last Out ဖြစ်ပြီးတော့ Queue ဟာ First In First Out ဖြစ်ပါတယ်။ Queue ဟာ ဘာနဲ့ တူသလဲ ဆိုတော့ ဆိုင်တွေမှာ တန်းစီပြီး မုန့်ဝယ် သလို အရင် တန်းစီတဲ့လူ အရင် ရပါတယ်။ Stack ကတော့ တစ်ကား တစ်ပေါက်ထဲရှိတဲ့ bus ကား လိုမျိုး နောက်ဆုံးဝင်သည့် သူက အရင် ထွက် လို့ ရပါတယ်။

Queue Abstract Data Type

Queue တစ်ခု ဖန်တီးဖို့ ကျွန်တော်တို့ ဘာတွေ လိုမလဲ အရင် စဉ်းစားကြည့်ရအောင်။

Queue() Queue class တစ်ခု ဖန်တီးဖို့ လိုအပ်ပါတယ်။ ပထမဆုံး class ကို create လုပ်သည့်အခါမှတော့ empty ဖြစ်နေဖို့ လိုပါတယ်။ enqueue(item) item အသစ်ထည့်လိုက်ရင် နောက်ဆုံးမှာ data တွေသွားပြီး append လုပ်ပါမယ်။ dequeue() ဖျက်ပြီဆိုရင် ရှေ့ဆုံးက data ကို ထုတ်ဖို့ လိုအပ်ပါတယ်။ isEmpty() queue တစ်ခု ဟာ empty ဖြစ်မဖြစ် စစ်ဖို့လိုပါတယ်။ Boolean value return ပြန်လာပါမယ်။ size() queue ထဲမှာ item ဘယ်နှစ်ခု ရှိလဲဆိုတာကို သိဖို့ အတွက်ပါ။

ကျွန်တော်တို့ စပြီးတော့ implement လုပ်ကြည့်ရအောင်။

Implementing A Queue

ကျွန်တော်တို့ Stack တစ်ခု ကို ဖန်တီးထားဖူးသည့် အတွက်ကြောင့် Queue တစ်ခု ဖန်တီးဖို့ မခက်ခဲလှပါဘူး။

pyqueue.py တစ်ခု ကို ဖန်တီးပြီး အောက်ပါ code ထည့်လိုက်ပါမယ်။

class Queue:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self, item):
        self.items.insert(0,item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)

q=Queue()
q.enqueue(6)
q.enqueue('cat')
q.enqueue(True)
print(q.size())
print(q.dequeue())
print(q.dequeue())
print(q.size())

3
6
cat
1

ဆိုပြီး ထွက်လာပါမယ်။ စုစုပေါင်း ၃ ခု ရှိပါတယ်။ ပထမဆုံးထည့်လိုက်သည့် value က 6 ဖြစ်သည့်အတွက် 6 ထွက်လာပါမယ်။ ဒုတိယ အကြိမ် က cat ဆိုပြီး ထွက်လာပါမယ်။ အခု အချိန်မှာတော့ queue တစ်ခု ပဲ ရှိပါတော့တယ်။

Priority Queue

Queue မှာ နောက်ထပ် တစ်မျိုး ရှိတာကတော့ Priority Queue ပါ။ အရင်လာ အရင်ထွက် ဆိုပေမယ့် အရေးကြီးတာကို ဦးစားပေးပြီး နောက်မှလာပေမယ့် အရင် ထွက်ဖို့ လိုပါတယ်။ ထည့်လိုက်သည့် data ရဲ့ Priority ပေါ်မှာ မူတည်ပြီးတော့ ပြန်ထုတ်ဖို့ လိုပါတယ်။

pyqueue.py နဲ့ အတူတူ pqueue.py ကို ဖန်တီးပါတယ်။

from pyqueue import Queue

class PQueue:
    def __init__(self):
        self.items = {}

    def isEmpty(self):
        return len(self.items) == 0

    def enqueue(self, item,priority=0):
        if priority not in self.items:
            self.items[priority] = Queue()
            
        queue = self.items[priority]
        queue.enqueue(item)

    def dequeue(self):
        keys = list(self.items.keys())
        
        if len(keys) > 0 :
            cursor = keys[-1]
            
            myqueue = self.items[cursor]
            val = myqueue.dequeue()
            
            if myqueue.size() == 0 :
                del self.items[cursor]
            return val
        return ""

    def size(self):
        size = 0
        for key in self.items.keys():
            size = size + self.items[key].size()
        return size

Priority Queue ဟာ queue တွေကို Priority အလိုက် စီပြီးတော့ ပြန် ထုတ်ပေးတာပါ။ Code ကို မရှင်းပြခင်မှာ အရင်ဆုံး စမ်းကြည့် ရအောင်။

from pqueue import PQueue

p = PQueue()

p.enqueue("HELLO",1)
p.enqueue("H",2)
p.enqueue("E",5)
p.enqueue("L",3)
p.enqueue("O",3)
p.enqueue("Sample",9)

# 7
print(p.size())

#Sample
print(p.dequeue())

#E
print(p.dequeue())

#4
print(p.size())

#L
print(p.dequeue())

#O
print(p.dequeue())

#H
print(p.dequeue())


#1
print(p.size())

enqueue လုပ်တဲ့ အခါမှာ value နဲ့ priority ပါပါတယ်။ သို့ပေမယ့် ပြန်ထုတ်သည့် အခါမှာ Priority အမြင့်ဆုံး က အရင် ထွက်လာပါလိမ့်မယ်။

p = PQueue()

p.enqueue("HELLO",1)
p.enqueue("H",2)
p.enqueue("E",5)
p.enqueue("L",3)
p.enqueue("O",3)
p.enqueue("Sample",9)

အဲဒီမှာ priority အမြင့်ဆုံးက "Sample" ပါ။ ဒါကြောင့် နောက်ဆုံးမှ ထည့်ပေမယ့် ပထမဆုံး ထွက်လာတာကို တွေ့ပါလိမ့်မယ်။

အခု ကျွန်တော်တို့ PQueue() ကို လေ့လာကြည့်ရအောင်။

ကျွန်တော်တို့ဟာ Queue တွေကို priority အလိုက် စီရမှာ ဖြစ်တဲ့ အတွက် array အစား dictionary ကို အသုံးပြုထားပါတယ်။ နောက် အခန်းမှာ Dictionary အကြောင်းကို ရှင်းပြပေးပါမယ်။ enqueue လုပ်တဲ့ အခါမှာ item dictionary ရဲ့ Priority အခန်း မှာ Queue Object ရှိမရှိ စစ်ပါတယ်။

if priority not in self.items:
    self.items[priority] = Queue()

ဆိုတာက self.items ထဲမှာ key name က priority ရှိ မရှိကြည့်တာပါ။ မရှိဘူးဆိုရင် Queue Object အသစ် တစ်ခု ဆောက်ပြီး ထည့်လိုက်ပါတယ်။

queue = self.items[priority]
queue.enqueue(item)

item ထဲကနေ ပြီးတော့ priority key ပေါ်မှာ မူတည်ပြီးတော့ Queue object ကို ထုတ်လိုက်ပါတယ်။ ပြီးတော့ Queue ထဲမှာ enqueue လုပ်ပေးပါတယ်။

p.enqueue("HELLO",1)
p.enqueue("H",2)
p.enqueue("E",5)
p.enqueue("L",3)
p.enqueue("O",3)
p.enqueue("Sample",9)

အဲဒီလို ဆိုရင် data တွေ အနေနဲ့

{
    1 : ["HELLO"],
    2 : ["H"],
    3 : ["L","O"],
    5 : ["E"],
    9 : ["Sample"]
}

ဆိုပြီး ရှိနေပါမယ်။

dequeue အပိုင်းကတော့ နည်းနည်း ရှုပ်ထွေးပါတယ်။

keys = list(self.items.keys())

keys ထဲမှာ [1,2,3,5,9] ဆိုပြီး ရောက်လာပါမယ်။

if len(keys) > 0 :

keys မှာ အခန်း ရှိမရှိ စစ်ပါတယ်။

cursor = keys[-1]

-1 ဆိုတာကတော့ နောက်ဆုံး အခန်းကို ဆွဲထုတ်လိုက်ပါတယ်။

myqueue = self.items[cursor]
val = myqueue.dequeue()

ပြီးတော့ queue object ကို ဆွဲထုတ်ပါတယ်။ ပြီးတော့ dequeue() လုပ်ပြီးတော့ data ကို ဆွဲထုတ်လိုက်ပါတယ်။

if myqueue.size() == 0 :
    del self.items[cursor]

queue ထဲမှာ data မရှိတော့ရင် အခန်းကို ဖျက်ချလိုက်ပါတယ်။

size = 0
for key in self.items.keys():
    size = size + self.items[key].size()

size တွက် ကတော့ ရိုးရိုးလေးပါပဲ။ item ထဲမှာ ရှိတဲ့ queue တွေ အားလုံးရဲ့ size ကို ပေါင်းပြီးတော့ return ပြန်ပေးလိုက် ရုံပါပဲ။

Hot Potato

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

ကျွန်တော်တို့ အခု အဲဒီ အတွက် program လေးကို Queue ကို အသုံးပြုပြီး ရေးပါမယ်။ မရေးခင် စဉ်းစားကြည့်ရအောင်။

Aung Aung, Mg Mg , Thiha , Thin Thin , Ko Ko , Hla Hla ဆိုပြီး ရှိတယ်။ အာလူး ၈ ကြိမ်မြောက် လူက ထွက် ရမယ် ဆိုရင် Thiha က အရင် ထွက်ရပါမယ်။ နောက်တစ်ကြိမ်ဆိုရင် Aung Aung ထွက်ရမယ်။ ပြီးရင် Mg Mg။ ပြီးတော့ Hla Hla။ ပြီးတော့ Thin Thin။ နောက်ဆုံး Ko Ko သာကျန်ခဲ့ပါမယ်။

အဲဒီ Program လေးကို စဉ်းစားရင် အာလူးဟာ တစ်ယောက်ပြီး တစ်ယောက် ပြောင်းသွားတယ်။ နောက်ဆုံး Hla Hla ဆီ ရောက်သွားရင် Aung Aung ကနေ ပြန်စတယ်။

တနည်းပြောရင် ပထမဆုံး က လူကို နောက်ကနေ ပြန်ပြီး တန်းစီ ခိုင်းတာနဲ့ အတူတူပါပဲ။ အာလူးကို နောက်တစ်ယောက်ကို ပေးပြီးပြီ ဆိုရင် နောက်ကို ပြန်သွားပြီး တန်းစီ ပုံစံပါပဲ။

Aung Aung, Mg Mg , Thiha , Thin Thin , Ko Ko , Hla Hla ဆိုပါဆို့။ Aung Ang ကနေ Mg Mg ကို အာလူး ပေးပြီးရင် Queue က Mg Mg , Thiha , Thin Thin , Ko Ko , Hla Hla, Aung Aung ဖြစ်သွားမယ်။ ပြီးရင် Thiha , Thin Thin , Ko Ko , Hla Hla, Aung Aung, Mg Mg ဖြစ်မယ်။

ဒါကို သဘောပေါက်ပြီဆိုရင် ကျွန်တော်တို့ code ရေးလို့ရပါပြီ။

from pyqueue import Queue

def hotPotato(namelist, num):
    simqueue = Queue()
    for name in namelist:
        simqueue.enqueue(name)

    while simqueue.size() > 1:
        for i in range(num):
            simqueue.enqueue(simqueue.dequeue())
        simqueue.dequeue()
    return simqueue.dequeue()


print(hotPotato(["Aung Aung", "Mg Mg" , "Thiha" , "Thin Thin" , "Ko Ko" , "Hla Hla"],8))

Code လေးက ရှင်းပါတယ်။ ထွေထွေ ထူးထူး မရှင်းပြတော့ပါဘူး။

simqueue.enqueue(simqueue.dequeue())

အဲဒီ code လေးက dequeue လုပ်ပြီးတာနဲ့ ချက်ခြင်း enqueue ပြန်လုပ်ဆိုတဲ့ သဘောပါ။ အခုဆိုရင်တော့ Queue အကြောင်း အနည်းငယ်သဘောပေါက်လောက်ပြီ ထင်ပါတယ်။

လေ့ကျင့်ခန်း ၅။

မေးခွန်း ၁။

class Queue:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self, item):
        self.items.insert(0,item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)

q=Queue()
q.enqueue(12)
q.enqueue('dog')
q.enqueue(True)

print(q.dequeue())

အဖြေသည်

A . 12 B. dog C. True