পাইথনে লিস্ট ব্যবহার করে Stack এবং Queue বাস্তবায়ন

এই আর্টিকেলে আমরা পাইথন ৩.x-এ Stack এবং Queue ডেটা স্ট্রাকচার শিখব। এখানে আমরা এই ডেটা স্ট্রাকচারগুলোর ওয়ার্কিং এবং মডিফিকেশন নিয়ে আলোচনা করব।

এতে অন্তর্ভুক্ত:

1. ইনসারশন অপারেশন (Push, Enqueue)
2. ডিলিশন অপারেশন (Pop, Dequeue)
3. ডিসপ্লে / ট্রাভার্সিং অপারেশন

প্রিরিকুইসাইটস: লিস্ট এবং লিস্ট অপারেশন

রিলেটেড ডেটা স্ট্রাকচার: লিস্ট ম্যানিপুলেশন

রিলেটেড ইমেজ

Stack

Stack-এ অবজেক্টগুলো একে অপর ওপর তালা রাখা হয় এবং এগুলো এসার বিপরীত ক্রমে (reverse order of arrival) রিমুভ হয়, অর্থাৎ LIFO কনসেপ্ট ফলো করা হয়। LIFO মানে Last In First Out টাইপ আয়োজন Stack ডেটা স্ট্রাকচার-এ ফলো করা হয়।

Stack-এ অপারেশন:

• এলিমেন্ট যোগ/অ্যাপেন্ড: এটি স্ট্যাক সাইজ বড়ায় যোগ করা আইটেমের সংখ্যা অনুযায়ী এবং যোগ হয় উপরের এন্ডে অর্থাৎ স্ট্যাকের টপে।
• এলিমেন্ট ডিলিশন/রিমুভ: এতে দুটি কন্ডিশন রয়েছে - যদি Stack খালি হয় তবে ডিলিশনের জন্য কোনো এলিমেন্ট নেই অর্থাৎ Underflow হয় বা যদি Stack-এ কিছু এলিমেন্ট থাকে তবে টপে থাকা এলিমেন্ট রিমুভ হয়। এটি স্ট্যাক সাইজ কমায় রিমুভ করা এলিমেন্টের সংখ্যা অনুযায়ী।
• ট্রাভার্সিং/ডিসপ্লে: স্ট্যাকের প্রতিটি এলিমেন্ট ভিজিট করে স্ক্রিনে ডিসপ্লে করা।

আমরা peek ফাংশনালিটিও যোগ করতে পারি অর্থাৎ Stack-এর টপে থাকা ভ্যালু রিট্রিভ করা।

Stack-এর বৈশিষ্ট্য

• ইনসারশন অর্ডার প্রিজার্ভড (preserved)।
• Stack-এ ডুপ্লিকেসি অ্যালাউড।
• সিমিলার ডেটা-টাইপ স্টোরেজ।
• পার্সিং অপারেশনে অত্যন্ত উপকারী।

উদাহরণ কোড

def isEmpty(stk):
    # চেক করে স্ট্যাক খালি কিনা
    if stk == []:
        return True
    else:
        return False

def Push(stk, item):
    # স্ট্যাকে যোগ করার অনুমতি
    stk.append(item)
    top = len(stk) - 1

def Pop(stk):
    if isEmpty(stk):
        # ভেরিফাই করে স্ট্যাক খালি কিনা
        print("Underflow")
    else:
        # স্ট্যাক থেকে ডিলিশন অনুমতি
        item = stk.pop()
        if len(stk) == 0:
            top = None
        else:
            top = len(stk)
        print("Popped item is " + str(item))

def Display(stk):
    if isEmpty(stk):
        print("Stack is empty")
    else:
        top = len(stk) - 1
        print("Elements in the stack are: ")
        for i in range(top, -1, -1):
            print(str(stk[i]))

# এক্সিকিউটেবল কোড
if __name__ == "__main__":
    stk = []
    top = None
    Push(stk, 1)
    Push(stk, 2)
    Push(stk, 3)
    Push(stk, 4)
    Pop(stk)
    Display(stk)

উপরের কোড পাইথন ৩.x-এ Stack ফাংশনালিটি বাস্তবায়ন করে। আমরা মেনু-ড্রাইভেন প্রোগ্রাম বানাতে পারি ইউজারকে চویس দিয়ে মাল্টিপল if-else স্টেটমেন্ট ব্যবহার করে। Stack ফ্রেম করার কনসেপ্ট দুটি কেসেই একই থাকে।

