Breadth First Search Algorithm (BFS)

Breadth First Search Algorithm (BFS)

গ্রাফ অ্যালগরিদম  গুলোর মধ্যে  BFS অ্যালগরিদম  অন্যতম ।

দেখে অনেক কঠিন মনে হলেও অ্যালগরিদমটা অনেক সহজ ।

আসুন ধাপে ধাপে নিচের প্রবলেম টা সল্ভ করি ...

চিত্রে  আমরা যে গ্রাফ টা দেখতে পাচ্ছি এখানে টোটাল ৮ টা ভার্টেক্স আছে 

(A,B,C,D,E,F,G,H) 

এখন আমরা A ভার্টেক্স থেকে কাজ শুরু করব কারন alphabetically A সবার আগে  

এখন আমরা দেখব A এর সাথে সংযুক্ত ভার্টেক্স কোনগুলা আছে

এখানে B,D,G হল A এর সাথে যুক্ত । তাই এই ভার্টেক্স গুলা আমি Queue এ Enqueue করব 

এবার আমরা B ভিজিট করব (কারন Queue এ সবার উপরে B আছে )

এবং B Queue থেকে বাদ যাবে । এখন দেখা যাচ্ছে B এর সাথে A,E,F এই ৩টা   ভার্টেক্স  যুক্ত আছে কিন্তু A আমরা ভিজিট করে ফেলেছি , তাই এখন Queue তে শুধু E,F যাবে 

এখন Queue এ সবার উপরে ডি  আছে কিন্তু D এর সাথে যে ভার্টেক্স গুলা যুক্ত আছে A,F আগে ভিজিট করা হয়েছে ,তাই D তে এখন কোন কাজ নাই ,তাই আমরা queue থেকে D বাদ দিলাম ।

একই ঘটনা G,E এর সাথে হবে কারন এদের সাথে যুক্ত আনভিজিটেড

কোন ভার্টেক্স নাই 

এখন আমরা F তে মুভ করব । F এর সাথে যুক্ত একমাত্র আনভিজিটেড ভার্টেক্স হল C , So  F এর পর আমরা C ভিজিট করব  এবং  F ,C কে Queue থেকে বাদ দিবো 

এরপর বাকি থাকে H . H থেকে ভিজিট করার মত আর কিছু নাই সো H ও Queue থেকে বাদ যাবে এবং আমাদের অ্যালগরিদম সম্পন্ন হবে ।

পরিশেষে আমরা যে ফলাফল টা পাচ্ছি তা হলঃ

A B D G E F C H 

কোন সমস্যা হলে কমেন্ট করুন 

ধন্যবাদ 

বাইনারি সার্চ ট্রি (BST)

বাইনারি সার্চ ট্রি (BST)

                                       

                বাইনারি সার্চ ট্রি (BST) 

বাইনারি সার্চ ট্রিঃ বাইনারি সার্চ ট্রি হল সেসব ট্রি, যে ট্রি তে প্রতিটি নোডের ডানপাশের সাবট্রি ঐ নোডের চেয়ে বড় হবে এবং বাম পাশের সাবট্রি ঐ নোডের চেয়ে ছোট হবে। 

বাইনারি সার্চ ট্রি 

Order Of Binary Search Tree (BST): 

Pre-Order: প্রি অর্ডারে প্রথমে নোড তারপর left sub tree তারপর right sub tree (Node->Left->Right: NLR) ! যেমন উপরের ট্রির প্রি অর্ডার হবেঃ 

{7,5,3,1,4,6,12,9,8,10,15,13,17}

In order: in order এ হবে প্রথমে left sub tree তারপর Node তারপর right sub tree (Left->Node->Right: LNR)

Ex- {1,3,4,5,6,7,8,9,10,12,13,15,17}

post Order: এটা হবে LRN - Left->Right->Node

Ex- {1,4,3,6,5,8,10,9,13,17,15,12,7}

বাইনারি ট্রি

বাইনারি ট্রি

                       

     বাইনারি ট্রি 

• বাইনারি ট্রি (Binary Tree): যেসব ট্রি তে সাবট্রি দুটির বেশী থাকেনা তাকে বাইনারি ট্রি বলে। অর্থাৎ, যেকোন নোডের সাবট্রি ০,১,২ যেকোনটি হতে পারে। 

বাইনারি ট্রি 

বাইনারি  ট্রি আবার দু প্রকারঃ 

