পাইথন ডাটা স্ট্রাকচার এন্ড এলগোরিদমঃ পর্ব-১(স্ট্যাক এবং কিউ) | yusuff.dev

পাইথন ডাটা স্ট্রাকচার এন্ড এলগোরিদমঃ পর্ব-১(স্ট্যাক এবং কিউ)

April 21, 2019, 8:48 p.m.

Author-Abu Yusuf

Image

স্ট্যাক এবং কিউঃ

স্ট্যাকঃ স্ট্যাক এর সোজা বাংলা অর্থ হলো স্তূপ। আমার টেবিল এর উপর অনেক গুলো বই রাখা আছে স্তূপ আকারে। মানে একটার উপর একটা এভাবে রাখা আছে। এখন আমি নতুন একটা বই কিনলে সেটা সেই বইগুলোর উপর রাখবো। আবার সেই স্তূপ থেকে যখন বই সরাবো তখন সবার উপরেরটা সরাবো। অনেকে আবার বলবে যে না ভাই আমি নতুন বই কিনে স্তূপের মাঝখানে রাখবো আবার যখন সেই স্তূপ থেকে বই সরাবো তখন মাঝখান থেকেই সরাবো। সেইটা ভিন্ন কথা। এই উধাহরণটা দেয়া হয়েছে শুধু মাত্র স্ট্যাক কি সেটা বুঝানোর জন্য।

এই যে সবার উপরে নতুন বই রাখলাম এবং সবার আগে সেই বই সরালাম এটাই হলো স্ট্যাক।

ডেটা স্ট্রাকচারে যখন আমরা আমাদের ডাটার সাথে নতুন কোন ডাটা যোগ করবো সেটি একেবারে ডাটার শেষে এসে অ্যাড হবে। আবার সেখান থেকে কোন ডাটাকে রিমুভ করলে সেই ডাটাই(সর্বশেষ অ্যাডকৃত ডাটা) সবার আগে রিমুভ হবে। আর এটাকেই ডাটা স্ট্রাকচারের স্ট্যাক বলা হয়।

আশা করছি একটা উধাহরণ দিলে ব্যাপারটা ক্লিয়ার হবেঃ

ধরুন, আমার একটা ডাটা সেট আছে এরকমঃ

data = [1, 2, 3, 4, 5]

তো আমই চাচ্ছি এই ডাটা সেটের সাথে নতুন একটা এলিমেন্ট অ্যাড করতে। পাইথনের বিল্টিন ডাটা স্ট্রাকচার লিস্টের জন্য append() নামের একটা ফাংশন আছে যেটা ব্যাবহার করে আমরা এই কাজটা খুব সহজেই করতে পারি।

>>> data.append(8)
>>> data
[1, 2, 3, 4, 5, 8]

append() ফাংশন দিয়ে খুব সহজেই এই কাজটা করে ফেলা যায় কিন্তু আমি যদি ৫/১০টা বা আরও বেশি ডাটা অ্যাড করতে চাই একেবারে? সেটা কিভাবে করবো? চিন্তার কোন কারণ নাই। পাইথনের বিল্টিন ডাটা স্ট্রাকচার লিস্টের জন্য extend() নামের একটা ফাংশন আছে যেটা ব্যাবহার করে আমরা এই কাজটা খুব সহজেই করতে পারি।

>>> data = [1, 2, 3]
>>> data.extend([4,5,6])
>>> data
[1, 2, 3, 4, 5, 6]

বেশ মজার ব্যাপার তাই না? আমরা এই লিস্ট পরে শিখবো। লিস্ট দিয়ে অনেক মজার মজার কাজ করা যায়। আপাতত আমরা স্ট্যাক শিখার জন্য যা যা লাগে সেগুলো দেখাচ্ছি একটু একটু করে।