নিচের স্ক্রিন উপরের প্রোগ্রামের আউটপুট দেখাচ্ছে। আমরা input() ফাংশনও ব্যবহার করতে পারি ইউজার-বেসড ইনপুট সিস্টেমের জন্য (এখানে স্ট্যাটিক ইনপুট বাস্তবায়ন করা হয়েছে)।

আউটপুট

Popped item is 4
Elements in the stack are:
3
2
1

Queue

Queue-এ অবজেক্টগুলো একে পরে একে স্টোর হয় এবং এগুলো এসার ক্রমে (order of arrival) রিমুভ হয়, অর্থাৎ FIFO কনসেপ্ট ফলো করা হয়। FIFO মানে First In First Out টাইপ আয়োজন Queue ডেটা স্ট্রাকচার-এ ফলো করা হয়।

Queue-এ অপারেশন:

• এলিমেন্ট যোগ/অ্যাপেন্ড: এটি কিউ সাইজ বড়ায় যোগ করা আইটেমের সংখ্যা অনুযায়ী এবং যোগ হয় রিয়ার এন্ডে অর্থাৎ কিউর পিছনে।

• এলিমেন্ট ডিলিশন/রিমুভ: এতে দুটি কন্ডিশন - যদি Queue খালি হয় তবে ডিলিশনের জন্য এলিমেন্ট নেই অর্থাৎ Underflow হয় Queue-তে বা যদি Queue-এ কিছু এলিমেন্ট থাকে তবে ফ্রন্টে থাকা এলিমেন্ট রিমুভ হয়। এটি স্ট্যাক সাইজ কমায় রিমুভ করা এলিমেন্টের সংখ্যা অনুযায়ী।

• ট্রাভার্সিং/ডিসপ্লে: স্ট্যাকের প্রতিটি এলিমেন্ট ভিজিট করে স্ক্রিনে ডিসপ্লে করা।

আমরা peek ফাংশনালিটিও যোগ করতে পারি অর্থাৎ Queue-এর ব্যাক/এন্ডে থাকা ভ্যালু রিট্রিভ করা।

Queue-এর বৈশিষ্ট্য

• ইনসারশন অর্ডার প্রিজার্ভড।
• Queue-এ ডুপ্লিকেসি অ্যালাউড।
• সিমিলার ডেটা-টাইপ স্টোরেজ।
• CPU টাস্ক অপারেশন পার্সিং-এ অত্যন্ত উপকারী।

উদাহরণ কোড

# কিউর রিয়ার এন্ডে এলিমেন্ট যোগ
def enqueue(data):
    queue.insert(0, data)

# কিউর ফ্রন্ট এলিমেন্ট রিমুভ
def dequeue():
    if len(queue) > 0:
        return queue.pop()
    return ("Queue Empty!")

# কিউর এলিমেন্ট ডিসপ্লে
def display():
    print("Elements on queue are:")
    for i in range(len(queue)):
        print(queue[i])

# এক্সিকিউটেবল কোড
if __name__ == "__main__":
    queue = []
    enqueue(5)
    enqueue(6)
    enqueue(9)
    enqueue(5)
    enqueue(3)
    print("Popped Element is: " + str(dequeue()))
    display()

উপরের কোড পাইথন ৩.x-এ Queue ফাংশনালিটি বাস্তবায়ন করে। মেনু-ড্রাইভেন প্রোগ্রাম বানাতে পারি ইউজারকে চویس দিয়ে মাল্টিপল if-else স্টেটমেন্ট ব্যবহার করে। Queue ফ্রেম করার কনসেপ্ট দুটি কেসেই একই থাকে।

নিচের স্ক্রিন উপরের প্রোগ্রামের আউটপুট দেখাচ্ছে। ইউজার-বেসড ইনপুট সিস্টেমের জন্য input() ফাংশনও ব্যবহার করা যায় (এখানে স্ট্যাটিক ইনপুট বাস্তবায়ন করা হয়েছে)।

আউটপুট

Popped item is: 5
Elements on queue are:
3
5
9
6

উপসংহার

এই আর্টিকেলে আমরা পাইথন ৩.x-এ Stack ও Queue ডেটা স্ট্রাকচার বাস্তবায়ন শিখেছি। আপনি একই অ্যালগরিদম ব্যবহার করে যেকোনো অন্য প্রোগ্রামিং ল্যাঙ্গুয়েজে stack/queue ডিটেক্টর প্রোগ্রাম বাস্তবায়ন করতে পারেন।