1. Complete binary Tree: যেসকল বাইনারি ট্রি বাম পাশ থেকে পূর্ণ হয়ে ডানপাশে এসে শেষ হয় তাকে কমপ্লিট বাইনারি ট্রি বলে ।

2. Full Binary Tree: যেসকল বাইনারি ট্রি'র প্রত্যেকটি নোডে দুইটা করে সাব ট্রি থাকে তাকে ফুল বাইনারি ট্রি বলে। দুইটার কম থাকলে তা কখনো Full binary Tree হবেনা। 

• Maximum Number of node On a level: কোন লেবেলে বড়জোর 2^i সংখ্যক নোড থাকতে পারে। যেখানে i হল লেবেল নাম্বার!  
যখন, i=0; জিরো লেবেলে 1 টা নোড ; 
যখন, i=1; 1 নং লেবেল 2 টা নোড থাকতে পারবে। এভাবে যেতে থাকবে। 

• Maximum Number of node on a Tree: কোন ট্রিতে সরবোচ্চ নোড সংখ্যা হবে 2^0 থেকে শুরু করে 2^h পর্যন্ত সংখ্যাগুলোর যোগফল। যেখানে, H হল সরবোচ্চ লেবেল নাম্বার। 
i.e: fig-2 
2^0+2^1+2^2=7 
অর্থাৎ, দ্বিতীয় চিত্রে সরবচ্চ ৭ টি নোড থাকতে পারবে। 

Tree To array: ট্রি থেকে অ্যারেতে রুপান্তর সময় কয়েকটা জিনিস খেয়াল রাখতে হবে। 
১। প্রথবার root->left->right তারপর থেকে left->right ; এভাবে লেবেল বাই লেবেল ট্র্যাভারস করবে । 
২। সবসময় ট্রি এর প্রতিটি নোডকে দুইটা সাবট্রি(child) বিবেচনা করতে হবে। মানে হল প্রত্যেকটি লেবেল কমপ্লিট বিবেচনা করতে হবে(2^i) । যেমন, 0 লেবেলে 2^1  টি 1নং লেবেলে 2^1 টি ,2 নং লেবেলে 2^2 টি এভাবে। যদি কোন লেবেল অসম্পূর্ণ থাকে তাহলে সে যায়গায় খালি রেখে অ্যারে সম্পূর্ণ করতে হবে। চিত্রটি লক্ষ করলে ব্যাপারটা ক্লিয়ার হবে  । 

চিত্রঃ ট্রি থেকে অ্যারে তে রুপান্তর 

প্রথমে রুট থেকে শুরু হয়েছে। তারপর ১ নং লেবেলে বাম থেকে শুরু করে ডানে এসে শেষ হল। তারপর দুই নং লেবেলে, এভাবে অ্যারে শেষ হল । এখন প্রশ্ন হল যদি ট্রি টি full binary tree না হত তাহলে কি হত? মানে যদি উপরের ট্রি তে কোন একটা নোড না থাকতো ? সেক্ষেত্রে ওই নোডের যায়গাটি ফাঁকা রয়ে থেকে যেতো ! চিত্রটি খেয়াল করিঃ 

চিত্রে I নাই। তাই I এর যায়গাটি ফাঁকা আছে। এভাবে ট্রি থেকে অ্যারেতে রুপান্তর করা হয়। একই কৌশল ব্যাবহার করে অ্যারে  থেকে ট্রি তে রুপান্তর করা হয়।  আজ এ পর্যন্তই ! 

ট্রি পরিচিতি

ট্রি পরিচিতি

                               

      ট্রি পরিচিতি

বাংলা শব্দ গাছ এর ইংরেজী প্রতিশব্দ হল Tree. ট্রি  সম্পর্কে নতুন করে কিছু বলার নাই। ট্রি ঠিক নরমাল ট্রি (গাছ) এর মতই তবে গঠন বা পজিশনের দিক দিয়ে ঠিক বাস্তব ট্রি'র উল্টো! যদি মস্ত বড় ভূমিকম্পে  পৃথিবী কখনো উল্টে যায় তাহলে ডাটা স্ট্রাকচারের ট্রি আর নরমাল ট্রি'র পজিশন এক হয়ে যাবে। যাইহোক, ভূতাত্ত্বিক গবেষনা বাদ দিয়ে ডাটা স্ট্রাকচার নিয়ে জানাশুনা করি! ট্রি আসলে কি ?  এ নিয়ে উইকিপিডিয়ার বক্তব্যঃ 
In computer science, a tree is a widely used abstract data type (ADT) or data structure implementing this ADT that simulates a hierarchical tree structure, with a root value and subtrees of children, represented as a set of linked nodes.