লিস্টে একটা এলিমেন্ট কিভাবে অ্যাড করে সেটা আমরা দেখেছি append() ফাংশনের মাধ্যমে। স্ট্যাকে নতুন কোন ডাটা অ্যাড করাকে বলে পুশ(push) আর কোন ডাটা রিমুভ করাকে বলে পপ(pop)।

আমরা যখন লিস্টে নতুন কোন ডাটা রাখলাম সেটা লিস্টের একেবারে শেষে গিয়ে অ্যাড হয়েছে। আবার আমরা যদি পপ করি তাহলে ওই শেষে অ্যাড হইয়া এলিমেন্ট টাই রিমুভ হবে। পাইথনের বিল্টিন ডাটা স্ট্রাকচার লিস্টের জন্য pop() নামের একটা ফাংশন আছে যেটা ব্যাবহার করে আমরা এই কাজটা খুব সহজেই করতে পারিঃ

>>> data = [1, 2, 3, 4, 5]
>>> data.pop()
5
>>> data
[1, 2, 3, 4]

আবার আমরা এই লিস্টের কোন স্পেসিফিক কোন এলিমেন্টকে রিমুভ করতে চাইলে করতে পারি remove() ফাংশন ব্যাবহার করেঃ

>>> data.remove(2)
>>> li
[1, 3, 4]

এর চাইতেও সহজ কিছু আছে এই দুনিয়ায়?

আশা করছি যে স্ট্যাকের ধারণা এখন স্পষ্ট সবার কাছে।

স্ট্যাকে কোন এলিমেন্ট অ্যাড করবো (পুশ)- append() ফাংশন দিয়ে।

স্ট্যাকে থেকে কোন এলিমেন্ট রিমুভ করবো (পপ) - pop() ফাংশন দিয়ে।

আমরা এই স্ট্যাকের পুরো কোডটা লিখবোঃ

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

    def push(self, item):
        self.items.append(item)

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

    def is_empty(self):
        if self.items == []:
            return True
        return False


if __name__ == "__main__":
    s = Stack()
    s.push(1)
    s.push(2)
    s.push(3)

    while not s.is_empty():
        item = s.pop()
        print(item)

একটা সময় পপ করতে করতে আমাদের লিস্ট/স্ট্যাক পুরোপুরি খালি হয়ে যাবে তখন আবার পপ করলে IndexError: pop from empty list এরকম একটা ইরর থ্রো করবে। মানে আমাদের আর পপ কোরার মত কোন ইলিমেন্ট নাই। এখানে is_empty() ফাংশনটা ব্যাবহার করা হয়েছে লিস্ট ফাঁকা আছে কিনা সেটা আগেই চেক কোরার জন্য। থাকলে রিটার্ন করবে সত্য নতুবা মিথ্যা।তাহলে আমরা আর এই ইরর খাবো না। ইরর খেতে কারোই ভালো লাগে না।

পুশ এবং পপের কমপ্লেক্সিটিঃ আমরা যখন লিস্টে এলিমেন্ট অ্যাড করছি তখন লিস্টে যতই ডাটা থাকুক না কেন আমাদের এলিমেন্ট টা লিস্টের একেবারে শেষে অ্যাড হচ্ছে। এতে অন্য এলিমেন্ট গুলোর কোন প্রভাব পরছে না। মানে অন্য কোন এলিমেন্টকে কথাও সরতে হচ্ছে না। সেজন্য পুশ এর কমপ্লেক্সিটিঃ O(1)

আবার, পপের ক্ষেত্রেও সেম কমপ্লেক্সিটিঃ O(1) কারণ, লিস্টে যত খুশি এলিমেন্ট থাকুক না কেন, আমরা শুধু মাত্র লিস্টের সবার শেষের এলিমেন্টটাকে রিমুভ করছি। তাতে অন্য এলিমেন্টের কোন প্রভাব পরছে না। অন্য কারো পরিবর্তন হচ্ছে না।

