Linked Lists এবং Stacks এর ইমপ্লিমেন্টেশন

লুয়া ভাষায় লিঙ্কড লিস্ট এবং স্ট্যাক ডেটা স্ট্রাকচারগুলোর ইমপ্লিমেন্টেশন করার জন্য সাধারণত টেবিল (tables) ব্যবহার করা হয়। টেবিল হল লুয়া ভাষার একমাত্র ডেটা স্ট্রাকচার, এবং এটি খুবই নমনীয়, যা বিভিন্ন ধরনের ডেটা স্ট্রাকচার তৈরিতে ব্যবহার করা যায়। এই টিউটোরিয়ালে আমরা লিঙ্কড লিস্ট এবং স্ট্যাক এর বেসিক ইমপ্লিমেন্টেশন দেখব।

১. লিঙ্কড লিস্ট (Linked List) এর ইমপ্লিমেন্টেশন

লিঙ্কড লিস্ট হলো একধরনের ডেটা স্ট্রাকচার যেখানে প্রতিটি উপাদান (node) পরবর্তী উপাদানের পয়েন্টার ধারণ করে। এটি মূলত চেইন আকারে ডেটা স্টোর করে। লুয়া ভাষায়, একটি লিঙ্কড লিস্ট তৈরি করতে আমরা প্রতিটি নোডে দুটি অংশ রাখতে পারি: ডেটা এবং পরবর্তী নোডের রেফারেন্স।

১.১. লিঙ্কড লিস্ট এর নোড স্ট্রাকচার

প্রথমে, একটি নোডের গঠন করতে হবে। প্রতিটি নোডের মধ্যে ডেটা এবং পরবর্তী নোডের রেফারেন্স থাকবে।

উদাহরণ:

-- নোডের জন্য কনস্ট্রাক্টর ফাংশন
function createNode(data)
    return {data = data, next = nil}
end

-- লিঙ্কড লিস্টে নতুন নোড যোগ করা
function addNode(head, data)
    local newNode = createNode(data)
    if head == nil then
        return newNode  -- যদি লিস্ট খালি থাকে, নতুন নোড হেড হবে
    else
        local current = head
        while current.next do
            current = current.next  -- লিঙ্কড লিস্টের শেষ পর্যন্ত চলুন
        end
        current.next = newNode  -- শেষ নোডের পর নতুন নোড যুক্ত করুন
    end
    return head
end

-- লিঙ্কড লিস্ট প্রিন্ট করা
function printList(head)
    local current = head
    while current do
        print(current.data)  -- নোডের ডেটা প্রিন্ট করা
        current = current.next  -- পরবর্তী নোডে চলা
    end
end

-- লিঙ্কড লিস্ট তৈরি করা
local head = createNode(1)
head = addNode(head, 2)
head = addNode(head, 3)
head = addNode(head, 4)

printList(head)  -- আউটপুট: 1 2 3 4

এখানে, createNode ফাংশন একটি নতুন নোড তৈরি করে, addNode ফাংশন লিঙ্কড লিস্টে নতুন নোড যোগ করে, এবং printList ফাংশন লিস্টের সমস্ত উপাদান প্রিন্ট করে।

২. স্ট্যাক (Stack) এর ইমপ্লিমেন্টেশন

স্ট্যাক একটি লিনিয়ার ডেটা স্ট্রাকচার যেখানে LIFO (Last In First Out) নিয়ম অনুসরণ করা হয়। অর্থাৎ, সর্বশেষ যে উপাদানটি প্রবেশ করেছে, সেটি প্রথমে বের হবে।

স্ট্যাক তৈরি করতে আমরা লুয়া ভাষায় টেবিল ব্যবহার করতে পারি। স্ট্যাকের মধ্যে উপাদান যোগ করার জন্য push এবং উপাদান বের করার জন্য pop ফাংশন ব্যবহার করা হয়।

২.১. স্ট্যাক এর কনসেপ্ট

• push: স্ট্যাকের শীর্ষে একটি নতুন উপাদান যোগ করা।
• pop: স্ট্যাকের শীর্ষ থেকে একটি উপাদান বের করা।
• peek: স্ট্যাকের শীর্ষে থাকা উপাদান দেখা (যা স্ট্যাক থেকে বের করা হয় না)।
• isEmpty: স্ট্যাকটি খালি কিনা তা পরীক্ষা করা।

উদাহরণ:

-- স্ট্যাক কনস্ট্রাক্টর
function createStack()
    return {items = {}, size = 0}
end

-- পুশ ফাংশন (স্ট্যাকে নতুন উপাদান যোগ করা)
function push(stack, item)
    stack.size = stack.size + 1
    stack.items[stack.size] = item
end

-- পপ ফাংশন (স্ট্যাক থেকে উপাদান বের করা)
function pop(stack)
    if stack.size == 0 then
        return nil  -- স্ট্যাক খালি হলে nil ফেরত দিবে
    else
        local item = stack.items[stack.size]
        stack.items[stack.size] = nil  -- ঐ উপাদানটি মুছে ফেলা
        stack.size = stack.size - 1
        return item
    end
end

-- পিক ফাংশন (স্ট্যাকের শীর্ষে থাকা উপাদান দেখা)
function peek(stack)
    return stack.items[stack.size]
end

-- স্ট্যাকের শীর্ষে উপাদান আছে কিনা পরীক্ষা করা
function isEmpty(stack)
    return stack.size == 0
end

-- স্ট্যাক তৈরি করা
local stack = createStack()

-- কিছু উপাদান পুশ করা
push(stack, 10)
push(stack, 20)
push(stack, 30)

print(peek(stack))  -- আউটপুট: 30

-- কিছু উপাদান পপ করা
print(pop(stack))  -- আউটপুট: 30
print(pop(stack))  -- আউটপুট: 20

print(isEmpty(stack))  -- আউটপুট: false

print(pop(stack))  -- আউটপুট: 10
print(isEmpty(stack))  -- আউটপুট: true

এখানে, createStack ফাংশন স্ট্যাক তৈরি করে, push ফাংশন স্ট্যাকের শীর্ষে উপাদান যোগ করে, pop ফাংশন শীর্ষ থেকে উপাদান বের করে, এবং peek ফাংশন শীর্ষে থাকা উপাদান দেখার জন্য ব্যবহৃত হয়।

সারসংক্ষেপ

লুয়া ভাষায় লিঙ্কড লিস্ট এবং স্ট্যাক ইমপ্লিমেন্টেশন করতে টেবিল (tables) এবং কিছু ফাংশন ব্যবহৃত হয়।

• লিঙ্কড লিস্ট: এটি একটি চেইন আকারে ডেটা স্টোর করে, যেখানে প্রতিটি নোড পরবর্তী নোডের রেফারেন্স ধারণ করে। লুয়া টেবিল এবং মেটাটেবিল ব্যবহার করে লিঙ্কড লিস্ট তৈরি করা হয়।
• স্ট্যাক: এটি একটি লিনিয়ার ডেটা স্ট্রাকচার যা LIFO (Last In, First Out) নিয়ম অনুসরণ করে। স্ট্যাক তৈরি করতে লুয়া টেবিলের মাধ্যমে push, pop, peek এবং isEmpty ফাংশন ব্যবহার করা হয়।

এই ডেটা স্ট্রাকচারগুলি বিভিন্ন প্রোগ্রামিং সমস্যার সমাধান সহজ এবং কার্যকরী করে তোলে।