চিত্রঃ ট্রি 

এতক্ষনে হয়তো ক্লিয়ার হয়ে গেছে ট্রি কেন বাস্তব ট্রি'র উল্টো! এবার ট্রি বেসিক জিনিসপত্র জেনে নেবো! ট্রি'র প্রত্যেকটি অংশকে একেকটি নোড হিসেবে কল্পনা করবো প্রতিটি তীর চিহ্ন (arrow) কে বলা হয় লিঙ্ক বা edge. 

১। প্যারেন্ট(parent): যে নোড থেকে অন্য নোডের দিকে লিঙ্ক করা থাকে তাকে ওই নোডগুলোর প্যারেন্ট বলে। যেমন , B হল D ও E এর প্যারেন্ট, C হল F এর প্যারেন্ট এবং F হল G ও H এর প্যারেন্ট! 

২। সিবলিংস (siblings): একই প্যারেন্ট যুক্ত নোডগুলোর একে অপরকে সিবলিংস বলে। যেমন, D ও E অথবা G ও H হল একে অপরের সিবলিংস। 

৩। চিলড্রেন (children): যে নোডের সাথে পূর্ববর্তী কোন নোডের লিঙ্ক করা থাকে তাকে ওই নোডের চিলড্রেন বলে। চিত্রেঃ B ও C হল A নোডের চিলড্রেন; D ও E হল B নোডের চিলড্রেন ; F  হল C নোডের চিলড্রেন এবং G ও H হল F নোডের চিলড্রেন! 

৪। রুট নোড (Root node): যে নোডের দিকে অন্য কোন নোডের লিঙ্ক নাই তাকে রুট নোড বলে অথবা যে নোডের কোন parent নাই তাকেই রুট নোড বলে। যেকোন ট্রি'র মাত্র একটি রুট নোড থাকে! সাধারনত প্রথম নোডটাই রুট নোড হয়ে থাকে। চিত্রে A হল রুট নোড।  

৫। লিফ নোড (Leaf node): যে নোড হতে অন্য কোন নোডের দিকে লিঙ্ক করা থাকেনা তাকে লিফ নোড বলে। অন্যভাবে বলতে গেলে যে নোডের কোন বাচ্চাকাচ্চা-চিলড্রেন নাই তাকে লিফ নোড বলে! চিত্রে- D,E,G,H হল লিফ নোড। 

৬। ancestor (অ্যানসেস্টর): অ্যানসেস্টর কথাটার অর্থই হল পূর্বপুরুষ! পূর্বপুরুষ কি জিনিস বলার প্রয়োজন নাই! আরো সহজে বলতে গেলে কোন নোড কোন কোন নোড অতিক্রম করে ওই নোডে এসেছে সেই সেই নোডগুলোই বলা হয় ওই নোডের অ্যানসেস্টর। 
যেমন, H এর অ্যানসেস্টর হল A,C,F 
E এর অ্যানসেস্টর হল- A,B

লক্ষনীয়ঃ প্রত্যেকে আবার নিজেই নিজের নিজের অ্যানসেস্টর! নিজেকে বাদ দিয়ে যে অ্যানসেস্টর হয় তাকে proper ancestor বলে। 
যেমনঃ Ancestor of H: {H,A,C,F}
proper ancestor of H:{ A,C,F}

৭। Descendant( বংশধর): descendant মানে হল বংশধর! কোন এক প্যারেন্ট থেকে বাচ্চা কাচ্চা সহ যে পরিমান নাতি-পুতি বের হইছে সবগুলোকেই descendant বলে :D  
যেমন H হল A,C,F এর descendant 
descendant of C: {F,G,H}

৮।  Degree of Node: কোন নোডের ডিগ্রি হল ওই নোড থেকে আশা মোট সাব- ট্রি'র সংখ্যা! 
যেমন A এর সাব ট্রি B ও C সুতরাং  A এর ডিগ্রি- 2 
এভাবে-
Degree of B: 2
Degree of F: 2
Degree of G: 0