লাস্ট ইন ফার্স্ট আউটঃ স্ট্যাককে বলা হয়ে থাকে লাস্ট ইন ফার্স্ট আউট(লিফো)। মানে আপনি সবার শেষে আসলেই কেবল সবার আগে যেতে পারবেন। লিফটে সবার শেষে ডুকলেন, আবার গ্রাউন্ড ফ্লোরে যাওয়ার পর সবার আগেই বের হলেন। সবার শেষে ডুকলেন বলেই সবার আগে বের হতে পারলেন। তার মানে আপনি ডাটা স্ট্রাকচারের স্ট্যাক রুলস ফলো করেছেন। অভিনন্দন।।
_____ স্ট্যাক শেষ ____
কিউঃ কিউ এর সোজা বাংলা অর্থ হলো সারি বা লাইন। রাস্তায় বের হলে আমরা অনেক সময় কিছু লোককে সারিবদ্ধভাবে লাইনে দাড়িয়ে থাকতে দেখি। বিশেষ করে সকাল বেলায় অফিস যাওয়ার জন্য কিছু বাস কাউন্টারে এমনভাবে লোকজনকে সারিবদ্ধভাবে দাড়িয়ে থাকতে দেখা যায়। যিনি আগে লাইনে দাঁড়ান তিনিই আগে বাসে উঠেন। এভাবে সবার শেষে যিনি দাঁড়ান তিনি সবার শেষেই বাসে উঠেন। অর্থাৎ এখানে “ আগে আসলে আগে পাবেন ” এমন একটা ব্যাপার ঘটে সাধারণত। এই পুরো ব্যাপারটাই হলো ডাটা স্ট্রাকচারের কিউ।

এমন অনেক উদাহরণ আছে যেমনঃ স্কুলের এসেম্বলি শেষে ছাত্রদের ক্লাসে প্রবেশ, ব্যাংকে টাকা তোলা বা জমা দেয়ার সময়, ডাক্তারের চেম্বারে, যেকোনো টিকেট কেনার সময়(বাস,ট্রেন বা ক্রিকেট খেলার) ইত্যাদি।

স্ট্যাক এর সাথে কিউ এর পার্থক্য হচ্ছেঃ স্ট্যাক হলো লাস্ট ইন ফার্স্ট আউট আর কিউ হলো ফার্স্ট ইন ফার্স্ট আউট। এতটুকুই জানলে হবে আপাতত।

কিউ ইমপ্লিমেন্টেশনঃ ধরি, আমার একটা লিস্ট আছে এরকমঃ

data = [1, 2, 3, 4, 5]

তো, আমি এখানে কিউ করবো মানে ডাটা অ্যাড করবো আর ডাটা রিমুভ করবো। আমি এই লিস্টে কোন ডাটা ইলিমেন্ট অ্যাড করলে সেটা একেবারে লিস্টের শেষে গিয়ে অ্যাড হবে(স্ট্যাক এর মত) কিন্তু যখন এই লিস্ট থেকে কোন ডাটা এলিমেন্ট রিমুভ করবো তখন লিস্টের সর্বপ্রথম ডাটা এলিমেন্টটা রিমুভ হবে। চলেন করে ফেলিঃ

>>> data = list([1,2,3,4])
>>> data
[1, 2, 3, 4]
>>> data.append(5)
>>> data
[1, 2, 3, 4, 5]
>>> data.pop(0)
1
>>> data
[2, 3, 4, 5]

এখানে pop(0) করা হয়েছে যাতে লিস্টের সর্বপ্রথম এলিমেন্টকে রিমুভ করা যায় সেজন্য। append() ফাংশনের কাজ আমরা স্ট্যাকে আগেই দেখেছি।

আমরা এই যে লিস্টে নতুন ডাটা এলিমেন্ট অ্যাড করলাম, আবার লিস্টের সর্বপ্রথম এলিমেন্টকে রিমুভ করলাম এটাকে ডেটা স্ট্রাকচারের ভাষায় যথাক্রমে এনকিউ(enqueue) এবং ডিকিউ(dequeue) বলে।

