Stack (স্ট্যাক) কী?
Stack & Queue হলো একটি Linear Data Structure যেটি LIFO (Last In First Out) নীতিতে কাজ করে। অর্থাৎ যে উপাদানটি সর্বশেষে insert (push) করা হয়েছে, সেটিই সর্বপ্রথম remove (pop) হয়।
তুলনা করা যায় পিঠের উপর পিঠ রাখা প্লেটের স্তূপের (plate stack) সাথে — উপরের প্লেট আগে উঠবে।
Stack-এর প্রধান Operations:
Push Operation
- একটি নতুন element Stack-এর top-এ add করা হয়।
- যদি Stack পূর্ণ থাকে (fixed size হলে), তখন Stack Overflow ঘটে।
উদাহরণ: Stack: [10, 20, 30]Push(40)→ Stack: [10, 20, 30, 40]
Pop Operation
- Stack-এর top element মুছে ফেলা হয় এবং return করা হয়।
- যদি Stack ফাঁকা থাকে, তখন Stack Underflow ঘটে।
উদাহরণ: Stack: [10, 20, 30]Pop()→ Return: 30→ Stack: [10, 20]
Stack-এর গুরুত্বপূর্ণ Applications:
1. Function Call Stack
প্রোগ্রাম execution-এর সময় প্রতিটি function call একটি stack-এ সংরক্ষিত হয়, এবং execution শেষ হলে stack থেকে বের হয়।
2. Undo/Redo Operations
Text editor-এ কাজ করার সময় পূর্ববর্তী অবস্থা ফিরে পেতে বা আবার redo করতে Stack ব্যবহৃত হয়।
3. Expression Evaluation & Conversion
- Infix to Postfix বা Prefix conversion
- Postfix expression evaluation
4. Backtracking Algorithms
যেমন:
- Maze solving
- Recursion
- Sudoku solver
5. Browser History Navigation
Back বাটন চাপলে আগের পৃষ্ঠায় যাওয়ার জন্য Stack ব্যবহার হয়।
চিত্র (সাধারণ Stack Visualization):
Top → [40] ← Last In (Push) [30] [20]Bottom→ [10] ← First In
Pop করলে প্রথমে 40 যাবে, তারপর 30, ইত্যাদি।
Queue (কিউ) কী?
Queue হলো একটি Linear Data Structure যেটি FIFO (First In First Out) নীতিতে কাজ করে।
অর্থাৎ যেই element প্রথমে enqueue (insert) করা হয়েছে, সেটিই প্রথমে dequeue (remove) করা হবে।
তুলনা করা যায় বাসে উঠার লাইনের সাথে — যে আগে লাইনে এসেছে, সে আগে উঠবে।
Queue-এর প্রধান Operations:
Enqueue Operation
- নতুন element rear (পেছনের দিকে) যুক্ত হয়।
- যদি Queue পূর্ণ হয়, তখন Queue Overflow ঘটে।
উদাহরণ: Queue: [10, 20, 30]Enqueue (40)→ Queue: [10, 20, 30, 40]
Dequeue Operation
- প্রথমে থাকা element (front) Queue থেকে মুছে ফেলা হয়।
- যদি Queue ফাঁকা থাকে, তখন Queue Underflow ঘটে।
উদাহরণ: Queue: [10, 20, 30]Dequeue()→ Return: 10→ Queue: [20, 30]
Queue-এর গুরুত্বপূর্ণ Applications:
- Task Scheduling – যেমন CPU scheduling, Printer queue
- Data Buffering – যেমন: IO Buffers, Network data packets
- Call Center Systems – ফোন কলে যারা আগে আসবে, তাদের আগে সেবা দেওয়া হয়
- Breadth-First Search (BFS) – Graph traversal-এ ব্যবহৃত
- Simulation Systems – যেমন: ব্যাংক লাইনের বা ট্রাফিক কন্ট্রোল মডেলিং
Circular Queue (সার্কুলার কিউ) কী?
Circular Queue হলো একটি বিশেষ Queue যেখানে last position আবার first position-এর সাথে যুক্ত থাকে, ফলে এটি একটি বৃত্ত (circle) তৈরি করে। এতে করে space utilization বৃদ্ধি পায়।
Structure:
[10] → [20] → [30] → [40] ↑ ↓ ← ← ← ← ← ← ← ← ← ← ← ← ←
সুবিধা:
- Fixed size queue-এর মধ্যে memory efficiently ব্যবহৃত হয়
- Rear এবং Front pointer ঘুরে ঘুরে কাজ করে
Priority Queue (প্রায়োরিটি কিউ) কী?
Priority Queue হলো একটি বিশেষ ধরনের Queue যেখানে প্রতিটি element-এর একটি priority থাকে।
এখানে element-কে insertion-এর ক্রমে নয়, বরং priority অনুসারে serve করা হয়।
উদাহরণ:
- Patient emergency system: গুরুতর রোগী আগে চিকিৎসা পাবে
- Job scheduling system: high-priority কাজ আগে সম্পন্ন হবে
বৈশিষ্ট্য:
- High priority element আগে serve হবে
- যদি Priority সমান হয়, তবে FIFO নীতি অনুসরণ করা হয়
তুলনামূলক চিত্র:
| Queue Type | Behavior | Key Feature |
| Simple Queue | FIFO | Front থেকে remove, Rear এ insert |
| Circular Queue | FIFO (with wrapping) | Memory reuse করে, overflow কমে |
| Priority Queue | Based on priority (not FIFO) | High priority → earlier execution |
Recursion (রিকারশন) কী?
Recursion হলো একটি প্রোগ্রামিং কৌশল যেখানে একটি ফাংশন নিজেই নিজেকে কল (call) করে সমস্যা সমাধান করে। এটি সাধারণত একটি বড় সমস্যাকে ছোট ছোট উপ-সমস্যায় ভাগ করে base case পর্যন্ত পৌঁছে সমাধান করে।
উদাহরণ: def factorial(n): if n == 1: return 1 else: return n * factorial(n-1)
উপরের উদাহরণে factorial() ফাংশন নিজেই নিজেকে কল করছে যতক্ষণ না base case n == 1 পূরণ হয়।
Advantages of Recursion (রিকারশনের সুবিধাসমূহ):
- Simpler Code
- জটিল সমস্যাগুলো (যেমন Tree traversal, Fibonacci series, Tower of Hanoi) অনেক কম লাইনে ও পরিষ্কারভাবে লেখা যায়।
- Divide and Conquer Approach
- বড় সমস্যা ছোট ছোট অংশে ভাগ করে সহজে সমাধান করা যায়।
- Backtracking সহজ হয়
- যেমন: Maze solving, Sudoku solving, N-Queens problem।
- Tree/Graph traversal সহজ হয়
- যেমন: Inorder, Preorder, Postorder traversal।
Limitations of Recursion (রিকারশনের সীমাবদ্ধতা):
- Performance Overhead
- প্রতিটি recursive call এর জন্য একটি function call stack তৈরি হয়, যা memory এবং time consume করে।
- Stack Overflow
- খুব বেশি recursive depth হলে stack overflow error হতে পারে।
- Debugging কঠিন
- একাধিক recursive call একসাথে চলার কারণে সমস্যা খুঁজে বের করা কঠিন হতে পারে।
- Less Efficient than Iteration (in some cases)
- অনেক সময় recursion-এর চেয়ে loop (iteration) faster এবং memory efficient হয়।
ব্যবহারযোগ্য ক্ষেত্র:
- Mathematical problems: factorial, fibonacci
- Data structures: tree traversal, graph traversal
- Algorithms: quick sort, merge sort
- Backtracking problems: maze, puzzles
Linear Search (লিনিয়ার সার্চ)
Linear Search হলো একটি সহজ searching algorithm যেখানে data structure-এর প্রতিটি element একে একে দেখে চাওয়া মান (target value) আছে কি না তা খোঁজা হয়।
Algorithm:
- প্রথম element থেকে শুরু করে একে একে সব element চেক করা হয়
- যদি match পাওয়া যায়, তাহলে index return করা হয়
- না পেলে “Not Found” return করে
সময় জটিলতা (Time Complexity):
- Best Case: O(1)
- Worst Case: O(n)
Binary Search (বাইনারি সার্চ)
Binary Search একটি উন্নত searching algorithm যা শুধুমাত্র sorted array-তে কাজ করে। এটি data-কে বারবার দুই ভাগে ভাগ করে target খোঁজে।
Algorithm:
- Array মাঝখান থেকে শুরু করে
- যদি মাঝের element == target → return index
- যদি target < mid → search left side
- যদি target > mid → search right side
- যতক্ষণ না element পাওয়া যায় বা search range শেষ হয়
সময় জটিলতা (Time Complexity):
- Best Case: O(1)
- Worst Case: O(log n)
Linear vs Binary Search:
| বৈশিষ্ট্য | Linear Search | Binary Search |
| Array Sorted? | না হলেও চলে | Sorted হতে হবে |
| Time Complexity | O(n) | O(log n) |
| Logic | Sequential check | Divide & conquer |
| বাস্তব ব্যবহার | ছোট বা Unsorted list | বড় ও Sorted list |
Bubble Sort (বাবল সার্ট)
Bubble Sort হলো একটি সহজ sorting algorithm, যেখানে প্রতিটি পাশের দুটি element compare করে তাদের স্থান বদল করা হয় যতক্ষণ না পুরো array sorted হয়।
Algorithm:
- পুরো list বারবার traverse করা হয়
- adjacent দুটি element compare করা হয়
- যদি তারা ভুল order-এ থাকে (g., বড়টা আগে), তবে swap করা হয়
- প্রতিবার সবচেয়ে বড় element “bubble up” করে শেষে চলে যায়
Example (Ascending order):
python arr = [5, 2, 9, 1, 5]n = len(arr) for i in range(n): for j in range(0, n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j]
সময় জটিলতা (Time Complexity):
- Best Case: O(n) → when already sorted (with optimization)
- Worst Case: O(n²)
Bubble Sort এর ব্যবহার:
- ছোট dataset-এর জন্য
- শিক্ষামূলক উদাহরণ হিসেবে
বাস্তব ক্ষেত্রে খুব একটা কার্যকর নয় বৃহৎ ডেটার জন্য