৯। height of a node: কোন নোডে থেকে লিফ নোড পর্যন্ত সর্বাধিক লম্বা পথে ভ্রমন করলে যে পরিমান লিঙ্ক পাওয়া যায় তাকে সে নোডের উচ্চতা বা height বলে। 
Height of A: 3
Height of C: 2
Height of B: 1
Height of G: 0

৯। Level a tree (লেবেল): রুট নোড থেকে শুরু করে লিফ নোড পর্যন্ত লম্বা পথে থাকা মোট লিঙ্ক সংখ্যাকে লেবেল বলে। লেবেল শুন্য থেকে শুরু হয়। 
Level of the tree: 3
Level of A: 0
Level of B,C: 1
Level of D,E,F: 2
Level of G,H: 3

১০। Depth of a node: রুট নোড থেকে ঐ নোড পর্যন্ত যতগুলো লিঙ্ক থাকে সে লিঙ্কের মোট সংখ্যাকে ওই নোডের depth বলে। যেমন,
Depth of A: 0
Depth of B: 1
Depth of F: 2
Depth of H: 3

#লক্ষণীয়ঃ প্রত্যেকটি ট্রি'র n-1 লিঙ্ক থাকে! যেখানে n হল মোট নোড সংখ্যা! 
আজ এ পর্যন্তই ! ধন্যবাদ, সাথে থাকুন । 

introduction to queue

introduction to queue

                                  queue পরিচিতি 
ইংরেজি শব্দ  "queue" শব্দটির অর্থ হল সারি! ইংরেজিতে-   A queue is an example of a linear data structure, or more abstractly a sequential collection. Queues provide services in computer science, transport, and operations research where various entities such as data, objects, persons, or events are stored and held to be processed later. (উইকিপিডিয়া) 

queue অন্যন্য ডাটা স্ট্রাকচারের মতই একটি ডাটা স্ট্রাকচার। আমরা আদের দৈনন্দিন জীবনে এটা প্রায়ই লক্ষ করি। যেমন,  বিদ্যুত বিল দিতে গেলে লাইনে দাঁড়িয়ে দিতে হয় সেটা একটা কিউ; ডিজিটাল ওয়ার্ল্ডে দেখতে গেলে লাইনে দাঁড়িয়ে ঢুকতে হয়; ব্যাংক থেকে টাকা তুলতে গেলে কিম্বা টাকা জমা দিতে গেলে সেখানেও লাইনে দাড়াতে হয় আবার ঢাকা শহরে পুটপাতেও মাঝে মাঝে হাটতে গেলে কিউ তৈরি হয় :P !  মানে আমাদের প্রচলিত জীবন ব্যাবস্থার সর্বক্ষেত্রে রয়েছে কিউ এর ব্যাবহার! 

চিত্রঃ  কিউ 

queue and stack (স্ট্যাক এবং কিউ) :  কিউ এর সাথে স্ট্যাকের যথেষ্ঠ মিল আছে। তবে পার্থক্য শুধু  স্ট্যাকে ইনপুট এবং আউটপুট এক দিক দিয়ে হয় আর কিউ এর ইনপুট একদিকে আউটপুট অন্য প্রান্ত দিয়ে হয়। স্ট্যাক হল FILO কিন্তু কিউ হল FIFO-First In First Out. অর্থাৎ যে আগে আসবে সে আগে pop হবে এরকম! বাস্তব লাইফের কিউ এর দিকে লক্ষ করুন যিনি আগে আসেন তিনি আগেই সেবা নিয়ে চলে যান ! প্রোগ্রামিং এও ঠিক একই রকম ব্যাপারটা। যে প্রান্ত দিয়ে ইনপুট হয় তাকে বলা হয় rear (পেছন) আর যে প্রান্ত দিয়ে বের হয় তাকে বলা হয় front অথবা head.  আশা করি কারো বুজতে অসুবিধা হয়নি।