লিস্টে নতুন ডাটা অ্যাডঃ - এনকিউ(enqueue) - append()
লিস্টের প্রথম ডাটা রিমুভঃ- ডিকিউ(dequeue)- pop(0)

এখন আমরা কিউ এর জন্য পুরো কোডটা লিখবোঃ

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

    def enqueue(self, element):
        self.elements.append(element)

    def dequeue(self):
        return self.elements.pop(0)

    def is_faka(self):
        if self.elements == []:
            return True
        return False


if __name__ == "__main__":
    queue = Queue()
    queue.enqueue(4)
    queue.enqueue(6)
    queue.enqueue(8)

    while not queue.is_faka():
        x = queue.dequeue()
        print(x)

আউটপুটঃ

4
6
8

আমরা কিউতে যেইভাবে ডাটা রেখেছিলাম সেভাবেই ডাটার সারি দেখতে পাচ্ছি আমাদের আউটপুটে। অনেকটা আগে আসলে আগে পাবেন এমন ভিত্তিতে।

is_faka() ফাংশনটা কেন ব্যাবহার করেছি সেটা আগেই ব্যাখ্যা করা আছে।
এনকিউ এবং ডিকিউ এর কমপ্লেক্সিটিঃ আমরা যখন লিস্টে এলিমেন্ট অ্যাড করছি তখন লিস্টে যতই ডাটা থাকুক না কেন আমাদের এলিমেন্ট টা লিস্টের একেবারে শেষে অ্যাড হচ্ছে। এতে অন্য এলিমেন্ট গুলোর কোন প্রভাব পরছে না। মানে অন্য কোন এলিমেন্টকে কথাও সরতে হচ্ছে না। সেজন্য এনকিউ এর কমপ্লেক্সিটিঃ O(1)

আবার, ডিকিউ এর ক্ষেত্রে কমপ্লেক্সিটিঃ O(n) কারণ, আমরা যখন লিস্টের প্রথম এলিমেন্টটাকে রিমুভ করছি তখন বাকি এলিমেন্টগুলো বামদিকে একঘর করে সরে এসেছে। মানে আগে যার ইনডেক্স ছিল data[1], প্রথম ডাটা রিমুভ এর পর তার ইনডেক্স হলোঃ data[0], এভাবে সবগুলো ডাটা বামদিকে একঘর করে সরে আসবে। ধরি, লিস্টে n সংখ্যক ডাটা এলিমেন্ট থাকলে প্রত্যেকে একবার করে বামদিকে সরলে এই কাজটি n সংখ্যক বার ঘটবে। তাই, ডিকিউ এর ক্ষেত্রে কমপ্লেক্সিটি হলোঃ O(n)

শুধু pop() ইউজ করলে কমপ্লেক্সিটিঃ O(1)
কিন্তু, pop(0) ইউজ করলে কমপ্লেক্সিটিঃ O(n)

ফার্স্ট ইন ফার্স্ট আউটঃ কিউকে বলা হয়ে থাকে ফার্স্ট ইন ফার্স্ট আউট(ফিফো, ফিফা না আবার)। আগে আসলে আগে পাবেন। আপনি সারির একদম সবার আগে দাঁড়ালেন, এবং সবার আগেই বাসে উঠলেন বা ব্যাংকে টাকা জমা দিলেন।অভিনন্দন, আপনি ডাটা স্ট্রাকচারের কিউ রুলস ফলো করেছেন।

বিঃদ্রঃ এই ব্লগ টা নিজের শখের বশে লিখা। যতটুকু জানি তার আলোকে যতটা সহজ ভাবে উপস্থাপণ সম্ভব চেষ্টা করেছি। কারো কোনকিছু বুঝতে সমস্যা হলে দয়া করে কমেন্ট করবেন। কোন পরামর্শ থাকেলও সেটা সাদরে গৃহীত হবে। ধন্যবাদ ।।