লুয়া (Lua) একটি শক্তিশালী স্ক্রিপ্টিং ভাষা, যা সাধারণ ডেটা স্ট্রাকচার যেমন অ্যারে, টেবিল, সেট, ম্যাপ ইত্যাদি সমর্থন করে। তবে কখনও কখনও আপনার প্রয়োজন হতে পারে আরো উন্নত ডেটা স্ট্রাকচারগুলির, যেমন গ্রাফ (graphs), হ্যাশ টেবিল (hash tables), হিপ (heaps), ট্রি (trees), স্ট্যাক (stacks), কিউ (queues), এবং সঠিকভাবে মেমরি ব্যবস্থাপনা (memory management) করা। এই ধরনের অ্যাডভান্সড ডেটা স্ট্রাকচারগুলি ব্যবহারের মাধ্যমে আপনি আরও দ্রুত এবং কার্যকরী কোড তৈরি করতে পারবেন।
লুয়া ভাষায় এই ধরনের ডেটা স্ট্রাকচারগুলি কিছুটা স্বাভাবিক না হলেও আপনি সহজেই কাস্টম ক্লাস এবং মেটাটেবিল ব্যবহার করে এগুলি তৈরি করতে পারেন।
১. স্ট্যাক (Stack)
স্ট্যাক একটি লিনিয়ার ডেটা স্ট্রাকচার যা LIFO (Last In First Out) নীতি অনুসরণ করে, অর্থাৎ শেষের উপাদানটি প্রথমে বের হয়। আপনি স্ট্যাকের জন্য দুটি মৌলিক অপারেশন ব্যবহার করতে পারেন: push (উপাদান ঢোকানো) এবং pop (উপাদান বের করা)।
উদাহরণ:
Stack = {}
function Stack:new()
local stack = {}
setmetatable(stack, self)
self.__index = self
return stack
end
function Stack:push(value)
table.insert(self, value)
end
function Stack:pop()
return table.remove(self)
end
-- ব্যবহার
local stack = Stack:new()
stack:push(10)
stack:push(20)
stack:push(30)
print(stack:pop()) -- আউটপুট: 30
print(stack:pop()) -- আউটপুট: 20এখানে, Stack একটি কাস্টম স্ট্যাক অবজেক্ট তৈরি করেছে এবং push ও pop মেথডগুলি দিয়ে স্ট্যাক অপারেশন সম্পাদন করা হয়েছে।
২. কিউ (Queue)
কিউ একটি লিনিয়ার ডেটা স্ট্রাকচার যা FIFO (First In First Out) নীতি অনুসরণ করে, অর্থাৎ প্রথমে ঢোকানো উপাদানটি প্রথমে বের হয়। কিউতে দুটি মৌলিক অপারেশন থাকে: enqueue (উপাদান ঢোকানো) এবং dequeue (উপাদান বের করা)।
উদাহরণ:
Queue = {}
function Queue:new()
local queue = {}
setmetatable(queue, self)
self.__index = self
return queue
end
function Queue:enqueue(value)
table.insert(self, value)
end
function Queue:dequeue()
return table.remove(self, 1)
end
-- ব্যবহার
local queue = Queue:new()
queue:enqueue(10)
queue:enqueue(20)
queue:enqueue(30)
print(queue:dequeue()) -- আউটপুট: 10
print(queue:dequeue()) -- আউটপুট: 20এখানে, Queue একটি কাস্টম কিউ অবজেক্ট তৈরি করেছে এবং enqueue ও dequeue মেথডগুলি দিয়ে কিউ অপারেশন সম্পাদন করা হয়েছে।
৩. হ্যাশ টেবিল (Hash Table)
লুয়া ভাষায় হ্যাশ টেবিল একটি গুরুত্বপূর্ণ ডেটা স্ট্রাকচার, যা কী-ভ্যালু পেয়ার স্টোর করে। এটি সাধারণত অ্যারে বা ডিকশনারি হিসেবে কাজ করে এবং এক্সেস টাইম O(1) এর মতো থাকে।
উদাহরণ:
hash_table = {}
function hash_table:set(key, value)
self[key] = value
end
function hash_table:get(key)
return self[key]
end
-- ব্যবহার
hash_table:set("name", "Alice")
hash_table:set("age", 30)
print(hash_table:get("name")) -- আউটপুট: Alice
print(hash_table:get("age")) -- আউটপুট: 30এখানে, hash_table একটি কাস্টম হ্যাশ টেবিল তৈরি করা হয়েছে, যেখানে কী-ভ্যালু পেয়ার সংরক্ষণ করা হচ্ছে এবং সহজে এক্সেস করা হচ্ছে।
৪. ট্রি (Tree)
ট্রি একটি হায়ারার্কিকাল ডেটা স্ট্রাকচার, যা গাছের মতো শাখা-প্রশাখায় বিভক্ত থাকে। সাধারণত বাইনারি ট্রি (Binary Tree) বা বাইনারি সার্চ ট্রি (Binary Search Tree) ব্যবহার করা হয়।
উদাহরণ: বাইনারি ট্রি (Binary Tree)
BinaryTree = {}
function BinaryTree:new(value)
local tree = {value = value, left = nil, right = nil}
setmetatable(tree, self)
self.__index = self
return tree
end
function BinaryTree:insert(value)
if value < self.value then
if self.left == nil then
self.left = BinaryTree:new(value)
else
self.left:insert(value)
end
else
if self.right == nil then
self.right = BinaryTree:new(value)
else
self.right:insert(value)
end
end
end
-- ব্যবহার
root = BinaryTree:new(10)
root:insert(5)
root:insert(15)
root:insert(12)
print(root.left.value) -- আউটপুট: 5
print(root.right.value) -- আউটপুট: 15এখানে, একটি বাইনারি ট্রি তৈরি করা হয়েছে যেখানে insert মেথড ব্যবহার করে মান ইনসার্ট করা হচ্ছে এবং ট্রির মধ্যে ডেটা রাখা হচ্ছে।
৫. গ্রাফ (Graph)
গ্রাফ একটি জটিল ডেটা স্ট্রাকচার, যা নোড (nodes) এবং তাদের মধ্যে সম্পর্ক (edges) সংরক্ষণ করে। এটি বিভিন্ন সমস্যার সমাধানে যেমন সোশ্যাল নেটওয়ার্ক, ওয়েব পেজ লিংক, রাস্তা বা যানবাহনের নেটওয়ার্ক ইত্যাদিতে ব্যবহৃত হয়।
উদাহরণ:
Graph = {}
function Graph:new()
local graph = {nodes = {}}
setmetatable(graph, self)
self.__index = self
return graph
end
function Graph:add_node(node)
self.nodes[node] = {}
end
function Graph:add_edge(node1, node2)
table.insert(self.nodes[node1], node2)
table.insert(self.nodes[node2], node1)
end
-- ব্যবহার
g = Graph:new()
g:add_node("A")
g:add_node("B")
g:add_node("C")
g:add_edge("A", "B")
g:add_edge("B", "C")
for _, neighbor in ipairs(g.nodes["B"]) do
print(neighbor) -- আউটপুট: A, C
endএখানে, Graph একটি গ্রাফ তৈরি করা হয়েছে এবং add_node এবং add_edge মেথড দিয়ে গ্রাফে নোড এবং সম্পর্ক (এজ) যোগ করা হয়েছে।
সারসংক্ষেপ
লুয়া ভাষায় অ্যাডভান্সড ডেটা স্ট্রাকচার তৈরি এবং ব্যবহারের জন্য বিভিন্ন কাস্টম ক্লাস এবং মেটাটেবিল ব্যবহার করা হয়। এই ধরনের স্ট্রাকচারগুলো যেমন স্ট্যাক, কিউ, হ্যাশ টেবিল, ট্রি, এবং গ্রাফ আমাদের কমপ্লেক্স ডেটা ম্যানিপুলেশন করতে সহায়তা করে এবং দক্ষতার সাথে বিভিন্ন সমস্যার সমাধান করতে সক্ষম করে।
লুয়া ভাষায় লিঙ্কড লিস্ট এবং স্ট্যাক ডেটা স্ট্রাকচারগুলোর ইমপ্লিমেন্টেশন করার জন্য সাধারণত টেবিল (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ফাংশন ব্যবহার করা হয়।
এই ডেটা স্ট্রাকচারগুলি বিভিন্ন প্রোগ্রামিং সমস্যার সমাধান সহজ এবং কার্যকরী করে তোলে।
লুয়া (Lua) ভাষায় কিউ (Queue) এবং প্রায়োরিটি কিউ (Priority Queue) তৈরি করতে টেবিল (Tables) এবং কিছু কাস্টম লজিক ব্যবহার করা হয়। কিউ একটি ডেটা স্ট্রাকচার যা FIFO (First In, First Out) প্রিন্সিপল অনুসরণ করে, অর্থাৎ প্রথমে প্রবেশ করা উপাদান প্রথমে বের হয়। অন্যদিকে, প্রায়োরিটি কিউ উপাদানগুলোকে তাদের প্রাধান্য (priority) অনুসারে সাজিয়ে রাখে, যাতে উচ্চ প্রাধান্য সম্পন্ন উপাদানগুলি আগে বের হয়।
এই টিউটোরিয়ালে আমরা কিউ এবং প্রায়োরিটি কিউ তৈরি করার পদ্ধতি দেখব।
১. কিউ (Queue) তৈরি করা
কিউ (Queue) একটি সাধারণ ডেটা স্ট্রাকচার যা FIFO প্রিন্সিপল অনুসরণ করে। আমরা এটি একটি টেবিল ব্যবহার করে তৈরি করতে পারি, যেখানে enqueue এবং dequeue অপারেশনগুলো কাজ করবে।
কিউ তৈরি করা:
Queue = {}
Queue.__index = Queue
-- কিউ কন্সট্রাক্টর
function Queue.new()
return setmetatable({items = {}}, Queue)
end
-- এনকিউ (enqueue): নতুন আইটেম কিউতে যোগ করা
function Queue:enqueue(item)
table.insert(self.items, item)
end
-- ডিকিউ (dequeue): কিউ থেকে প্রথম আইটেম বের করা
function Queue:dequeue()
if #self.items == 0 then
return nil, "Queue is empty"
end
return table.remove(self.items, 1)
end
-- কিউয়ের সাইজ
function Queue:size()
return #self.items
end
-- কিউয়ের প্রথম আইটেম
function Queue:peek()
return self.items[1]
endএখানে, আমরা Queue টেবিলটি কিউ ক্লাস হিসেবে ব্যবহার করেছি। কিউ তৈরি করতে Queue.new() ফাংশনটি ব্যবহার করা হয়েছে, যা একটি খালি টেবিল রিটার্ন করবে। enqueue ফাংশনটি নতুন উপাদান কিউতে যোগ করে এবং dequeue ফাংশনটি কিউ থেকে প্রথম উপাদান বের করে।
কিউ ব্যবহার করা:
local queue = Queue.new()
-- এনকিউ (enqueue)
queue:enqueue("Item 1")
queue:enqueue("Item 2")
queue:enqueue("Item 3")
print(queue:dequeue()) -- আউটপুট: Item 1
print(queue:dequeue()) -- আউটপুট: Item 2
print(queue:dequeue()) -- আউটপুট: Item 3এখানে, তিনটি আইটেম কিউতে যোগ করা হয়েছে এবং পরে ডিকিউ করে সেগুলি বের করা হয়েছে।
২. প্রায়োরিটি কিউ (Priority Queue) তৈরি করা
প্রায়োরিটি কিউ একটি কিউ টাইপ, যেখানে উপাদানগুলির প্রাধান্য থাকে এবং উপাদানগুলো তাদের প্রাধান্যের ভিত্তিতে কিউ থেকে বের হয়। এই কিউতে সাধারণত প্রতিটি উপাদান একটি প্রাধান্য সঙ্গে থাকে এবং সেই অনুযায়ী উপাদানগুলো বের করা হয়।
প্রায়োরিটি কিউ তৈরি করা:
PriorityQueue = {}
PriorityQueue.__index = PriorityQueue
-- প্রায়োরিটি কিউ কন্সট্রাক্টর
function PriorityQueue.new()
return setmetatable({items = {}}, PriorityQueue)
end
-- এনকিউ (enqueue): নতুন আইটেম কিউতে যোগ করা, প্রাধান্য অনুসারে
function PriorityQueue:enqueue(item, priority)
table.insert(self.items, {item = item, priority = priority})
table.sort(self.items, function(a, b)
return a.priority > b.priority -- উচ্চ প্রাধান্য প্রথমে থাকবে
end)
end
-- ডিকিউ (dequeue): কিউ থেকে সর্বোচ্চ প্রাধান্য সম্পন্ন আইটেম বের করা
function PriorityQueue:dequeue()
if #self.items == 0 then
return nil, "Priority Queue is empty"
end
return table.remove(self.items, 1).item
end
-- কিউয়ের সাইজ
function PriorityQueue:size()
return #self.items
endএখানে, PriorityQueue টেবিলটি প্রায়োরিটি কিউ ক্লাস হিসেবে ব্যবহৃত হচ্ছে। enqueue ফাংশনে উপাদান এবং তার প্রাধান্য পাস করা হয় এবং table.sort ব্যবহার করে উপাদানগুলো প্রাধান্য অনুসারে সাজানো হয়।
প্রায়োরিটি কিউ ব্যবহার করা:
local pq = PriorityQueue.new()
-- এনকিউ (enqueue) বিভিন্ন প্রাধান্য সহ
pq:enqueue("Item 1", 1)
pq:enqueue("Item 2", 3)
pq:enqueue("Item 3", 2)
print(pq:dequeue()) -- আউটপুট: Item 2 (হাই প্রিয়োরিটি)
print(pq:dequeue()) -- আউটপুট: Item 3
print(pq:dequeue()) -- আউটপুট: Item 1 (লো প্রিয়োরিটি)এখানে, প্রথমে প্রাধান্য অনুসারে আইটেমগুলো কিউতে যোগ করা হয়েছে এবং পরে তাদের প্রাধান্য অনুসারে ডিকিউ করা হয়েছে।
সারসংক্ষেপ
লুয়া ভাষায় কিউ এবং প্রায়োরিটি কিউ তৈরি করতে টেবিল (tables) ব্যবহার করা হয় এবং ফাংশনগুলোর মাধ্যমে কিউয়ের বিভিন্ন কার্যকলাপ পরিচালিত হয়:
- কিউ (Queue) FIFO (First In, First Out) প্রিন্সিপল অনুসরণ করে।
- প্রায়োরিটি কিউ (Priority Queue) একটি প্রাধান্য ভিত্তিক কিউ, যেখানে উপাদানগুলোর প্রাধান্য অনুযায়ী সাজানো হয় এবং বের করা হয়।
এই ডেটা স্ট্রাকচারগুলি লুয়া ভাষায় অনেক কার্যক্রম যেমন টাস্ক ম্যানেজমেন্ট, ইভেন্ট হ্যান্ডলিং ইত্যাদিতে ব্যবহৃত হতে পারে।
লুয়া (Lua) ভাষায় গাছ (Trees) এবং গ্রাফ (Graphs) ডেটা স্ট্রাকচার তৈরি এবং পরিচালনা করা খুবই নমনীয় এবং সহজ। কারণ, লুয়া টেবিলগুলি (tables) ডেটা সংরক্ষণের জন্য একটি সাধারণ, শক্তিশালী এবং নমনীয় উপায় প্রদান করে। আমরা এখানে গাছ (Trees) এবং গ্রাফ (Graphs) ডেটা স্ট্রাকচারগুলি তৈরি করার জন্য টেবিল এবং কিছু বেসিক এলগরিদম নিয়ে আলোচনা করব।
১. গাছ (Trees)
গাছ (Tree) হল একটি হায়ারার্কিক্যাল ডেটা স্ট্রাকচার যা নোড (Node) দ্বারা গঠিত। প্রতিটি নোডের মধ্যে একটি মান থাকে এবং এটি এক বা একাধিক চাইল্ড নোডের সাথে যুক্ত থাকে। গাছের সবচেয়ে শীর্ষে থাকা নোডটিকে রুট (Root) বলা হয়।
গাছের উপাদান:
- নোড (Node): একটি গাছের মৌলিক একক, যা একটি ডেটা ধারণ করে।
- রুট (Root): গাছের শীর্ষ নোড।
- চাইল্ড (Child): কোন নোডের নিচের স্তরের নোড।
- লিফ (Leaf): যে নোডে কোনো চাইল্ড নোড নেই।
উদাহরণ: বাইনারি গাছ (Binary Tree)
একটি সিম্পল বাইনারি গাছ তৈরি করা, যেখানে প্রতিটি নোডে সর্বাধিক দুটি চাইল্ড নোড থাকতে পারে:
-- একটি বাইনারি গাছের জন্য নোড তৈরি
Node = {}
Node.__index = Node
function Node.new(value)
local self = setmetatable({}, Node)
self.value = value
self.left = nil
self.right = nil
return self
end
-- গাছের মধ্যে মান যোগ করার ফাংশন
function insert(root, value)
if root == nil then
return Node.new(value)
end
if value < root.value then
root.left = insert(root.left, value)
else
root.right = insert(root.right, value)
end
return root
end
-- গাছটি ইন অর্ডার (Inorder) ট্র্যাভার্স করার ফাংশন
function inorderTraversal(root)
if root ~= nil then
inorderTraversal(root.left)
print(root.value)
inorderTraversal(root.right)
end
end
-- গাছ তৈরি করা এবং মান ইনসার্ট করা
local root = Node.new(10)
insert(root, 5)
insert(root, 15)
insert(root, 3)
insert(root, 7)
insert(root, 12)
insert(root, 17)
-- গাছের মান ইনঅর্ডারে প্রিন্ট করা
inorderTraversal(root) -- আউটপুট: 3 5 7 10 12 15 17এখানে, আমরা একটি বাইনারি গাছ তৈরি করেছি এবং ইনঅর্ডার ট্র্যাভার্সাল ব্যবহার করে গাছের মধ্যে থাকা মানগুলো প্রিন্ট করেছি।
২. গ্রাফ (Graphs)
গ্রাফ (Graph) একটি গাছের মতো কিন্তু এটি সাইকেল (cycle) ধারণ করতে পারে, এবং প্রতিটি নোড (vertex) একাধিক সংযোগ (edge) দ্বারা অন্যান্য নোডের সাথে যুক্ত থাকতে পারে। গ্রাফে নোড এবং এজ (যে দুটি নোডের মধ্যে সম্পর্ক তৈরি করে) থাকে।
গ্রাফের উপাদান:
- নোড (Vertex): গ্রাফের একটি বিন্দু বা উপাদান।
- এজ (Edge): দুটি নোডের মধ্যে সম্পর্ক।
- ডিরেক্টেড গ্রাফ (Directed Graph): যেখানে এজের দিকে নির্দেশ থাকে।
- আনডিরেক্টেড গ্রাফ (Undirected Graph): যেখানে এজের কোন দিক নির্দেশিত থাকে না।
উদাহরণ: আনডিরেক্টেড গ্রাফ (Undirected Graph)
লুয়া ভাষায় গ্রাফের তৈরি এবং পরিচালনা করার জন্য আমরা একটি সিম্পল টেবিল ব্যবহার করতে পারি।
-- একটি গ্রাফ তৈরি করার জন্য টেবিল ব্যবহার
Graph = {}
Graph.__index = Graph
function Graph.new()
local self = setmetatable({}, Graph)
self.nodes = {}
return self
end
-- গ্রাফে একটি নতুন নোড যোগ করার ফাংশন
function Graph:addNode(node)
if not self.nodes[node] then
self.nodes[node] = {}
end
end
-- গ্রাফে দুটি নোডের মধ্যে একটি এজ যোগ করার ফাংশন
function Graph:addEdge(node1, node2)
if not self.nodes[node1] then
self:addNode(node1)
end
if not self.nodes[node2] then
self:addNode(node2)
end
table.insert(self.nodes[node1], node2)
table.insert(self.nodes[node2], node1)
end
-- গ্রাফ প্রিন্ট করার ফাংশন
function Graph:printGraph()
for node, edges in pairs(self.nodes) do
print(node .. " is connected to " .. table.concat(edges, ", "))
end
end
-- গ্রাফ তৈরি এবং এজ যোগ করা
local g = Graph.new()
g:addNode("A")
g:addNode("B")
g:addNode("C")
g:addEdge("A", "B")
g:addEdge("A", "C")
g:addEdge("B", "C")
-- গ্রাফ প্রিন্ট করা
g:printGraph()
-- আউটপুট:
-- A is connected to B, C
-- B is connected to A, C
-- C is connected to A, Bএখানে, একটি আনডিরেক্টেড গ্রাফ তৈরি করা হয়েছে, যেখানে নোডগুলি পরস্পর সংযুক্ত রয়েছে। addEdge ফাংশনটি দুটি নোডের মধ্যে একটি সম্পর্ক তৈরি করে, এবং printGraph ফাংশনটি গ্রাফটি প্রিন্ট করে।
৩. গ্রাফের ট্র্যাভার্সাল (Graph Traversal)
গ্রাফের মধ্যে ভ্রমণ বা ট্র্যাভার্সাল দুটি প্রধান পদ্ধতিতে করা হয়:
- ডেপথ-ফার্স্ট সার্চ (DFS): একটি নোডের গভীরে প্রবেশ করা এবং পরে পাশের নোডগুলো পরীক্ষা করা।
- ব্রেডথ-ফার্স্ট সার্চ (BFS): নোডগুলির পাশের সব নোড একসাথে পরীক্ষা করা।
উদাহরণ: ডেপথ-ফার্স্ট সার্চ (DFS)
function dfs(graph, node, visited)
if not visited[node] then
print(node)
visited[node] = true
for _, neighbor in ipairs(graph.nodes[node]) do
dfs(graph, neighbor, visited)
end
end
end
local g = Graph.new()
g:addNode("A")
g:addNode("B")
g:addNode("C")
g:addNode("D")
g:addEdge("A", "B")
g:addEdge("A", "C")
g:addEdge("B", "D")
-- DFS ট্র্যাভার্সাল
local visited = {}
dfs(g, "A", visited)
-- আউটপুট:
-- A
-- B
-- D
-- Cএখানে, dfs ফাংশনটি একটি গ্রাফে ডেপথ-ফার্স্ট সার্চের মাধ্যমে নোডগুলো পরিদর্শন করছে।
সারসংক্ষেপ
- গাছ (Tree): গাছ হল একটি হায়ারার্কিক্যাল ডেটা স্ট্রাকচার যেখানে একটি রুট নোড এবং এর সাব-নোডগুলো থাকে। লুয়া টেবিল ব্যবহার করে গাছ তৈরি করা সহজ।
- গ্রাফ (Graph): গ্রাফ হল একটি জটিল ডেটা স্ট্রাকচার যেখানে নোডগুলো একে অপরের সাথে সংযুক্ত থাকে। গ্রাফ তৈরি এবং পরিচালনা করার জন্য টেবিল ব্যবহার করা হয়।
- গ্রাফ ট্র্যাভার্সাল: গ্রাফের মধ্যে ভ্রমণ করতে ডেপথ-ফার্স্ট এবং ব্রেডথ-ফার্স্ট সার্চ পদ্ধতি ব্যবহার করা হয়।
লুয়া ভাষায় গাছ এবং গ্রাফ নিয়ে কাজ করা সহজ এবং ফ্লেক্সিবল, যেহেতু টেবিলগুলি অত্যন্ত নমনীয় ডেটা স্ট্রাকচার।
লুয়া (Lua) একটি ডায়নামিক টাইপিং ভাষা এবং এর টেবিল (table) ডেটা স্ট্রাকচার খুবই শক্তিশালী এবং নমনীয়। লুয়া টেবিল ব্যবহার করে আপনি একাধিক ডেটা টাইপের সংমিশ্রণ তৈরি করতে পারেন, যার মাধ্যমে জটিল (complex) ডেটা স্ট্রাকচার তৈরি করা যায়। এতে আপনি অ্যারে, ম্যাপ, স্ট্যাক, কিউ, গ্রাফ, হ্যাশ টেবিল ইত্যাদি বিভিন্ন ধরনের ডেটা স্ট্রাকচার তৈরি করতে পারেন।
এই টিউটোরিয়ালে, আমরা লুয়া ভাষায় কমপ্লেক্স ডেটা স্ট্রাকচার এবং তাদের ব্যবহার বিস্তারিতভাবে আলোচনা করব।
১. অ্যারে (Arrays)
লুয়া ভাষায় অ্যারে সাধারণত টেবিল ব্যবহার করে তৈরি করা হয়, যেখানে টেবিলের ইনডেক্সগুলি সংখ্যার ভিত্তিতে থাকে। একটি অ্যারে হল ডেটার একটি সিকোয়েন্স বা তালিকা যেখানে ইনডেক্সগুলি ধারাবাহিকভাবে বৃদ্ধি পায় (১, ২, ৩, ...)
উদাহরণ:
local fruits = {"Apple", "Banana", "Cherry"}
-- অ্যারে অ্যাক্সেস
print(fruits[1]) -- আউটপুট: Apple
print(fruits[2]) -- আউটপুট: Bananaএখানে, fruits একটি সাধারণ অ্যারে যেটি তিনটি ফলের নাম ধারণ করছে। অ্যারে ইনডেক্সিং শুরু হয় ১ থেকে।
২. ম্যাপ (Maps)
লুয়া ভাষায় ম্যাপ তৈরি করতে আপনি একটি টেবিল ব্যবহার করেন যেখানে কীগুলি (keys) এবং মানগুলি (values) সংযুক্ত থাকে। এই স্ট্রাকচারটি ডিকশনারি বা হ্যাশ টেবিলের মতো কাজ করে।
উদাহরণ:
local person = {
name = "Alice",
age = 30,
occupation = "Engineer"
}
-- ম্যাপের মান অ্যাক্সেস
print(person["name"]) -- আউটপুট: Alice
print(person["age"]) -- আউটপুট: 30এখানে, person একটি ম্যাপ যেখানে প্রতিটি কী (যেমন "name", "age", "occupation") এর সাথে একটি মান যুক্ত আছে। আপনি কী ব্যবহার করে মান অ্যাক্সেস করতে পারেন।
৩. স্ট্যাক (Stack)
স্ট্যাক একটি ডেটা স্ট্রাকচার যা Last In, First Out (LIFO) নীতিতে কাজ করে, অর্থাৎ যে উপাদানটি সর্বশেষ ইনপুট হবে, সেটি প্রথমে বের হবে।
উদাহরণ:
local stack = {}
-- স্ট্যাক এlement যোগ করা (push)
table.insert(stack, "A")
table.insert(stack, "B")
table.insert(stack, "C")
-- স্ট্যাক থেকে উপাদান বের করা (pop)
local poppedItem = table.remove(stack)
print(poppedItem) -- আউটপুট: C
poppedItem = table.remove(stack)
print(poppedItem) -- আউটপুট: Bএখানে, table.insert ব্যবহার করে উপাদান স্ট্যাকে যোগ করা হচ্ছে এবং table.remove ব্যবহার করে সর্বশেষ যোগ করা উপাদান বের করা হচ্ছে, যা স্ট্যাকের LIFO আচরণ অনুসরণ করে।
৪. কিউ (Queue)
কিউ একটি ডেটা স্ট্রাকচার যা First In, First Out (FIFO) নীতিতে কাজ করে, অর্থাৎ যে উপাদানটি প্রথমে ইনপুট হবে, সেটি প্রথমে বের হবে।
উদাহরণ:
local queue = {}
-- কিউতে উপাদান যোগ করা (enqueue)
table.insert(queue, "A")
table.insert(queue, "B")
table.insert(queue, "C")
-- কিউ থেকে উপাদান বের করা (dequeue)
local dequeuedItem = table.remove(queue, 1)
print(dequeuedItem) -- আউটপুট: A
dequeuedItem = table.remove(queue, 1)
print(dequeuedItem) -- আউটপুট: Bএখানে, table.insert ব্যবহার করে কিউতে উপাদান যোগ করা হচ্ছে এবং table.remove(queue, 1) ব্যবহার করে কিউয়ের প্রথম উপাদান বের করা হচ্ছে, যা FIFO নীতি অনুসরণ করে।
৫. গ্রাফ (Graph)
গ্রাফ একটি জটিল ডেটা স্ট্রাকচার যা নোড (nodes) এবং এজ (edges) দিয়ে তৈরি হয়। এটি সাধারণত সংযোগ বা সম্পর্ক তৈরি করতে ব্যবহৃত হয়। লুয়া ভাষায় গ্রাফ সিম্পল টেবিলের মাধ্যমে তৈরি করা যায়।
উদাহরণ:
local graph = {
A = {B = true, C = true},
B = {A = true, D = true},
C = {A = true, D = true},
D = {B = true, C = true}
}
-- গ্রাফের প্রতিবেশী নোডগুলি অ্যাক্সেস
for neighbor, _ in pairs(graph["A"]) do
print(neighbor) -- আউটপুট: B, C
endএখানে, graph একটি গ্রাফ যেখানে প্রতিটি নোড (যেমন "A", "B") তার প্রতিবেশী নোডগুলির সাথে যুক্ত। pairs ফাংশন ব্যবহার করে আমরা "A" নোডের প্রতিবেশী নোডগুলির সাথে সংযোগ দেখতে পাচ্ছি।
৬. হ্যাশ টেবিল (Hash Table)
হ্যাশ টেবিল একটি ম্যাপের মতো, তবে এটি কীগুলিকে দ্রুত অ্যাক্সেস করার জন্য হ্যাশ ফাংশন ব্যবহার করে। লুয়া টেবিল আসলে একটি হ্যাশ টেবিল।
উদাহরণ:
local hashTable = {}
-- হ্যাশ টেবিলে ডেটা ইনসার্ট
hashTable["key1"] = "value1"
hashTable["key2"] = "value2"
hashTable["key3"] = "value3"
-- হ্যাশ টেবিলের মান অ্যাক্সেস
print(hashTable["key1"]) -- আউটপুট: value1
print(hashTable["key2"]) -- আউটপুট: value2এখানে, hashTable একটি সাধারণ হ্যাশ টেবিল যা কীগুলির সাথে মান সংরক্ষণ করছে। আপনি কী ব্যবহার করে মান অ্যাক্সেস করতে পারেন।
৭. Multidimensional Arrays (বহু-মাত্রিক অ্যারে)
লুয়া ভাষায় বহু-মাত্রিক অ্যারে (যেমন ম্যাট্রিক্স) তৈরি করতে একাধিক টেবিল ব্যবহার করা হয়।
উদাহরণ:
local matrix = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
}
-- ম্যাট্রিক্সের উপাদান অ্যাক্সেস
print(matrix[1][1]) -- আউটপুট: 1
print(matrix[2][3]) -- আউটপুট: 6এখানে, matrix একটি দুই-মাত্রিক অ্যারে (ম্যাট্রিক্স) যা ৩টি সারি এবং ৩টি কলাম ধারণ করছে। আপনি সাধারণ অ্যারে অ্যাক্সেসের মতো matrix[row][column] ব্যবহার করে উপাদান অ্যাক্সেস করতে পারেন।
সারসংক্ষেপ
লুয়া ভাষায় টেবিল ব্যবহার করে আপনি বিভিন্ন ধরনের কমপ্লেক্স ডেটা স্ট্রাকচার তৈরি করতে পারেন। এই ডেটা স্ট্রাকচারগুলোর মধ্যে রয়েছে:
- অ্যারে: ধারাবাহিক ডেটা সংরক্ষণ করতে ব্যবহৃত।
- ম্যাপ: কী এবং মানের সংমিশ্রণ, যা ডিকশনারির মতো কাজ করে।
- স্ট্যাক: LIFO (Last In, First Out) ভিত্তিতে কাজ করে।
- কিউ: FIFO (First In, First Out) ভিত্তিতে কাজ করে।
- গ্রাফ: নোড এবং এজ দ্বারা সম্পর্কিত ডেটা সংরক্ষণ।
- হ্যাশ টেবিল: দ্রুত কী-ভ্যালু পেয়ার অ্যাক্সেস।
- বহু-মাত্রিক অ্যারে: ২ বা তার বেশি মাত্রিক অ্যারে।
লুয়া ভাষায় এই ডেটা স্ট্রাকচারগুলির মাধ্যমে আপনি জটিল ডেটা ম্যানিপুলেশন সহজেই করতে পারেন, এবং এগুলির নমনীয়তা এবং কার্যকারিতা অনেক প্রোগ্রামিং কাজকে সহজ করে তোলে।
Read more