Uses of queue (কিউ এর  ব্যাবহারঃ কম্পিউটার সায়েন্সের অন্যতম গুরুত্বপূর্ণ ব্যাবহার হল printers queue. যখন একই প্রিন্টারের সাথে এক বা একাধিক পিসি থেকে কমান্ড দেওয়া হয় তখন সবগুলোর প্রিন্ট একসাথে করেনা বা করা সম্ভবও হয়না। তখন কিউ ফলো করা হয়। যার কমান্ড আগে দেওয়া হয় তারটা আগে করা হয় এভাবে পর্যায়ক্রমে সবগুলো প্রিন্ট করা শেষ করে।

মাল্টিপল কানেকশন 

 এ সিস্টেমটা ম্যান্ডেটরি যেখানে একাধিক পিসিতে মাত্র একটি প্রিন্টার ব্যাবহার করা হয়। ভিবিন্ন ধরনের প্রতিষ্ঠানে এটা দরকার হয় যেমন , বিশ্ববিদ্যালয়ের ফ্যাকাল্টি রুম! এছাড়াও প্রসেস সিডিউলিং এবং সিমুলেটিং ওয়েটিং এর কাজেও ব্যাবহার করা হয়। 

queue Operation (কিউ অপারেশন):  কিউ তে নিন্মোক্ত অপারেশন করা হয়-

1. Enqueue: ডাটা প্রবেশ করানোর জন্য এটা ব্যাবহার করা হয়।  এটা স্ট্যাকের push অপারেশনের মত । 

2. Dequeue: ডাটা বের করে আনার জন্য এটা ব্যাবহার করা হয়। এটা স্ট্যাকের pop এর মত। 

3. Display: ডাটা দেখাতে হবে তো ! 

Queue Implementation: কিউ দুইভাবে ইমপ্লিমেন্টেশন করা হয়। একটি হল  অ্যারে দিয়ে আরেকটি হল লিঙ্ক লিস্ট দিয়ে। পরবর্তীতে  দুই টাইপ ই আলোচনা করা হবে। চিত্রটি লক্ষ করুন। 

চিত্রে দেখা যাচ্ছে সবার আগে 37 ইনপুট দেওয়া হল এবং সেটা সবার আগে রিমোভ হয়ে যাচ্ছে। ক্রমান্বয়ে এভাবে ঘটতে থাকবে। টাইপ অনুযায়ী rear/front এর পরিবর্তন হবে। 

 আজ এ পর্যন্তই! পরবর্তীতে দেখবো কিভাবে অ্যারে দিয়ে ইমপ্লিমেন্টেশন করা হয়। কিপ টাচ! 

stack implementation using link list

stack implementation using link list

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

1:  struct Node{  
2:    int data;  
3:    struct Node* next;  
4:  };  
5:  typedef struct Node node;  
6:  node* top;  

1:  int main()  
2:  {  
3:    top=NULL;  
4:    push(10);  
5:    push(20);  
6:    push(30);  
7:    pop();  
8:    pop();  
9:    display();  
10:    return 0;  
11:  }  

1:  void push(int x)  
2:  {  
3:    node* temp;  
4:    temp=(node*)malloc(sizeof(node));  
5:    temp->data=x;  
6:    temp->next=top;  
7:    top=temp;  
8:    }  

1:  void pop()  
2:  {  
3:    node* temp;
4      temp=top;  
6:      printf("Nothing to pop\n");  
7:      return;  
8:
9:    top=top->next;  
10:    free(temp);  
11:    }  

1:  void display()  
2:  {  
3:    node* temp;  
4:    temp=top;  
5:    while(temp!=NULL){  
6:      printf("%d ",temp->data);  
7:      temp=temp->next;  
8:    }  
9:  }  

এইটা লিঙ্ক লিস্টের বিগেনিং ইমপ্লিমেন্টেশন । এর আগে লিঙ্ক লিস্ট ইমপ্লিমেন্টেশন কয়েক ধাপে আলোচনা করা হয়েছিলো।  এখানে শুধু  হেড এর পরিবর্তে top ধরা হয়েছে। Top সম্পর্কে এখানে বর্ণনা করা হয়েছে। তবুও কিছু জিনিস বলে রাখিঃ
push  ফাংশনঃ
10 20 30 push করার পর লিস্টের বর্তমান অবস্থা হবে 30 20 10  কারন এইটা বিগেনিং ইমপ্লিমেন্টেশন। ইমপ্লিমেন্টেশ সম্পর্কে দুটি পুরনাংগ পোস্ট করা হয়েছে ইতোমধ্যে। বিগেনিং ইমপ্লিমেন্টেশন পাওয়া যাবে  এখান থেকে এবং end লিঙ্ক লিস্ট পাওয়া যাবে এখান থেকে।
pop ফাংশনঃ 

pop যেভাবে কাজ করে (এখানে শুধু প্রথম পপ দেখানো হয়েছে )

যেহেতু সবার শেষে পুশ করা হয়েছে 30 , সেহেতু স্ট্যাকের নিয়ম অনুযায়ী 30 সর্বপ্রথম পপ  হবে তারপর 20 সবশেষে 10.
এই মুহূর্তে top=30. আমরা যদি Top থেকে 30 বিচ্ছিন্ন করে ফেলি তাহলেই আমাদের কাজ শেষ। মেইন ফাংশনের ৭ম লাইন থেকে যখন pop করা হল তখন pop ফাংশনে এসে temp=top হলো কারন পরে আমাদের যায়গাটি ফ্রি করার দরকার হবে । তারপর Top কে ঘুরিয়ে পরবর্তী নোডে নিয়ে গেলাম। এখন আর 30 নাই। কিন্তু 30 কিছু মেমরি দখল করে আছে । তা ফ্রি করার জন্য free(temp) ব্যাবহার করা হয়েছে ।
একইভাবে যখন আরেকবার pop করা হল তখন একই ভবে 20 চলে যাবে। এবার যখন display ফাংশন কল করা হল স্বভাবতই প্রিন্ট করবে শুধু 10.
আজ এ পর্যন্তই। ধন্যবাদ 

Stack implementation using array

Stack implementation using array

স্ট্যাকে যে ধরনের অপারেশনগুলো করা হয়! push, pop এবং ডাটাগুলো দেখানোর display ফাংশন। প্রথমে কয়েকটা ছোটখাটো কাজ করে ফেলিঃ

1:  #define MAX_SIZE 5  
2:  top= -1;  
3:  int A[MAX_SIZE];  

উপরের কাজটি ফাংশনের বাইরের কাজ। গ্লোবালি ডিক্লেয়ার করা হয়েছে যাতে সকল ফাংশন তা ব্যাবহার করতে  পারে। লাইন ১ এ- একটি ম্যাক্রো তৈরী করা হয়েছে। যার মান দেওয়া হয়েছে 5. এইটা আসলে আমাদের অ্যারের হাইস্ট সাইজ।  দ্বিতীয় লাইনে ইনিসিয়ালি  top=-1 দেওয়া হয়েছে। টপ সম্পর্কে আগে পর্বে বর্ণনা করা হয়েছে। আগের পর্ব দেখা যাবে এখান থেকে।  Top হল যে বিন্দুতে ইনপুট নেওয়া বন্ধ হয় সেটা। প্রকৃত অর্থে Top আমাদের অ্যারের ইনডেক্স বহন করবে। প্রথমে এর ইনডেক্স -১ ধরলাম তার মানে হল এখনো লিস্ট তৈরী করা হয়নি। এখানে ইন্ডেক্স -১ একটি কাল্পনিক ইনডেক্স কারন অ্যারের ইনডেক্স শুন্য থেকে শুরু হয়।
এবার push ফাংশন লিখে ফেলিঃ

1:  void push(int x)  
2:  {  
3:    if(top==MAX_SIZE-1){  
4:      printf("Stack Over flaw\n");  
5:      return;  
6:    }  
7:     top++;
8:    A[top]=x;  
9:  }  

প্রথম লাইনে ফাংশনটি প্যারামিটার হিসেবে একটি একটি ইন্টেজার নিবে। সেই ইন্টেজারটি আসলে আমরা স্ট্যাকে প্রবেশ করাবো । যেহেতু আমরা অ্যারের হাইস্ট সাইজ 5 নিলাম সেহেতু আমরা ডাটা ৫ টার বেশী রাখতে পারবোনা। যদি ৫ টার বেশী রাখতে চাই over flaw. এই সিস্টেমকে বলা হয় stack over flaw. যাইহোক ডাটা পাঠানোর জন্য মেইন ফাংশন লিখে ফেললাম।

1:  int main()  
2:  {  
3:    push(10);  
4:    push(20);  
5:    push(30);  
6:    push(40); 
7:    push(50);
8:    pop();  
9:    display();  
10:  }  

যখন push(10) কল করলাম তখন  push ফাংশনে প্রবেশ করবে এবং ৩য় লাইনে কন্ডিশন চেক করবে। যেহেতু top এর মান -1 এবং (5-1)=4 সমান নয় সেহেতু ওই কন্ডিশনে ঢুকবেনা। তারপর সপ্তম লাইনে এসে top এর মান 1 বেড়ে 0 হয়ে যাবে এবং A[0] তে 10 অ্যাসাইন করবে।
তারপর আবার যখন push(20) দিলাম তখন top এর মান শুন্য যেহেতু কন্ডিশন মিথ্যা সেহেতু কন্ডিশনে ঢুকবেনা এবং top এর মান 1 বেড়ে যাবে এবং A[1] এ 20 অ্যাসাইন করবে। এভাবে push(30) পাঠাবো তখন যেহেতু top এর মান 1 সেহেতু A[2]=30 যখন push(40) দিলাম তখন top এর মান 2 সেহেতু A[3]=40 হবে আবার যখন push(50) দিলাম তখন top এর মান 3 এরপর A[4]=50 হবে।
এখন যদি আরেকবার push ফাংশন করি তখন 4=4 কন্ডিশন সত্য হয়ে যাবে এবং প্রিন্ট করবে stack over flaw দেখাবে। সুডো কোড দেখলে ব্যাপারটা আরো ক্লিয়ার হবে।

push(10)
top=-1   //-1!=4
top=0
A[0]=10

push(20)
top=0 //0!=4
top=1

A[1]=20
push(30)
top=1 // 1!=4
top=2
A[2]=30

push(40)
top=2 2!=4
top=3
A[3]=40

push(50)
top=3 3!=4
top=4
A[4]=50

push(60)
top=4 // 4==4
stack over flaw

এবার pop ফাংশন লিখে ফেলিঃ

1:  void pop()  
2:  {  
3:    if(top==-1){  
4:      printf("stack is empty\n");  
5:      return;  
6:    }  
7:    top--;  
8:  }  

পপিং এর লজিক হল যেকোনভাবে আমরা ইনডেক্স উড়িয়ে দেব। ইনডেক্স উড়িয়ে দিতে পারলেই আমাদের পপিং শেষ। আমরা আগেই জানি যে যখন top এর মান -1 হয় তখন stack empty থাকে । এবং তখন pop করার মত কিছুইনাই। কন্ডিশনে সেইটা দেওয়া আছে।
আচ্ছা বলুনতো এখন top এর মান কত? নিশ্চয় 4 তাইনা ?
-হুম।
এখন মেইন ফাংশ থেকে pop() ফাংশনকে কল করার পর কন্ডিশনে মিথ্যা হয়ে top এর মান এক কমে গেল। ব্যাস, A[4] এখন হাওয়া :D এভাবে যতবার পপ করব ততবার এক এক করে কমতে থাকবে কোন এক সময় top=-1 হয়ে যাবে তখন আর স্ট্যাকে কিছুই থাকবেনা এবং কন্ডিশন সত্য হয়ে যাবে এবং প্রিন্ট দিবে stack is empty !
এইবার display() ফাংশনের কাজঃ

1:  void display()  
2:  {  
3:    int i;  
4:    for(i=0;i<=top;i++){  
5:      printf("%d ",A[i]);  
6:    }  
7:  }  

এখানে আর কিছুই বলার নাই । শুন্য থেকে করে টপের হাইস্ট ভেলু পর্যন্ত প্রিন্ট দিবে। একবার pop করার পর top= 3
তাহলে আ[0] থেকে শুরু করে A[3] পর্যন্ত মানগুলো প্রিন্ট দিবে। যখন মেইন ফাংশনের ৯ম লাইন থেকে display() কল করা হল  স্বভাবতই প্রিন্ট করবেঃ
10 20 30 40
পূর্ণাংগ প্রোগ্রামটি কম্মেন্ট সহ পাওয়া যাবে এখানে! আজ এ পর্যন্তই! থেঙ্কু ! 

Introduction to stack

Introduction to stack

স্ট্যাকের নাম শুনলেই একটা কমন প্রশ্ন মাথায় ভেসে উঠে স্ট্যাক আসলে কি? এইটা দিয়ে কি করে ? খায় নাকি মাথায় দেয় :p শুধু স্ট্যাক কেন; যেকোন কিছু  শুনলেই প্রত্যেক মানুষের মনে স্বভাবতই একটা প্রশ্ন তৈরী হয় আসলে জিনিসটা কি, কেন জানতে হবে,কি কাজে ব্যাবহার করা হয়! ইত্যাদি ইত্যাদি! সেসব নিয়েই আলোচনা হবে আজ । 
ইংরেজি stack শব্দের অর্থ স্তুপ!  উইকিপিডিয়া অনুযায়ী  স্ট্যাকের সংজ্ঞাঃ
In computer science, a stack or LIFO (last in, first out) is an abstract data type that serves as a collection of elements, with two principal operations: push adds an element to the collection; pop removes the last element that was added.

আমরা জানি মেমরি চারটি সেকশনে ভাগ করাঃ 
১। code(text) সেকশনঃ  যে অংশে ব্যাবহারকারীর লেখা কোড সংরক্ষন করা হয়। 
২। static(global variable) সেকশনঃ  এ অংশে সকল গ্লোবাল ভেরিয়েবল সংরক্ষন করা থাকে। 
৩। stack সেকশনঃ  এখানে সকল ফাংশন এবং সে ফাংশনের ভেতর থাকা সকল ভেরিয়েবল। 
৪। heap সেকশনঃ  এবং সবশেষে heap সেকশন।

মেমরির ভিবিন্ন অংশ 

প্রত্যেকটি সেকশনের কাজের ধরণ ভিন্ন। স্ট্যাক নিয়ে আলোচনার পূর্বে একটা জিনিস ক্লিয়ার করা দরকার। ধরুন আপনার বাসায় সাতটি চেয়ার আছে। প্রথম চেয়ারটি রাখলেন, তারপউপর দ্বিতীয় চেয়ারটি,তারপর তৃতীয় চেয়ারটি এবং তারপর  চতুর্থ চেয়ার,এরপর যথাক্রমে পঞ্চম , ষষ্ঠ এবং সপ্তম! অতঃপর চেয়ারের একটি স্তুপ তৈরী হল। এখন আপনাকে যদি চেয়ারগুলো স্তুপ থেকে আলাদা করতে বলা হয়  তাহলে আপনি কি করবেন? আপনাকে নিশ্চয়ই প্রথমে সাত নাম্বার চেয়ারটা তুলতে হবে তারপর ছয় নাম্বার তারপর পাঁচ নাম্বার  নাম্বার এভাবে সবশেষে এক নাম্বারটা তুলতে হবে। লক্ষ্য করবেন আপনি ১ নাম্বার চেয়ারটি  প্রথমে দিয়েছিলেন তা তুলতে হল শেষে এবং ৭ নাম্বার চেয়ারটি শেষে দিলেন তা তুলতে হলো প্রথমে। এখানে চেয়ারের স্তুপ এক ধরনের স্ট্যাক। 

চেয়ারের স্ট্যাক 

আবার আপনাকে যদি বলা হয়; হে, আমি তোমাকে একটি বক্স দিলাম যার মধ্যে তোমাকে বই রাখতে হবে। আপনি এক এক করে বই রাখলেন এবং যখন আপনাকে তুলতে বলা হয় আপনাকে এক এক করেই তুলতে হবে। খেয়াল করুন এখানেও যা শেষে রেখেছিলেন তা প্রথমে তুলতে হচ্ছে এবং যা শেষে দিয়েছিলেন তা প্রথম রাখলেন তা শেষে তুলতে হচ্ছে। এখানে বইয়ের স্তুপ এক ধরনের স্ট্যাক। 

প্রশ্ন হতে পারে এরকম হওয়ার কারন কি ! এরকম হওয়ার কারন হল, আমরা ইনপুট এবং আউটপুটের জন্য শুধু একটা পথ পাচ্ছি!

#লক্ষনীয়ঃ 
○ এই প্রকৃয়াকে বলা হয় LIFO or last in first out 
○ ইনপুট দেওয়াকে বলা হয় push 
○ বের করে আনাকে বলা হয় pop 
○ যে বিন্দুতে গিয়ে ইনপুট নেওয়া বন্ধ হয় তাকে বলা হয় top 

#স্ট্যাক ডাটা স্ট্রাকচারের প্রয়োগঃ  
1. parsing 
2. Recursive function 
3. Calling function 
4. Expression Evaluation
○ infix to Postfix 
○ Infix to prefix 
○ postfix to infix 
○ prefix to infix
5. Page visited history in a web browser(back button) 
6. Matching tag HTML and xml 
7. Undo sequence in a text editor 


#Implementation of stack: স্ট্যাকের দুই ধরনের implementation আছে। এক. অ্যারে বেসড ইমপ্লিমেন্টেশন
দুই. লিঙ্ক লিস্ট ইমপ্লিমেন্টেশন! পরবর্তীতে আমরা অ্যারে বেসড ইমপ্লিমেন্টেশন সম্পর্কে জানবো! আজ এ পর্যন্তই! ধন্যবাদ :)