What is Data Structure?
ডেটা স্ট্রাকচার( Data Structure) হল একটি স্টোরেজ যা ডেটা সংরক্ষণ এবং সংগঠিত করতে ব্যবহৃত হয়। এটি একটি কম্পিউটারে ডেটা সাজানোর একটি উপায় যাতে এটি অ্যাক্সেস করা যায় এবং দক্ষতার সাথে আপডেট করা যায়।
Type of Data structure
মূলত, ডেটা স্ট্রাকচার দুটি বিভাগে বিভক্ত: 1) Linear data structure 2) Non-linear data structure
Linear data structure: উপাদানগুলিকে একের পর এক ক্রমানুসারে সাজানো হয়। যেহেতু উপাদানগুলি নির্দিষ্ট ক্রমে সাজানো হয়েছে, সেগুলি বাস্তবায়ন করা সহজ।
জনপ্রিয় Data structure গুলি হলঃ-
- Array
- Stack
- Queue
- Link List
Non-linear data structure:
Non-linear data structure বলতে এমন ডেটা স্ট্রাকচারগুলিকে(Data structure) বোঝায় যারা লিনিয়ার বা সরলরেখীয় নয়। এই ধরনের ডেটা স্ট্রাকচারে উপাদানগুলি সরলভাবে সাজানো থাকে না।
উদাহরণ:
- ট্রি (Tree) – ট্রিতে উপাদানগুলি হাইয়ারার্কিকাল ভাবে সাজানো থাকে, যেখানে প্রতিটি উপাদানের এক বা একাধিক চাইল্ড নোড থাকে।
- গ্রাফ (Graph) – গ্রাফে উপাদানগুলির মধ্যে যে কোন দিকে যোগাযোগ থাকতে পারে।
- লিংকড লিস্ট (Linked List) – লিংকড লিস্টে উপাদানগুলি লিনিয়ার না হয়ে পরস্পর লিঙ্ক করে থাকে।
- হ্যাশ টেবিল (Hash Table) – হ্যাশ টেবিলে ডেটা হ্যাশ ফাংশন ব্যবহার করে স্টোর করা হয় যা লিনিয়ার ইনডেক্সিং-এর চেয়ে দ্রুত অ্যাক্সেস দেয়।
সাধারণত, নন-লিনিয়ার ডেটা স্ট্রাকচারগুলি (Non-linear data structure লিনিয়ার ডেটা স্ট্রাকচার চেয়ে জটিল হলেও কিছু ক্ষেত্রে সেগুলি বেশি দক্ষতার সাথে কাজ করে।
Linear এবং Non-linear data structure এর মধ্যে পার্থক্য লেখ ?
| Type | Linear Data Structure | Non-linear Data Structure |
|---|---|---|
| সংজ্ঞা | ডেটাগুলি একটি সিকোয়েন্স বা সরলরেখায় সাজানো থাকে | ডেটাগুলি সিকোয়েন্স অনুযায়ী সাজানো থাকে না, বরং একটি হায়ারার্কিক্যাল অর্ডারে থাকে |
| উদাহরণ | অ্যারে, লিঙ্কড লিস্ট, স্ট্যাক, কিউ | ট্রি, গ্রাফ |
| অ্যাক্সেস পদ্ধতি | ডেটাগুলি সিকোয়েন্স অনুযায়ী অ্যাক্সেস করা হয়, অর্থাৎ, একটির পরে অন্যটি | ডেটাগুলি একটি নির্দিষ্ট নিয়ম অনুযায়ী অ্যাক্সেস করা হয়, যেমন ট্রি-তে রুট থেকে লিফ পর্যন্ত |
| পরিবর্তন | ডেটা ইনসার্ট এবং ডিলিট করা সহজ | ডেটা ইনসার্ট এবং ডিলিট করা কিছুটা জটিল |
What is Algorithm ?
একটি অ্যালগরিদম একটি নির্দিষ্ট সমস্যা সমাধানের জন্য সুনির্দিষ্ট নির্দেশাবলীর একটি সেট। এটি ইনপুট(গুলি) এর একটি সেট নেয় এবং পছন্দসই আউটপুট তৈরি করে। উদাহরণ স্বরূপ,
দুটি সংখ্যা গুন করার জন্য একটি অ্যালগরিদম:
- দুটি ইনপুট নিতে হবে [Take two number for inputs] যেমন – a,b
- দুটি নাম্বারের গুন করতে হবে [Multiply two number]- a*b
- কোন চলরাশির মাধ্যমে ফলাফল দেখাও[Show result in other variable]।
How to write algorithm?
- ইনপুট এবং আউটপুট সুনির্দিষ্টভাবে সংজ্ঞায়িত করা উচিত।
- অ্যালগরিদমের প্রতিটি ধাপ পরিষ্কার এবং অর্থবহ হওয়া উচিত।
- একটি সমস্যা সমাধানের অ্যালগরিদমগুলি সবচেয়ে কার্যকর হওয়া উচিত৷
- একটি অ্যালগরিদমে কম্পিউটার কোড অন্তর্ভুক্ত করা উচিত নয়৷ পরিবর্তে, অ্যালগরিদমটি এমনভাবে লিখতে হবে যাতে এটি বিভিন্ন প্রোগ্রামিং ভাষায় ব্যবহার করা যায়।
Example: write an algorithm to check whether a number is positive or negative.
//algorithm
Step 1: Start
Step 2: Input any Number
Step 3: Read n
Step 4: if(n==0)
print "Number is 0"
else
if(n>0)
print "Number is positive"
else
print "Number is negative"
step 5: stop
Array and its Operations
Array: Array হলো একটি ডাটা স্ট্রাকচার, যেখানে একই ধরনের একাধিক ডাটা একত্রে ধারাবাহিক মেমোরি লোকেশনে সংরক্ষণ করা যায়। এটি ইনডেক্স ব্যবহার করে ডাটা অ্যাক্সেস করতে সাহায্য করে।
Example:
ধরা যাক, ৫ জন শিক্ষার্থীর নম্বর সংরক্ষণ করতে হবে। ৫টি আলাদা ভ্যারিয়েবল ব্যবহার না করে আমরা একটি অ্যারে ব্যবহার করতে পারি।
int marks[5] = {85, 90, 78, 92, 88};এখানে:
marksহলো অ্যারের নাম।{85, 90, 78, 92, 88}অ্যারের মধ্যে থাকা উপাদান।- ইনডেক্স
0থেকে শুরু হয়ে4পর্যন্ত চলে।
Array Operations:
1. Traverse (ট্রাভার্স)
অ্যারের প্রতিটি এলিমেন্ট একবার করে পরিদর্শন বা অ্যাক্সেস করাকে ট্রাভার্স বলা হয়। ধারণা: অ্যারের প্রতিটি ইন্ডেক্সে একবার করে যেতে হবে এবং ভ্যালুগুলো প্রদর্শন করতে হবে।
1. Start
2. Set i = 0
3. Repeat steps 4 to 5 while i < n
4. Print A[i]
5. i = i + 1
6. EndExplain : এই অ্যালগরিদমে n হল অ্যারের সাইজ। লুপ ব্যবহার করে প্রতিটি এলিমেন্ট প্রিন্ট করা হয়।
2. Searching (সার্চিং)
অ্যারে থেকে একটি নির্দিষ্ট ভ্যালু খুঁজে বের করার প্রক্রিয়া।
ধারণা:
- Linear Search: প্রতিটি এলিমেন্ট চেক করা হয়।
- Binary Search: অ্যারে যদি সর্টেড থাকে, তবে মধ্যবর্তী এলিমেন্ট দেখে দ্রুত ফলাফল পাওয়া যায়।
Linear Search Algorithm:
1. Start
2. Set i = 0
3. Repeat steps 4 to 5 while i < n
4. If A[i] == key
Print "Element found at index i"
Exit
5. i = i + 1
4. Print "Element not found"
5. EndBinary Search Algorithm:
1. Start
2. Set low = 0, high = n - 1
3. Repeat while low <= high:
4. mid = (low + high) / 2
5. If A[mid] == key
Print "Element found at index mid"
Exit
6. Else If A[mid] < key
Set low = mid + 1
7. Else
Set high = mid - 1
4. Print "Element not found"
5. EndExplain: লিনিয়ার সার্চ ধীর কিন্তু সর্টেড না থাকলেও কাজ করে। বাইনারি সার্চ দ্রুত, তবে সর্টেড অ্যারেতে কার্যকর।
3. Insertion (ইনসার্ট)
অ্যারেতে নতুন ভ্যালু যোগ করা।
ধারণা: নতুন এলিমেন্টের জন্য স্থান তৈরি করে নির্দিষ্ট পজিশনে ইনসার্ট করতে হয়।
Algorithm:
1. Start
2. If n >= capacity
Print "Array is Full"
Exit
3. Set i = n - 1
4. Repeat while i >= pos
A[i + 1] = A[i]
i = i - 1
5. A[pos] = value
6. n = n + 1
7. EndExplain: n হল অ্যারের বর্তমান সাইজ, আর capacity হল অ্যারের সর্বোচ্চ সাইজ।
4. Deletion (ডিলিট)
অ্যারে থেকে একটি ভ্যালু সরানোর প্রক্রিয়া।
ধারণা: নির্দিষ্ট পজিশনের এলিমেন্ট মুছে ফেলে বাকি এলিমেন্টগুলোকে শিফট করতে হয়।
Algorithm:
1. Start
2. If pos >= n
Print "Invalid Position"
Exit
3. Set i = pos
4. Repeat while i < n - 1
A[i] = A[i + 1]
i = i + 1
5. n = n - 1
6. EndExplain: পজিশন চেক করা হয়, তারপর এলিমেন্টগুলো শিফট করে অ্যারের সাইজ কমানো হয়।
5. Merging (মার্জিং)
দুটি অ্যারের এলিমেন্টগুলো একত্রিত করে একটি নতুন অ্যারে তৈরি করা।
ধারণা: প্রথম এবং দ্বিতীয় অ্যারের সকল এলিমেন্ট নতুন অ্যারেতে কপি করতে হয়।
Algorithm:
1. Start
2. Set i = 0, j = 0, k = 0
3. Repeat steps 4 and 5 while i < n1
C[k] = A[i]
i = i + 1
k = k + 1
4. Repeat steps 5 and 6 while j < n2
C[k] = B[j]
j = j + 1
k = k + 1
5. EndExplain: A এবং B দুটি অ্যারে এবং C নতুন অ্যারে যেখানে A এবং B এর সকল ডাটা কপি হয়।
Data Structure: Stack
STACK operation with algorithm
স্ট্যাক(Stack) হল একটি লিনিয়ার ডাটা স্ট্রাকচার যা LIFO (Last In First Out) প্রিন্সিপল অনুসরণ করে। স্ট্যাকে প্রধানত নিম্নলিখিত অপারেশনগুলি করা হয়:
PUSH – স্ট্যাকের শীর্ষে একটি উপাদান যোগ করে।
POP – স্ট্যাক থেকে শীর্ষস্থ উপাদানটি সরিয়ে নেয়।
PEEK – স্ট্যাকের শীর্ষস্থ উপাদানটি রিটার্ন করে তবে সরিয়ে নেয় না।
স্ট্যাক(Stack) সম্পর্কে কিছু গুরুত্বপূর্ণ বিষয়:
- স্ট্যাক শুধুমাত্র উপরের উপাদানটির অ্যাক্সেস করা হয়। নিচের উপাদানগুলি সরাসরি অ্যাক্সেস করা যায় না।
- ব্রাউজার, কম্পাইলার, ইন্টারপ্রেটার এদেরকে ইমপ্লিমেন্ট করার জন্য স্ট্যাক(Stack) ব্যবহৃত হয়।
- রিকার্সিভভাবে ফাংশন কল করার জন্য স্ট্যাক ব্যবহার করা হয়।
- স্ট্যাকে শুধুমাত্র একটি দিক থেকে ইনসার্ট(Insert) or পূশ(PUSH) এবং ডিলিট(Delete) পপ (POP) অপারেশন করা যায়, যাকে টপ(TOP) বলা হয়। অন্য দিকটি ফিক্সড এবং বটম নামে ডাকা হয়।
- স্ট্যাকের কিছু সাধারণ অ্যাপ্লিকেশন হলো:
- এক্সপ্রেশন ইভ্যালুয়েশন(Expression Evolution) এবং সিনট্যাক্স পার্সিং(Syntax Parsing)
- ব্যাকট্র্যাকিং(Backtracking) যেমন মেজ(Maze) এবং গ্রাফ প্রবলেম(Graph Problem)
- গার্বেজ কালেকশন ছাড়াই পরিবেশের মেমোরি ম্যানেজমেন্ট
সংক্ষেপে, স্ট্যাক LIFO অর্ডার অনুসরণ করে, শুধুমাত্র এক দিকে অপারেশনের সুবিধা দেয় এবং ফাংশন, পার্সার, ব্যাকট্র্যাকিং অ্যালগরিদম ইত্যাদি ইমপ্লিমেন্টের জন্য ব্যবহৃত হয়। এর সহজ গঠনটি পুশ(PUSH)/পপ(POP) অপারেশনকে খুব দ্রুত করে তুলে। এই দুই অপারেশন দুই ভাবে ইমপ্লিমেন্ট করা সম্ভব 1) Array 2) Link List
Stack Simulation
স্ট্যাক(STACK) এর পুশ(PUSH) এবং পপ(POP) অপারেশনটির algorithm:
PUSH/INSERT()
1.if top=MAX then
print "Stack is full";
exit;
2. otherwise
top:=top+1;
stack(top)=item;
3. end of if
4. exit
POP/DELETE()
1. if top=0 then
print "Stack is empty";
exit;
2. otherwise
item=stack(top);
top:=top-1;
3. end of if
4. exit
isFull()
1. if top=MAX then
status=true;
2. otherwise
status=false;
3. end of if
4. exit
isEmpty()
1. if top=0 then
status=true;
2. otherwise
status=false;
3. end of if
4. exit
1. Array : স্ট্যাক(STACK) এর পুশ(PUSH) এবং পপ(POP) অপারেশন এর Source code টি উল্লেখ করা হল –
//Stack Implementation Using Array[Static Memory allocation]
#include<stdio.h>
int stack[100],choice,n,top,x,i;
void push(void);
void pop(void);
void display(void);
int main()
{
top=-1;
printf("\n Enter the size of STACK[MAX=100]:");
scanf("%d",&n);
printf("\n\t STACK OPERATIONS USING ARRAY");
printf("\n\t--------------------------------");
printf("\n\t 1.PUSH\n\t 2.POP\n\t 3.DISPLAY\n\t 4.EXIT");
do
{
printf("\n Enter the Choice:");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
push();
break;
}
case 2:
{
pop();
break;
}
case 3:
{
display();
break;
}
case 4:
{
printf("\n\t EXIT POINT ");
break;
}
default:
{
printf ("\n\t Please Enter a Valid Choice(1/2/3/4)");
}
}
}
while(choice!=4);
return 0;
}
void push()
{
if(top>=n-1)
{
printf("\n\tSTACK is over flow");
}
else
{
printf(" Enter a value to be pushed:");
scanf("%d",&x);
top++;
stack[top]=x;
}
}
void pop()
{
if(top<=-1)
{
printf("\n\t Stack is under flow");
}
else
{
printf("\n\t The popped elements is %d",stack[top]);
top--;
}
}
void display()
{
if(top>=0)
{
printf("\n The elements in STACK \n");
for(i=top; i>=0; i--)
printf("\n%d",stack[i]);
printf("\n Press Next Choice");
}
else
{
printf("\n The STACK is empty");
}
}Link list : স্ট্যাক(STACK) এর পুশ(PUSH) এবং পপ(POP) অপারেশন এর Source code টি উল্লেখ করা হল –
//Stack Implementation Using Link List
#include <stdio.h>
#include <stdlib.h>
struct Node
{
int data;
struct Node *next;
} *top = NULL;
void push(int);
void pop();
void display();
void main()
{
int ch, data;
printf("\n:: Stack using Linked List ::\n");
while (1)
{
printf("\n****** MENU ******\n");
printf("1. Insert\n2. Pop\n3. Display\n4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &ch);
switch (ch)
{
case 1:
printf("Enter the value to be insert: ");
scanf("%d", &data);
push(data);
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf("\nWrong selection!!! Please try again!!!\n");
}
}
}
void push(int value)
{
struct Node *newNode;
newNode = (struct Node *)malloc(sizeof(struct Node));
newNode->data = value;
if (top == NULL)
newNode->next = NULL;
else
newNode->next = top;
top = newNode;
printf("\nInsertion is Success!!!\n");
}
void pop()
{
if (top == NULL)
printf("\nStack is Empty!!!\n");
else
{
struct Node *temp = top;
printf("\nDeleted element: %d", temp->data);
top = temp->next;
free(temp);
}
}
void display()
{
if (top == NULL)
printf("\nStack is Empty!!!\n");
else
{
struct Node *temp = top;
while (temp->next != NULL)
{
printf("%d--->", temp->data);
temp = temp->next;
}
printf("%d--->NULL", temp->data);
}
}
Application Of Stack: Infix, Postfix, Prefix
Infix Expression কী?
Infix Expression এমন একটি গাণিতিক প্রকাশ যেখানে অপারেটরগুলি অপারেন্ডগুলির মধ্যে থাকে।
উদাহারন : A+B
Postfix Expression কী?
Postfix Expression, যাকে রিভার্স পোলিশ নোটেশনও (Reverse Polish Notation) বলা হয়, এমন একটি গাণিতিক প্রকাশ যেখানে অপারেটরগুলি অপারেন্ডগুলির পরে আসে।
উদাহারন : AB+
Prefix Expression কী?
Prefix Expression, যাকে পোলিশ নোটেশনও (Polish Notation) বলা হয়, এমন একটি গাণিতিক প্রকাশ যেখানে অপারেটরগুলি অপারেন্ডগুলির আগে থাকে।
উদাহারন : +AB
Infix, Postfix, এবং Prefix Expression এর জন্য অপারেটরদের অগ্রাধিকার (priority) এবং সঙ্গতি (associativity) বোঝা গুরুত্বপূর্ণ। নীচে Infix জন্য অপারেটরদের অগ্রাধিকার(priority) এবং সঙ্গতি(associativity) তালিকা, এবং এদের প্রয়োগের কিছু উদাহরণ রয়েছে।
অপারেটরদের অগ্রাধিকার ও সঙ্গতি (Operator Precedence and Associativity)
অগ্রাধিকার (Priority)
অপারেটরদের অগ্রাধিকার স্থির করে কোন অপারেটর প্রথমে কার্যকর হবে। নিচে কিছু সাধারণ অপারেটরদের অগ্রাধিকার তালিকা দেওয়া হল (উচ্চ থেকে নিম্ন অগ্রাধিকার অনুযায়ী)।
- Postfix:
(),[],->,.(left-to-right) - Unary:
+,-,!,~,++,--,sizeof(right-to-left) - Multiplicative:
*,/,%(left-to-right) - Additive:
+,-(left-to-right) - Shift:
<<,>>(left-to-right) - Relational:
<,<=,>,>=(left-to-right) - Equality:
==,!=(left-to-right) - Bitwise AND:
&(left-to-right) - Bitwise XOR:
^(left-to-right) - Bitwise OR:
|(left-to-right) - Logical AND:
&&(left-to-right) - Logical OR:
||(left-to-right) - Conditional:
?:(right-to-left) - Assignment:
=,+=,-=,*=,/=,%=,<<=,>>=,&=,^=,|=(right-to-left) - Comma:
,(left-to-right)
সঙ্গতি (Associativity)
অপারেটরদের সঙ্গতি স্থির করে অপারেটরটি কোন দিক থেকে কার্যকর হবে। নিচে অপারেটরদের সঙ্গতি তালিকা দেওয়া হল:
- Left-to-right:
+,-,*,/,%,==,!=,<,<=,>,>=,&&,||,&,|,^,<<,>> - Right-to-left:
=,+=,-=,*=,/=,%=,<<=,>>=,&=,^=,|=,? :,++,--,!,~
উদাহরণ সহ বিশ্লেষণ
আমরা যদি (A + B / C) Infix Expression টি postfix এবং prefix expression এ রূপান্তরিত করি:
ইনফিক্স (Infix): (A + B / C)
এখানে (+) অপারেটরটির অগ্রাধিকার কম, এবং (/) অপারেটরটির অগ্রাধিকার বেশি।
পোস্টফিক্স (Postfix): (A B C / +)
এই Expression এ , প্রথমে (B) এবং (C) অপারেন্ড রয়েছে, তারপর তাদের পরে (\times) অপারেটর রয়েছে। এরপর (A) অপারেন্ড এবং (\times) এর ফলাফলের পরে (+) অপারেটর আছে।
প্রিফিক্স (Prefix): (+ A / B C)
এই Expression এ , প্রথমে (+) অপারেটর রয়েছে, তারপর অপারেন্ড (A) এবং অবশেষে (\times) অপারেটর যা (B) এবং (C) এর ওপর প্রয়োগ করা হয়েছে।
ইনফিক্স(Infix) থেকে পোস্টফিক্স(Postfix) রূপান্তর:
- অপারেন্ডগুলি সরাসরি ফলাফলের তালিকায় যোগ করুন।
- অপারেটরগুলি স্ট্যাকে রাখুন।
- কোন বন্ধনী মেলানোর সময় স্ট্যাক থেকে অপারেটরগুলি বের করে ফলাফলের তালিকায় যোগ করুন।
ইনফিক্স(Infix) থেকে প্রিফিক্স(Postfix) রূপান্তর:
- ইনফিক্স প্রকাশের প্রতিটি উপাদানকে উল্টোভাবে পড়ুন।
- উল্টো প্রকাশের উপর পোস্টফিক্স রূপান্তরের নিয়ম প্রয়োগ করুন।
- পোস্টফিক্স প্রকাশটি উল্টো করুন।
Exercise:
1. ((A-B)*D)$(E+F)/G)
2. A+(B*C+(D/E$F)/G)/H
3. (A-B$D)/E+F-G
Data Structure : Queue
Queue Operation with algorithm
ডাটা স্ট্রাকচারে কিউয়ের(Queue) মূল অপারেশনগুলি নিম্নরূপ:
1. ENQUEUE – কিউয়ের(queue) শেষে একটি উপাদান যোগ করে। এটি রিয়ার পয়েন্টার (REAR pointer) ব্যবহার করে করা হয়।
2. DEQUEUE – কিউয়ের(queue) সামনে থেকে একটি উপাদান সরায়। যে উপাদানটি সরানো হয় তাকে ফ্রন্ট পয়েন্টার(FRONT pointer) দ্বারা পয়েন্ট করা থাকে।
3. isEmpty – কিউ(queue) খালি(empty) কিনা তা পরীক্ষা করে। যদি কিউয়ের সাইজ 0 হয় তাহলে ট্রু(TRUE) রিটার্ন করে।
4. is Full – কিউ পূর্ণ কিনা তা পরীক্ষা করে। যদি কিউয়ের সাইজ ম্যাক্স সাইজের সমান হয় তাহলে ট্রু(TRUE) রিটার্ন করে।
কিউয়ের(queue) কিছু গুরুত্বপূর্ণ বৈশিষ্ট্য:
- FIFO (First In First Out) অর্ডার অনুসরণ করে – যে উপাদানটি প্রথমে যোগ করা হয়েছে সেটি প্রথমেই সরানো হয়।
- ইনকিউ এবং ডিকিউ হল প্রাথমিক অপারেশন।
- ইনকিউ পিছনের(REAR) দিকে এবং ডিকিউ ফ্রন্ট(FRONT) দিকে করা হয়।
- অপেক্ষার তালিকা, বাফার ইত্যাদি তৈরিতে ব্যবহৃত হয়।
- অ্যাপ্লিকেশনগুলির মধ্যে CPU scheduling, Disk scheduling, Directories, Print spoolers ইত্যাদি অন্তর্ভুক্ত।
সংক্ষেপে, কিউ হল একটি লিনিয়ার ডাটা স্ট্রাকচার যেটি এক দিক থেকে যোগ করার এবং অন্য দিক থেকে সিকুয়েন্সিয়াল FIFO ম্যানারে সরানোর সুবিধা দেয়। এই দুই অপারেশন দুই ভাবে ইমপ্লিমেন্ট করা সম্ভব 1) Array 2) Link List
Queue Simulation
Queue এর enqueue এবং dequeue অপারেশনটির algorithm:
// Algorithm:
enqueue/insert element to the queue
procedure enqueue(data)
if queue is full
return overflow
endif
rear ← rear + 1
queue[rear] ← data
return true
end procedure
dequeue/delete element from the queue
procedure dequeue
if queue is empty
return underflow
end if
data = queue[front]
front ← front + 1
return true
end procedureArray: enqueue এবং dequeue অপারেশন এর Source code টি উল্লেখ করা হল –
//Queue Implementation Using Array
#include <stdio.h>
#include <stdlib.h>
#define MAX 50
void enqueue();
void dequeue();
void display();
int queue_array[MAX];
int rear = -1;
int front = -1;
int main()
{
int choice;
while (1)
{
printf("\n1.Enqueue/Insert element to queue \n");
printf("\n2.Dequeue/Delete element from queue \n");
printf("\n3.Display all elements of queue \n");
printf("\n4.Quit \n");
printf("\nEnter your choice : ");
scanf("%d", &choice);
switch (choice)
{
case 1:
enqueue();
break;
case 2:
dequeue();
break;
case 3:
display();
break;
case 4:
exit(1);
default:
printf("Wrong choice \n");
}
}
}
void enqueue()
{
int data;
if (rear == MAX - 1)
printf("Queue Overflow \n");
else
{
if (front == -1)
front = 0;
printf("Inset the element in queue : ");
scanf("%d", &data);
rear = rear + 1;
queue_array[rear] = data;
}
}
void dequeue()
{
if (front == -1 || front > rear)
{
printf("Queue Underflow \n");
return;
}
else
{
printf("Element dequeue from queue is : %d\n", queue_array[front]);
front = front + 1;
}
}
void display()
{
int i;
if (front == -1)
printf("Queue is empty \n");
else
{
printf("Queue is : \n");
for (i = front; i <= rear; i++)
printf("%d ", queue_array[i]);
printf("\n");
}
}Linked list: enqueue এবং dequeue অপারেশন এর Source code টি উল্লেখ করা হল –
//Queue implementation in C using Link List
#include<stdio.h>
#include<stdlib.h>
struct Queue //structure is declared
{
struct Queue *next; //self referensing structure
int item; //initailizing item in the structure
};
struct Queue *front; //a pointer front is declared in structure
struct Queue *rear; //a pointer rear is declared in structure
void addq(int); //addq function is declared
int delq(); //delq function id declared
void main()
{
int ch, item, val; //variables are declared
while(1)
{
printf("\nEnter 1 to add element in the Queue");
printf("\nEnter 2 to delete element from the Queue");
printf("\nEnter 3 to exit from program");
printf("\nEnter your choice::");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("\nEnter the item in the list::");
scanf("%d", &item);
addq(item);
break;
case 2: val=delq() ;
printf("\nThe deleted element is %d=",val);
break ;
case 3: exit(1);
default: printf("\nWrong Input") ;
}
}
}
void addq(int item)
{
struct Queue *temp; //a pointer temp is declared within the structure
temp=(struct Queue*)malloc(sizeof(struct Queue));
if(temp==NULL)
{
printf("\nQueue Overflowed");
return;
}
temp->item=item;//the value is entered in the List
temp->next=NULL;
if(rear==NULL)
{
front=temp;
rear=temp;
}
else
{
rear->next=temp;
rear=rear->next; //rear is incremented
}
}
int delq()
{
struct Queue *temp;
int item=0;
if(front==NULL) //checking unerflowed condition
{
printf("\nQueue Underflowed");
return 0;
}
item=front->item;
temp=front;
if(front==NULL) //checking whether front is null or not, if true
{
front=NULL; //front is assign with NULL
rear=NULL;
}
else
{
front=front->next;
free(temp);
}
return item;
}
Data Structure: Circular Queue
Circular Queue কি এবং এর সুবিধা, অসুবিধা ও প্রয়োগ
Circular Queue:
Circular Queue হল এক ধরনের লিনিয়ার ডেটা স্ট্রাকচার, যা মূলত একটি কিউ-এর মতোই কাজ করে, কিন্তু এটি শেষ থেকে শুরুতে আবার ঘুরে যেতে পারে। এতে প্রথম এবং শেষ এলিমেন্টের মধ্যে একটি লজিক্যাল কানেকশন থাকে।
সুবিধা:
- Memory use: Circular Queue তে মেমরি অপচয় হয় না, কারণ এটি শেষ পজিশন থেকে আবার শুরু পজিশনে যেতে পারে।
- Optimized Performance: নির্দিষ্ট সংখ্যক কাজ সম্পাদন করতে চক্রাকারভাবে ব্যবহার উপযোগী।
- Faster Operations: সাধারণ কিউ এর থেকে ফাস্টার ইনসারশন এবং ডিলিশন অপারেশন করা যায়।
অসুবিধা:
- Implementation Complexity: ইমপ্লিমেন্টেশন সাধারণ কিউ থেকে একটু জটিল।
- Size Limitation: স্থির মাপের হওয়ায় বড় বড় ডেটা হ্যান্ডেল করতে সমস্যা হতে পারে।
প্রয়োগ (Applications):
- CPU Scheduling: প্রসেস শিডিউলিংয়ের ক্ষেত্রে এটি ব্যবহার করা হয়।
- Memory Management: মেমরি ম্যানেজমেন্টে ফ্রি এবং ইউজড মেমরি ব্লকগুলি ট্র্যাক করতে।
- Network Buffers: নেটওয়ার্ক বাফারের ক্ষেত্রে ডেটা প্যাকেটগুলি সঞ্চয় ও পুনঃসঞ্চয় করতে।
😊 😊 😊 😊 😊
Data Structure: Priority Queue
Priority Queue কী এবং এর সুবিধা, অসুবিধা ও প্রয়োগ
Priority Queue:
Priority Queue হল একটি বিশেষ ধরনের ডেটা স্ট্রাকচার যেখানে প্রতিটি এলিমেন্টের সাথে একটি প্রায়োরিটি সংযুক্ত থাকে। এলিমেন্টগুলো তাদের প্রায়োরিটির ভিত্তিতে প্রসেস করা হয়, উচ্চ প্রায়োরিটির এলিমেন্টগুলো কম প্রায়োরিটির এলিমেন্টগুলোর আগে প্রসেস হয়।
সুবিধা:
- Efficient Task Management: উচ্চ প্রায়োরিটির কাজগুলোকে আগে প্রসেস করে, ফলে জরুরী কাজগুলো তাড়াতাড়ি সম্পন্ন হয়।
- Dynamic Prioritization: বিভিন্ন কাজের প্রায়োরিটি পরিবর্তন করা যায়, ফলে ফ্লেক্সিবল এবং কার্যকরী।
- Resource Allocation: সিস্টেম রিসোর্সগুলোকে কার্যকরভাবে ব্যবহারের সুযোগ দেয়।
অসুবিধা:
- Complex Implementation: ইমপ্লিমেন্টেশন জটিল, বিশেষ করে যখন প্রায়োরিটি অনুযায়ী এলিমেন্ট ইনসার্ট ও ডিলিট করতে হয়।
- Overhead: প্রায়োরিটি মেইনটেন করতে গিয়ে অতিরিক্ত প্রসেসিং টাইম এবং মেমরি ব্যবহৃত হয়।
- Fixed Priorities: স্থির প্রায়োরিটি থাকলে কার্যকরভাবে কাজ পরিচালনা করা কঠিন হতে পারে।
প্রয়োগ (Applications):
- CPU Scheduling: প্রসেস শিডিউলিংয়ে উচ্চ প্রায়োরিটির কাজগুলো আগে সম্পন্ন করার জন্য।
- Network Traffic Management: নেটওয়ার্ক ট্রাফিকের প্রায়োরিটি অনুযায়ী প্যাকেট রাউটিং।
- Operating Systems: বিভিন্ন সিস্টেম প্রসেসের প্রায়োরিটি অনুযায়ী রিসোর্স আলোকেশন।
😊 😊 😊 😊 😊 😊 😊 😊
Data Structure: link list
Single link list Operation with algorithm
Single link list একটি লিনিয়ার ডেটা স্ট্রাকচার যেখানে প্রতিটি উপাদান, যাকে নোড বলা হয়, দুটি অংশ নিয়ে গঠিত:
- ডেটা: আসল তথ্য সংরক্ষণ করে।
- নেক্সট পয়েন্টার: পরবর্তী নোডের ঠিকানা বা রেফারেন্স সংরক্ষণ করে।
প্রথম নোডকে হেড (head) বলা হয় এবং শেষ নোডটি NULL নির্দেশ করে, যা লিস্টের শেষ বুঝায়।
Application of Single Linklist
- ডাইনামিক মেমোরি বরাদ্দ: যখন উপাদানের সংখ্যা আগে থেকে জানা থাকে না।
- আনডু ফাংশনালিটি: টেক্সট এডিটরে পরিবর্তন ট্র্যাক করার জন্য।
- হ্যাশ টেবিল: চেইনিং ব্যবহার করে কোলিশন হ্যান্ডল করতে।
- স্ট্যাক এবং কিউ-এর বাস্তবায়ন: বিশেষত যখন সাইজ ডাইনামিক হয়।
- পলিনোমিয়াল উপস্থাপন: পলিনোমিয়াল যোগ এবং গুণ করার জন্য।
- গ্রাফ অ্যালগরিদমে অ্যাডজেসেন্সি লিস্ট উপস্থাপন।
সুবিধা(Advantage):
- ডাইনামিক সাইজ: প্রোগ্রাম চলাকালীন প্রয়োজন অনুযায়ী বাড়ানো বা ছোট করা যায়।
- দক্ষ ইনসারশন/ডিলিশন:
- উপাদান যোগ বা মুছে ফেলা অ্যারেগুলোর তুলনায় সহজ (এলিমেন্ট সরানোর দরকার নেই)।
- মেমোরি ব্যবহারে কার্যকরী: অ্যারের মতো ধারাবাহিক মেমোরি প্রয়োজন হয় না।
- এবস্ট্রাক্ট ডেটা টাইপ (ADT) বাস্তবায়নে সহজ: যেমন স্ট্যাক, কিউ এবং গ্রাফ।
অসুবিধা(Disadvantage):
- সিকোয়েন্সিয়াল অ্যাকসেস: যেকোনো উপাদান অ্যাকসেস করতে পুরো লিস্ট ট্রাভার্স করতে হয় (র্যান্ডম অ্যাকসেস নেই যেমন অ্যারেতে)।
- অতিরিক্ত মেমোরি প্রয়োজন: পয়েন্টার সংরক্ষণের জন্য অতিরিক্ত মেমোরি লাগে।
- রিভার্স ট্রাভার্সালের জটিলতা: সরাসরি সমর্থিত নয়; অতিরিক্ত প্রচেষ্টা প্রয়োজন।
- অতিরিক্ত ওভারহেড: সার্চিং অপারেশন অ্যারেগুলোর তুলনায় বেশি সময় নেয় (টাইম কমপ্লেক্সিটি O(n))।
Linked List Simulation
Linked list অপারেশন গুলির algorithm:
//Algorithm:
InsertNodeAtBegining()
If (newNode == NULL) then
print ('Unable to allocate memory')
End if
Else then
read item
newNode.item ← item
newNode.next ← head
head ← newNode
End else
InsertNodeAtEnding()
If (newNode == NULL) then
print ('Unable to allocate memory')
End if
Else then
read item
newNode.item ← item
newNode.next ← NULL
temp ← End
While (temp.next != NULL) do
temp ← temp.next
End while
temp.next ← newNode
End else
InsertNodeAtMiddle()
If (newNode == NULL) then
write ('Unable to allocate memory.')
End if
Else then
read item
newNode.item ← item
temp ← head
For i ← 2 to n-1
temp ← temp.next
If (temp == NULL) then
break
End if
End for
If (temp != NULL) then
newNode.next ← temp.next
temp.next ← newNode
End if
End else
deleteFirstNode()
If (head==NULL)
print “List Empty”
end if
else
temp = head
head = head.next
delete temp
End
deleteLastNode()
If (head == NULL) then
print ('List is already empty')
End if
Else then
temp ← head
previousNode ← head
While (temp.next != NULL) do
previousNode ← temp
temp ← temp.next
End while
If (temp == head) then
head ← NULL
End if
Else then
previousNode.next ← NULL
End else
free (temp)
End
deleteMiddleNode()
If (head == NULL) then
print('List empty')
End if
Else then
temp ← head
previousNode ← head
For i←2 to n do
previousNode ← temp
temp ← temp.next
If (temp == NULL) then
break
End if
End for
If (temp != NULL and temp == head) then
head ← head.next
End if
Else
previousNode.next ← temp.next
temp.next ← NULL
free (temp)
End else
Endলিঙ্কড লিস্ট (Linked list) অপারেশন এর source code টি উল্লেখ করা হল –
// Single Link List using C program
#include <stdio.h>
#include <stdlib.h>
/* Structure of a node */
struct node
{
int item;
struct node *next;
} * head;
void createList(int n);
void displayList();
void insertNodeAtBeginning(int item);
void insertNodeAtEnd(int item);
void insertNodeAtMiddle(int item, int position);
void deleteFirstNode();
void deleteLastNode();
void deleteMiddleNode(int position);
int main()
{
int n, item, position;
int choice;
for (;;)
{
printf("\n===========::Single Link List Menu::=================\n\n ");
printf("\n1. Press 1 for Creating Lists\n");
printf("\n2. Press 2 for display Lists\n");
printf("\n3. Press 3 for insert item into fisrt Position of Lists\n");
printf("\n4. Press 4 for insert item into last Position of Lists\n");
printf("\n5. Press 5 for insert item into specified middle Position of Lists\n");
printf("\n6. Press 6 for delete item from fisrt Position of Lists\n");
printf("\n7. Press 7 for delete item from last Position of Lists\n");
printf("\n8. Press 8 for delete item from specified middle Position of Lists\n");
printf("\n===========::Single Link List Menu::=================\n ");
printf("\n\tEnter your choice:");
scanf("%d", &choice);
switch (choice)
{
case 1:
printf("Enter the total number of nodes: ");
scanf("%d", &n);
createList(n);
break;
case 2:
printf("\nitem in the list \n");
displayList();
break;
case 3:
printf("\nEnter item to insert at beginning of the list: ");
scanf("%d", &item);
insertNodeAtBeginning(item);
break;
case 4:
printf("\nEnter item to insert at end of the list: ");
scanf("%d", &item);
insertNodeAtEnd(item);
break;
case 5:
printf("nEnter item to insert at middle of the list: ");
scanf("%d", &item);
printf("Enter the position to insert new node: ");
scanf("%d", &position);
insertNodeAtMiddle(item, position);
break;
case 6:
deleteFirstNode();
break;
case 7:
deleteLastNode();
break;
case 8:
printf("\nEnter the node position you want to delete: ");
scanf("%d", &position);
deleteMiddleNode(position);
break;
case 9:
exit(1);
break;
default:
printf("Wrong selction");
}
}
return 0;
}
void createList(int n)
{
struct node *newNode, *temp;
int item, i;
head = (struct node *)malloc(sizeof(struct node));
if (head == NULL)
{
printf("Unable to allocate memory.");
exit(0);
}
printf("Enter the item of node 1: ");
scanf("%d", &item);
head->item = item;
head->next = NULL;
temp = head;
for (i = 2; i <= n; i++)
{
newNode = (struct node *)malloc(sizeof(struct node));
if (newNode == NULL)
{
printf("Unable to allocate memory.");
break;
}
printf("Enter the item of node %d: ", i);
scanf("%d", &item);
newNode->item = item;
newNode->next = NULL;
temp->next = newNode;
temp = temp->next;
}
}
void displayList()
{
struct node *temp;
if (head == NULL)
{
printf("List is empty.");
}
else
{
temp = head;
while (temp != NULL)
{
printf("item = %d\n", temp->item);
temp = temp->next;
}
}
}
void insertNodeAtBeginning(int item)
{
struct node *newNode;
newNode = (struct node *)malloc(sizeof(struct node));
if (newNode == NULL)
{
printf("Unable to allocate memory.");
}
else
{
newNode->item = item;
newNode->next = head;
head = newNode;
printf("item INSERTED SUCCESSFULLY\n");
}
}
void insertNodeAtEnd(int item)
{
struct node *newNode, *temp;
newNode = (struct node *)malloc(sizeof(struct node));
if (newNode == NULL)
{
printf("Unable to allocate memory.");
}
else
{
newNode->item = item;
newNode->next = NULL;
temp = head;
while (temp != NULL && temp->next != NULL)
temp = temp->next;
temp->next = newNode;
printf("item INSERTED SUCCESSFULLY\n");
}
}
void insertNodeAtMiddle(int item, int position)
{
int i;
struct node *newNode, *temp;
newNode = (struct node *)malloc(sizeof(struct node));
if (newNode == NULL)
{
printf("Unable to allocate memory.");
}
else
{
newNode->item = item;
newNode->next = NULL;
temp = head;
for (i = 2; i <= position - 1; i++)
{
temp = temp->next;
if (temp == NULL)
break;
}
if (temp != NULL)
{
newNode->next = temp->next;
temp->next = newNode;
printf("item INSERTED SUCCESSFULLY\n");
}
else
{
printf("UNABLE TO INSERT item AT THE GIVEN POSITION\n");
}
}
}
void deleteFirstNode()
{
struct node *toDelete;
if (head == NULL)
{
printf("List is already empty.");
}
else
{
toDelete = head;
head = head->next;
printf("\nData deleted = %d\n", toDelete->item);
free(toDelete);
printf("Successfully Delete First Node\n");
}
}
void deleteLastNode()
{
struct node *toDelete, *secondLastNode;
if (head == NULL)
{
printf("List is already empty.");
}
else
{
toDelete = head;
secondLastNode = head;
while (toDelete->next != NULL)
{
secondLastNode = toDelete;
toDelete = toDelete->next;
}
if (toDelete == head)
{
head = NULL;
}
else
{
secondLastNode->next = NULL;
}
free(toDelete);
printf("Successfully Deleted Last Node\n");
}
}
void deleteMiddleNode(int position)
{
int i;
struct node *toDelete, *prevNode;
if (head == NULL)
{
printf("List is already empty.");
}
else
{
toDelete = head;
prevNode = head;
for (i = 2; i <= position; i++)
{
prevNode = toDelete;
toDelete = toDelete->next;
if (toDelete == NULL)
break;
}
if (toDelete != NULL)
{
if (toDelete == head)
head = head->next;
prevNode->next = toDelete->next;
toDelete->next = NULL;
free(toDelete);
printf("Successfully\n");
}
else
{
printf("Invalid position unable to delete.");
}
}
}
Circular Link List:
Circular Link List: A circular linked list is a variation of a linked list where the last node points back to the first node, creating a circle. This means there is no null at the end of the list, and you can traverse the entire list starting from any node. [একটি বৃত্তাকার লিংকড লিস্ট হল একটি লিংকড লিস্টের একটি রূপ যেখানে শেষ নোডটি আবার প্রথম নোডের দিকে ফিরে যায়, একটি বৃত্ত তৈরি করে। এর মানে হল, লিস্টের শেষে কোনো নাল থাকে না, এবং আপনি যেকোনো নোড থেকে শুরু করে পুরো লিস্টটি ঘুরে আসতে পারেন।]
Applications of Circular Linked Lists[Circular Linked Lists এর প্রয়োগ ]:
- Round-robin scheduling in operating systems
- Implementing circular buffers
- Managing multiple applications in a browser (switching between tabs)
- Playlist management in media players
সুবিধা(Advantage):
- Allows for constant-time insertion at both ends of the list [লিস্টের উভয় প্রান্তে কন্সট্যান্ট সময়ে নতুন উপাদান যোগ করা যায়]
- Efficient for applications that require cyclic data structures [সাইক্লিক ডাটা স্ট্রাকচার এর জন্য ইহা উপযুক্ত ]
অসুবিধা(Disadvantage):
Slightly more complex to implement and manage than singly linked lists [ একমুখী লিংকড লিস্টের তুলনায় বাস্তবায়ন ও পরিচালনা করা একটু জটিল ]
Risk of infinite loops if not handled carefully [সাবধানে পরিচালনা না করলে অসীম লুপের ঝুঁকি থাকে]
সার্কুলার লিঙ্ক লিস্টের কিছু গুরুত্বপূর্ণ বৈশিষ্ট্য নিম্নরূপ:
- Create: Initializes an empty circular linked list. [একটি খালি বৃত্তাকার লিংকড লিস্ট শুরু করা।]
- Insert: Adds a new node at a specified position (or at the end if the position is invalid). [নির্দিষ্ট অবস্থানে একটি নতুন নোড যোগ করে (অথবা অবস্থান অবৈধ হলে শেষে যোগ করে)]
- Delete: Removes a node from a specified position (or from the end if the position is invalid). [নির্দিষ্ট অবস্থান থেকে একটি নোড সরিয়ে ফেলে (অথবা অবস্থান অবৈধ হলে শেষ থেকে মুছে ফেলে)।]
- Traverse: Shows the order of elements, demonstrating the circular nature by returning to the first element.[উপাদানগুলির ক্রম দেখায়, প্রথম উপাদানে ফিরে এসে বৃত্তাকার প্রকৃতি প্রদর্শন করে।]
Double Link List
একটি লিনিয়ার ডেটা স্ট্রাকচার যেখানে প্রতিটি উপাদান, যাকে নোড বলা হয়, তিনটি অংশ নিয়ে গঠিত:
- ডেটা: আসল তথ্য সংরক্ষণ করে।
- পূর্ববর্তী পয়েন্টার (Previous pointer): আগের নোডের ঠিকানা নির্দেশ করে।
- পরবর্তী পয়েন্টার (Next pointer): পরবর্তী নোডের ঠিকানা নির্দেশ করে।
সিঙ্গলি লিঙ্কড লিস্টের থেকে ভিন্ন, ডাবলি লিঙ্কড লিস্টে উভয় দিকেই ট্রাভার্স করা যায়। প্রথম নোডকে হেড (head) বলা হয় এবং শেষ নোডের next পয়েন্টার NULL নির্দেশ করে।
Application of Double Link list:
- ন্যাভিগেশন সিস্টেম: পিছনে এবং সামনে ট্রাভার্সাল (যেমন, ওয়েব ব্রাউজার, মাল্টিমিডিয়া প্লেয়ার)।
- আনডু/রিডু ফাংশনালিটি: টেক্সট এডিটর বা ইতিহাস ব্যবস্থাপনার প্রয়োজন এমন অ্যাপ্লিকেশনে সহজে ব্যবহার করা যায়।
- জটিল ডেটা স্ট্রাকচার: উন্নত স্ট্রাকচার যেমন ফিবোনাচি হিপ বা গ্রাফের অ্যাডজেসেন্সি লিস্ট বাস্তবায়নের জন্য।
- ডাইনামিক মেমোরি ম্যানেজমেন্ট: যেখানে প্রায়শই ইনসারশন এবং ডিলিশন অপারেশন প্রয়োজন।
- ডিক (Deque) বাস্তবায়ন: উভয় প্রান্তে কার্যকর অপারেশন সাপোর্ট করে।
সুবিধা(Advantage):
- দ্বিমুখী ট্রাভার্সাল: সামনে ও পিছনে উভয় দিকেই চলা যায়, যা সিঙ্গলি লিঙ্কড লিস্টে সম্ভব নয়।
- সহজ ডিলিশন: নোড মুছে ফেলার জন্য হেড থেকে শুরু করার প্রয়োজন হয় না (কারণ
previousপয়েন্টার রয়েছে)। - দক্ষ ইনসারশন: একটি নোডের আগে বা পরে উপাদান যোগ করা সহজ।
- লিস্ট উল্টানো: সিঙ্গলি লিঙ্কড লিস্টের তুলনায় সহজ এবং দ্রুত।
অসুবিধা(Disadvantage):
- অতিরিক্ত মেমোরি প্রয়োজন: প্রতিটি নোডে
previousপয়েন্টারের জন্য অতিরিক্ত মেমোরি দরকার। - জটিল বাস্তবায়ন:
nextএবংpreviousউভয় পয়েন্টার পরিচালনা করা কঠিন। - ধীর অপারেশন: ইনসারশন এবং ডিলিশনের সময় বেশি পয়েন্টার সামঞ্জস্য করতে হয়।
- অতিরিক্ত ওভারহেড: একাধিক পয়েন্টার পরিচালনার জন্য বাগের সম্ভাবনা বেশি।
Recursion
রিকার্শন একটি পদ্ধতি যেখানে একটি ফাংশন নিজেকে বারবার কল করে একটি নির্দিষ্ট সমস্যার সমাধানে পৌঁছায়। রিকার্শন সাধারণত তখন ব্যবহৃত হয় যখন একটি সমস্যা ছোট ছোট সাব-প্রব্লেমে ভাগ করা যায় এবং এই ছোট প্রব্লেমগুলোর সমাধান মিলিয়ে আসল সমস্যার সমাধান পাওয়া যায়।
রিকার্শনের মধ্যে দুইটি অংশ থাকে:
1. **বেস কেস (Base Case)** – যেখানে রিকার্শন থেমে যায়।
2. **রিকার্শিভ কেস (Recursive Case)** – যেখানে ফাংশন নিজেকে পুনরায় কল করে।
Direct Recursion?
ডিরেক্ট রিকার্শন তখন হয় যখন একটি ফাংশন নিজেই নিজেকে কল করে।
**উদাহরণ:**
```javascript
function countdown(n) {
if (n <= 0) {
console.log("Finished!");
return;
}
console.log(n);
countdown(n - 1); // ফাংশন নিজেকে কল করছে
}
countdown(5);
```এখানে `countdown` ফাংশন নিজেই নিজেকে কল করছে এবং একে একে মান কমিয়ে বেস কেসে পৌঁছাচ্ছে।
Indirect Recursion?
ইনডিরেক্ট রিকার্শন তখন হয় যখন একটি ফাংশন নিজেকে সরাসরি কল না করে অন্য একটি ফাংশনকে কল করে এবং সেই ফাংশনটি আবার প্রথম ফাংশনটিকে কল করে।
**উদাহরণ:**
```javascript
function functionA(n) {
if (n <= 0) return;
console.log("Function A: " + n);
functionB(n - 1); // functionA, functionB কে কল করছে
}
function functionB(n) {
if (n <= 0) return;
console.log("Function B: " + n);
functionA(n - 2); // functionB, functionA কে কল করছে
}
functionA(5);
```এখানে `functionA` `functionB` কে কল করছে এবং `functionB` আবার `functionA` কে কল করছে। এটাই ইনডিরেক্ট রিকার্শন।
Head Recursion
হেড রিকার্শন তখন হয় যখন ফাংশনের মূল কাজটি রিকার্শিভ কলের পরে সম্পন্ন হয়। অর্থাৎ, ফাংশন প্রথমে নিজেকে কল করে এবং তারপরে কাজ সম্পন্ন করে।
**উদাহরণ:**
```javascript
function headRecursion(n) {
if (n <= 0) return;
headRecursion(n - 1); // প্রথমে রিকার্শন কল হচ্ছে
console.log(n); // রিকার্শনের পরে প্রিন্ট হচ্ছে
}
headRecursion(5);
```এখানে `headRecursion` ফাংশন প্রথমে রিকার্শন কল করে এবং পরে `n` প্রিন্ট করে।
Tail Recursion
টেইল রিকার্শন তখন হয় যখন রিকার্শন কলটি ফাংশনের শেষ অংশে থাকে এবং ফাংশনের বাকি কাজটি রিকার্শনের আগে সম্পন্ন হয়।
**উদাহরণ:**
```javascript
function tailRecursion(n) {
if (n <= 0) return;
console.log(n); // রিকার্শনের আগে প্রিন্ট হচ্ছে
tailRecursion(n - 1); // শেষ অংশে রিকার্শন কল হচ্ছে
}
tailRecursion(5);
```এখানে `tailRecursion` ফাংশন প্রথমে `n` প্রিন্ট করে এবং শেষে রিকার্শন কল করে।