Dev Skill: Game of MODs

Problem link: Game of MODs

In this problem, we are given an integer n with q queries. Each query we have k integer. We need to calculate the maximum and minimum number can be formed after removing k digits from n. Here the digits won't change their position.

Solution: Some things to observer first.

• If k == size of n (digits), then the answer would be 0 0
• If there are leading zeros, we need to remove them, say we got a number like 000000009. this should be changed to 9.
• If we have only 0 digit, then the answer would be zero

We will use recursion technique for building up our desired result. The idea is that a character among first (k+1) characters must be present in the resultant number. So we pick the first (k+1) smallest or largest depending on the situation. Put it on the result, then recur for remaining characters.
This is done in the legend function below. I used a counter variable for checking whether we are creating maximum or minimum number. Look at line 18 for understanding. Only the change in the index can produce two defferent result. Complexity is O(n), the number of digits. Considering all the cases, queries, complexity would be 100*200*11 = 220000

সেট (Set)

সেট (Set)

সেট বলতে আমরা ইউনিক জিনিস বুঝে থাকি। যেমন আমার কাছে অনেকগুলি চকলেট আছে, ২ টি মার্স, ১০ টি স্নিকার্স, ৭ টি কিটক্যাট, ১৮ টি সাফারী। এখন আমি যদি আমার চকলেট এর সেট করতে চাই, তাহলে
s = { Mars, Snikers, Kitkat, Safari };

এখানে কিন্তু কোন চকলেট কতবার আছে তা জানার কোন দরকার নেই। আমার খালি দরকার আমার কাছে ইউনিক কি আছে। সেট এই কাজটা করে। STL এর সেট ভ্যালুগুলিকে ইউনিক আকার এবং একই সাথে সর্টেড আকারেও রাখে।

#include <set>
using namespace std;
int main()
{
        set < int > s;
        s.insert ( 10 );
        s.insert ( 10 );
        s.insert ( 1 );
        s.insert ( 10 );
        s.insert ( 10 );
        s.insert ( 2 );
        s.insert ( 2 );

        // এখানে সেট এ আমরা পাবোঃ 1, 2, 10

        set < int > :: iterator it;                   //সেট এর ভ্যালু পয়েন্ট করার জন্য ইটারেটর ডিক্লার
        for ( it = s.begin(); it != s.end(); it++ )
               cout << *it << endl;                //সেট এর ভ্যালুগুলি প্রিন্ট করলাম

        cout << s.size() << endl;                //সেট এর সাইজ প্রিন্ট করলাম
       
        s.clear();                                         //সেট ক্লিয়ার করে দিলাম
}

ধরি আমাকে অনেকগুলি নম্বর দেয়া হল। আমাকে বলতে হবে এর মধ্যে ইউনিক কতটি নম্বর আছে। এর জন্য আমরা খালি সেট এর মধ্যে ইনসার্ট করতে থাকবো এবং সেট এর সাইজটি প্রিন্ট করে দিবো।

আপার_বাউন্ড এবং লোয়ার_বাউন্ড ( upper_bound & lower_bound )

আপার_বাউন্ড এবং লোয়ার_বাউন্ড(upper_bound & lower_bound)

আপার_বাউন্ড এবং লোয়ার_বাউন্ড খুব গুরুত্বপুর্ণ  একটি টপিক। এখন একটি কাহিনী দেখা যাকঃ
আসিফ এবং আসফি ২ যমজ ভাই। তাদের বয়স ধরি ২১। অর্থাৎ তাদের বিয়ের বয়স হয়েছে। তারা আবার খুব হ্যান্ডসাম এবং একই সাথে ব্রিলিয়ান্ট এবং তাদের আগে কোন ফুল-গার্লফ্রেন্ড, হাফ-গার্লফ্রেন্ড কিছুই ছিলনা। কাজেই তাদের বিয়ে করার কথা শুনে মেয়েরা পাগলপ্রায়। এখন আসিফ এর পছন্দ তার থেকে কম বা তার সমান বয়স্ক মেয়েদের (বউ হিসেবে)। অন্যদিকে আসফি এর পছন্দ তার থেকে বেশি বয়স্ক মেয়েদের। এখন ধরি প্রায় ১০০ জন মেয়ে তাদেরকে বিয়ে করার জন্য আগ্রহী। আমাদের কাজ হবে আসিফ এবং আসফি এর জন্য সঠিক বয়সের পাত্রী খুঁজে বের করা। কিভাবে করবো কাজটা? প্রথমেই আমরা পাত্রীদের কে তাদের বয়সের ক্রমানুসারে কম থেকে বেশি আকারে সাজাই। এই সংখ্যাগুলি ধরে একটি ভেক্টর এর মধ্যে রাখি। ধরি আমাদের ভেক্টরটি দেখতে এরকমঃ

int v [ ] = { 10, 12, 14, 21, 21, 21, 21, 30, 32 };

এখন আমরা এই v ভেক্টর এর উপর লোয়ার_বাউন্ড চালালে পাবো ২১, যা ৩ তম ইনডেক্স। আর আপার_বাউন্ড চালালে পাবো ৩০, যা ২১ থেকে ঠিক বড়।



Output :

lower_bound at position 3
upper_bound at position 6

ভেক্টর এর ইনিশিয়াল এবং এনডিং অ্যাড্রেস এবং কোন ভ্যালুর সাপেক্ষে আমরা বাউন্ড বের করতে চাই এগুলি প্যারামিটার হিসেবে দিতে হবে।

ইটারেটর(Iterator)

ইটারেটর(Iterator)

ইটারেটর আসলে সি এর পয়েন্টার এর মত কাজ করে। পয়েন্টার একটি অ্যাড্রেসকে পয়েন্ট করে থাকে যা থেকে আমরা পরবর্তীতে সেই অ্যাড্রেস এর ডাটা নিয়ে কাজ করতে পারি। সি++ এর ইটারেটর এর কাজ ও ঠিক ওরকম। STL ফাংশনগুলি অনেক ক্ষেত্রে অ্যাড্রেস পাঠায় আমরা যে ডাটাকে খুঁজছি, তা কোথায় আছে তার। ইটারেটর ডিক্লার করে এভাবে-->

vector< int > :: iterator it ;
আমরা ভেক্টর এর একটি ইটারেটর it ডিক্লার করলাম।
এখন ভেক্টর এর সব এলেমেন্ট দেখতে চাইলে আমরা এটা করবো-->

for ( it = v.begin(); it != v.end(); it++ )   // v নামের একটি ইন্টিজার এর ভেক্টর নিলাম।
       cout << *it << endl;                        // *it দিয়ে আমরা it অ্যাড্রেস যাকে পয়েন্ট করে আছে, তার ভ্যালু প্রিন্ট করলাম।

প্রায়োরিটি কিউ (Priority Queue)

প্রায়োরিটি কিউ (Priority Queue)

ঠিক কিউ এর মতই, তবে এর একটি সুন্দর দিক হচ্ছে এটি প্রোগ্রামারের প্রায়োরিটি অনুযায়ী কাজ করে।
ধরি কোন একটি জিনিস নিলামের জন্য ডাকা হল। এখন ক্রেতা অনেক। একেকজন একেক দাম হাঁকছে। ধরলাম ক্রেতা আবির, কালাম, হাসান, মমতাজ যথাক্রমে ১০, ৩০, ১২, ১৪ টাকা দাম ডাকলো। এখন আবির আগে ১০ টাকা ডাকলেও, কালাম কিন্তু ৩০ টাকা ডাকার কারনে তার প্রায়োরিটি বেশি হবে বিক্রেতার কাছে। তাই বিক্রেতা চাবে কালামকে জিনিসটি দিতে। এরপরে কালাম চলে গেলে বেশি প্রায়োরিটি পাবে মমতাজ। প্রায়োরিটি কিউ ঠিক এরকম বিক্রেতার মত আচরন করে। default প্রায়োরিটি কিউ বড় থেকে ছোট ভ্যালু প্রসেস করে। কাজেই এক্ষেত্রে ৩০, ১৪, ১২, ১০ এভাবে ভ্যালুগুলি সাজানো থাকবে কিউতে।
প্রায়োরিটি কিউ এর হেডার ফাইলঃ #include <priority_queue>

এখন আমরা যদি ছোট থেকে বড় প্রায়োরিটি অনুসারে সাজাতে চাই? তাহলে ব্যাপারটা কি হবে? একটি হিনটস দেইঃ আমরা ইনসার্ট এর সময় ভ্যালুগুলিকে মাইনাস ১ ( -1 ) দিয়ে গুন করে ইনসার্ট করতে পারি। এছাড়াও সর্টিং, কম্পেয়ারিং এর আরো কিছু মেথড আছে, সেগুলা আমরা পরে অন্য কোন জায়গায় আলোচনা করবো।

ম্যাপ ( Map )

ম্যাপ ( Map )

ম্যাপ খুব দরকারি একটি ডাটা স্ট্রাকচার। আমরা অ্যাারে এর কনসেপ্ট থেকে ম্যাপ কে বুঝার চেষ্টা করবো। আমরা অ্যাারে এর ব্যাপার গুলি থেকে যা জানি, অ্যাারে তে 0 থেকে n সংখ্যক কিছু ইনডেক্স থাকে, সেসব ইনডেক্স এ আমরা আমাদের ডাটা টাইপ অনুযায়ী ডাটা রাখি। অতঃপর আমরা অ্যাারে এর ইনডেক্স কে কল করলে, সে ইনডেক্স এ রাখা ডাটা কে খুব সহজে পেয়ে যাই। এটা মোটামুটি অ্যাারে এর ব্যাসিক আইডিয়া। এখন আমরা অ্যাারে এর ইনডেক্স এর জন্য কেবল মাত্র ইন্টিজার নম্বর ব্যবহার করি, অর্থাৎ কোন একটি ইন্টিজার নম্বর এর সাপেক্ষে আমরা ঐ ইনডেক্স এর ভ্যালু পাবো। এক্ষেত্রে এই ইন্টিজার নম্বরগুলি হচ্ছে key or index, আর এরমধ্যে রাখা জিনিসগুলি হচ্ছে value or data.
এখন একটি গল্প দেখা যাক-->

ধরি কোন এক রাজ্যে কোন এক রাজা আছে। রাজার প্রায় ১০০+ বউ আছে, এবং ৩০০+ বাচ্চাকাচ্চাও আছে !! আচ্ছা ব্যাপারটা একটু কেমন দাঁড়ায়। আসলে ইনি রাজা নন, এনাকে আমরা মহারাজা বলবো এখন থেকে :D । তো, মহারাজার নাম হচ্ছে সেন্টিনো। সেন্টিনোর মন্ত্রীর নাম লুসিফার। প্রতি মাসের প্রাইম নম্বর এর দিনগুলিতে মহারাজা সেন্টিনো, লুসিফার এর কাছে তার বউ বাচ্চার খবর জানতে চায়। আসলে খবর বলতে সেন্টিনো খালি জানতে চায় অমুক নামের মানুষটি কি তার বউ? নাকি বাচ্চা? ( অনেক বাচ্চাকাচ্চা, বউ, পাইক - পেয়াদা, সৈন্য সবার নাম, পদবী তার মনে থাকেনা, এজন্য মন্ত্রী মশাইয়ের কাছে উনি একেটটি নাম দিয়ে তার পজিশন জিজ্ঞাসা করেন  :P )। এখন সেন্টিনো খুব বদমেজাজী রাজা। পান থেকে চুন খসলেই গর্দান ফালায়ে দিবে এরকম টাইপ। লুসিফার এর ভয় ,যদি সে উলটাপালটা কোন ইনফরমেশন দেয়, তাহলে তার জীবন ঐদিন ই শেষ :( । তো লুসিফার অন্য এক সাম্রাজ্য থেকে তোমাকে ডেকে নিয়ে আসলো এবং মহারাজার এই ব্যাপারটায় সাহা্য্য করতে বললো। সাহায্য না করলে তোমার গর্দান যাবে বলে হুমকিও দিল। মজার কথা হচ্ছে, তুমি যদি ম্যাপ জানো, তাহলে তোমার জন্য এটা পুরা পান্তা ভাত, আর না জানলে তো গর্দান যাবে বুঝতেই পারছো।

এখন মহারাজা একটি একটি করে নাম বলে, এবং তোমাকে বলতে হবে ঐ নামধারী ব্যাক্তি আসলে মহারাজার কি হয়? বউ? বাচ্চা? নাকি অন্য কিছু। যেমন সেন্টিনো জানতে চাইলো, মর্জিনা আমার কি হয়? উত্তর ঃ বউ। এখন তুমি যদি উত্তর দেও যে মর্জিনা আপনার বাচ্চা হয়, এবং মর্জিনা কে ডেকে আনার পর যখন মহারাজা বুঝবে যে তুমি মিথ্যা বলেছো, তুমি ওইখানেই শেষ। ( ধরি হিসাবের সুবিধার্থে, কোন বাচ্চা, বউ, সৈন্য কারো নামের ডুপ্লিকেট কেউ থাকবে না )।

এখন আসি সমাধানে -->
এখন ম্যাপ জানা থাকলে তুমি একটি নাম কে, আরেকটি নাম দিয়ে রিপ্রেসেন্ট করবে। যেমন এখানে মর্জিনা হচ্ছে key, আর বউ হচ্ছে তার value. এখন মর্জিনা, বউ এগুলা তো স্ট্রিং টাইপ, কাজেই আমরা ম্যাপ এভাবে ডিক্লার করতে পারিঃ
#include <map>
map < string, string > m;
এখানে ম্যাপ আসলে এভাবে থাকে ঃ map < key, value >

তাহলে আমরা m নামের একটি ম্যাপ ডিক্লার করলাম।
এখন আমরা এই ম্যাপ এ ভ্যালু ইনসার্ট করবো।

m [ "Morjina" ] = "Bou";              // এরমানে হচ্ছে, "Morjina" নামের একটি ইনডেক্স এ "Bou" কে ইনসার্ট করলাম।
cout << m [ "Morjina" ] << endl; // এখানে আউটপুট আসবে ঃ "Bou"
আশা করি ব্যাপারটা বুঝে গেছো সবাই। এভাবে আমরা ম্যাপিং এর মাধ্যমে যেকোন ডাটা টাইপ কে যে কোন টাইপ দিয়ে রিপ্রেসেন্ট করতে পারি।

m [ "Sokhina" ] = "Bachcha";
m [ "Anika" ] = "Bou";
m [ "Solayman" ] = "Soldier";
m [ "Lucifer" ] = "Minister";
m [ "Keka Ferdousi" ] = "Radhuni";

এরকম ইনসার্ট করার পরে আমরা মহারাজা সেন্টিনোর কথা অনুযায়ী ম্যাপ থেকে খুব সহজেই ডাটা রিট্রিভ করতে পারবো।
যদি ম্যাপ এর সবকিছু আমরা আগের অবস্থায় আনতে চাই, তাহলে map.clear() লিখলে ম্যাপ একদম empty হয়ে যাবে।

ম্যাপ নিয়ে আপাতত এটুকুই। আরো ডিটেইলস জানতে চাইলে তোমরা গুগল করে শিখে নিলে সেটা ভালো হয়।
মহারাজার আজগুবি কাহিনী পড়ার জন্য ধন্যবাদ :P 

কিউ ( Queue )

কিউ(Queue)

কিউ পুরোপুরি স্ট্যাক এর উলটা। এর কাজ করার সিস্টেম হল ঃ First In First Out ( FIFO ).

আমরা কিউ এর উদাহরন এভাবে দিতে পারি, ধরি আমরা বসুন্ধরায় "ভালোবাসা দিবি কিনা বল" মুভি দেখতে গেলাম। আমরা n সংখ্যক বন্ধু বান্ধব মিলে লাইন এ দাড়ালাম টিকেট কিনার জন্য। এই লাইনটিই কিন্তু একটি কিউ। ধরি আমাদের দাড়ানোর সিরিয়ালটি এরকম ঃ তারেক->আমি->জামি->আহানাফ->ইসলাম।
তাহলে কিউ এর একদম প্রথমে আছে তারেক। যখন ওর টিকেট কিনা হয়ে যাবে, ও সামনে দিয়ে লাইন থেকে বের হয়ে যাবে। প্রোগ্রাম এর ভাষায় একে বলে পপ ( pop() ). তাহলে তারেক পপ হবার পরে কিউ এর সামনে থাকবো এখন আমি। এভাবে যে আগে কিউ তে প্রবেশ করবে, সে আগে বের হবে, এটা হল আসল কথা।

#include<queue>
using namespace std;
int main()
{
        queue <string> q;
        q.push("Tarek");                         // কিউ তে insert এর জন্য push() ফাংশন
        q.push("Shishir");
        q.push("Jami");
        q.push("Ahanaf");
        q.push("Islam");
        while ( !q.empty() )
        {
                 cout << q.front() << endl;  // কিউ এর প্রথম এলেমেন্ট প্রিন্ট করলাম
                 q.pop();                              // কিউ এর প্রথম এলেমেন্ট রিমুভ করলাম
        }
return 0;
}

প্র্যাকটিস এর জন্য কিছু প্রব্লেম ঃ

১। একটি কিউ এ ১ থেকে ১০০ পর্যন্ত নম্বর পুশ কর এবং এর মধ্যে থেকে কেবল মাত্র জোড় সংখ্যাগুলো প্রিন্ট কর।

২। কিউ তে কতগুলি স্ট্রিং পুশ কর এবং তাদেরকে LIFO আকারে প্রিন্ট কর। (using queue, print the values like stack).

স্ট্রিং ( String )

  স্ট্রিং(String)

স্ট্রিং একটি বেশ মজার এবং কাজের ডাটা স্ট্রাকচার। এর কাজ নরমাল ক্যারেক্টার অ্যারে এর মতই, কিন্তু এর ব্যবহার খুব সহজ এবং অনেক কাজ অনেক সহজে করা যায়। স্ট্রিং এর জন্য হেডার ফাইল : #include<string>
একটি কোড দেখা যাক -->

#include<string>
using namespace std;
int main()
{
                string a; // স্ট্রিং টাইপ একটি ভ্যারিয়েবল 'a' ডিক্লার করলাম
                cin >> a; // user থেকে ইনপুট নিলাম
                cout << a << endl; // ইনপুট এর স্ট্রিং প্রিন্ট করলাম
                return 0;
}

স্ট্রিং এর ক্ষেত্রে এভাবে নিয়ে আমরা স্ট্রিং প্রিন্ট করতে পারি। কিন্তু এখানে স্পেস এর পরে কোন ক্যারেক্টার প্রিন্ট হবেনা। তোমরা ইনপুট নিয়ে দেখতে পারো। এরকম ক্ষেত্রে আমরা তাহলে কি করবো? আমাদের দরকার পুরা একটি লাইন ইনপুট নেয়া। এরজন্য ইনপুট নিতে হবে এভাবে-->

getline ( cin, a );

getline() ফাংশন এর কাজ হচ্ছে লাইন শেষ না হওয়া পর্যন্ত ইনপুট নিবে। এখন আমরা স্পেস সহ ইনপুট নিতে পারবো। উপরের কোড এ cin>>a এর বদলে getline (cin,a) লিখে তোমরা ব্যাপারটা দেখতে পারো।

স্ট্রিং এর মজার ব্যাপার হচ্ছে স্ট্রিং কে আরেক স্ট্রিং এ সরাসরি কপি, অ্যাড করা যায়।

string a,b,c;
a = "I eat rice";
b = " and I eat pizza.";
c = a + b;
cout << c << endl;          // এখানে আউটপুট হবে : "I eat rice and I eat pizza"

সুন্দরভাবে concatanation হয়ে গেলো!! সি তে char array নিয়ে করতে গেলে ব্যাপারটা এত সহজ না।

string.size() ফাংশন স্ট্রিং এর সাইজ রিটার্ন করে (integer).
কোন একটি স্ট্রিং কে উলটা করে লিখার জন্য আমরা এভাবে for loop ব্যবহার কতে পারি-->

string a;
cin >> a;
int len = a.size();
string b = "";                 // একটি empty string ডিক্লার করলাম
for ( int i = len-1, pos = 0; i >= 0; i--, pos++ )
b [ pos ] = a [ i ];
cout << b << endl;       // রিভার্স করা স্ট্রিংটি 'b' এর মধ্যে আছে এখন।

সি++ এ আমরা reverse() ফাংশন ব্যবহার করে স্ট্রিং কে কোন লুপ কোড লিখা ছাড়াই রিভার্স করতে পারি এভাবেঃ
reverse ( a.begin(), a.end() );    // a = string variable

স্ট্রিং অনেকগুলি ক্যারেক্টার এর একটি অ্যারে। তাই নরমাল সি এর char array এর মত স্ট্রিং কেও ইনডেক্স অনুযায়ী এক্সেস করা যায়, প্রসেস করা যায়। যেমন, স্ট্রিং a এর 0th ইনডেক্স এর ক্যারেক্টার হবেঃ a [ 0 ]

স্ট্রিং একটি নরমাল ডাটা টাইপ (like int,float,double), কাজেই এটাকে আমরা অন্যান্য ডাটা টাইপ লিখার জন্য যেভাবে লিখি, সেভাবে লিখতে পারবো।
স্ট্রিং এর ভেক্টর: vector < string > string_vec;
স্ট্রিং এর স্ট্যাক: stack < string > string_stack;  এরকম।

স্ট্রিং এর জিনিসগুলি ভালোভাবে রপ্ত করার জন্য তোমরা নিচের সমস্যাগুলি চেষ্টা করতে পারোঃ

১। একটি স্ট্রিং প্যালিন্ড্রম কিনা চেক কর।
example :
hello -> not palindrome
1234321 -> palindrome
wecanacwe ->not palindrome

২। একটি স্ট্রিং দেয়া হবে। যেখানে কেবলমাত্র 0 এবং 1থাকবে। একে ডেসিমাল ভ্যালুতে প্রকাশ কর
example :
00000010 -> the decimal value is 2
111 -> the decimal value is 7

৩। একটি স্ট্রিং এ মোট কতটি ওয়ার্ড আছে এবং কিকি লিখ।
example :
Hello, how are you ?
--> there are 4 words. They are : Hello, how, are, you.

স্ট্যাক ( Stack )

স্ট্যাক (stack)

ধরি আমি কোন রেস্টুরেন্ট এ কাজ করি। আমার কাজ হচ্ছে থালাবাসন পরিষ্কার করা। এখন আমি এক গাদা প্লেট খাবার টেবিল থেকে নিয়ে ধুবো এবং এরপরে প্লেটগুলি স্তুপ করে একটার উপর একটা রাখবো। এখন লক্ষ্য করলে দেখবে যে প্লেট টা সবার আগে পরিষ্কার করলাম, সেটা কিন্তু স্তুপ এর সবার নিচে আছে। অর্থ্যাৎ আরেকভাবে বললে , যে প্লেট টা সবার পরে পরিষ্কার করলাম সেটা স্তুপ এর সবার উপরে আছে। এখন আমি পরিষ্কার প্লেটগুলি যখন নিবো, তখন কিন্তু স্তুপ এর উপরের থেকেই নেয়া শুরু করবো। অর্থ্যাৎ যে সবার আগে স্তুপ থেকে বের হবে, সে আসলে সবার শেষে স্তুপ এ ঢুকেছিল।

এটি ই স্ট্যাক এর মূল বৈশিষ্ট। একে আমরা বলি “Last In First Out” বা সংক্ষেপে “LIFO”.
এই জিনিসটাকে বলে স্ট্যাক। মানে আমরা সবার পরে যাকে প্রসেসিং করতে ঢুকাচ্ছি তাকে যদি আগে প্রসেসিং করি তাহলে সেটাই স্ট্যাক। STL এ স্ট্যাক ব্যবহার করতে হয় এভাবে,

#include <stack>
using namespace std;
int main()
{
        stack s;  //  একটি ইন্টিজার এর স্ট্যাক
        s.push( 10 );
        s.push( 20 );
        s.push( 30 );
}
/* 10, 20, 30 কে স্ট্যাক এ পুশ করলাম। এখন আমার স্ট্যাক টা দেখতে হবে অনেকটা এরকম
30 // top value of the stack (LIFO)
20
10
*/অর্থাৎ স্ট্যাক এ এখন ৩ টি ভ্যালু আছে।

তাই, স্ট্যাক এর সাইজ হবে ৩।  s.size() এর মাধ্যমে আমরা স্ট্যাক এর সাইজ জানতে পারি।

এখন আমরা স্ট্যাক এর টপ ভ্যালু দেখতে চাইলে যে ফাংশন ব্যবহার করবো তাহলো top() ফাংশন।

int x = s.top();    // x এর মধ্যে স্ট্যাক এর টপ (30) ভ্যালু আছে
cout << x << endl; // x = 30;

এখন যদি আমরা পরের ভ্যালু দেখতে চাই, তাহলে আমাদের আগে টপ এর ভ্যালু কে মুছে ফেলতে হবে। মুছে ফেলার জন্য আমরা ব্যবহার করবো pop() ফাংশন।

s.pop();       // স্ট্যাক এর টপ টাকে ডিলেট করে ফেললাম।
এখন আমার স্ট্যাক এর টপ ভ্যালু হবে 20.

আরেকটা গুরুত্বপুর্ণ ফাংশন হলো empty()
এর কাজ হল স্ট্যাক টা খালি (NULL) আছে কিনা তা চেক করা।

একটি কোড দেখা যাক,

while( !s.empty() )
{
        cout<< s.top() <<endl; // printing the top element;
        s.pop(); // removing the top element;
}
// যতক্ষন স্ট্যাক টা নাল না হবে, ততক্ষন স্ট্যাক এর এলেমেন্ট গুলি প্রিন্ট করলাম

স্ট্যাক দিয়ে আমরা অনেকরকম প্রব্লেম সল্ভ করতে পারি। এর মধ্যে ব্র্যাকেট ম্যাচিং (Bracket Matching or Paranthesis Matching) উল্লেখযোগ্য। তোমরা এগুলো একটু ঘাটাঘাটি করে দেখতে পারো। paranthesis matching নিয়ে পরে কোন এক পোস্ট এ কিছু লিখবো।

ভেক্টর ( Vector )

STL

সি++ এ বিশাল একটি লাইব্রেরী আছে, যার কোডগুলো যেকোন ধরণের ডাটার জন্য কাজ করতে পারে। এই টেম্প্লেট লাইব্রেরীর সবচেয়ে স্ট্যান্ডার্ড ভার্শনটার নামই স্ট্যান্ডার্ড টেম্প্লেট লাইব্রেরী, ওরফে STL।
STL হল একটা বেশ বড়সড় একটা লাইব্রেরী। আমাদের শুধু জানতে হবে সেটা আমরা কিভাবে ব্যবহার করবো। এখন আমরা কিছু STL নিয়ে আলোচনা করবো।

ভেক্টর (vector)

মাঝে মাঝে আমাদের এমন কিছু দরকার হয় যেখানে সাড়ি থাকবে n সংখ্যক, প্রতি সাড়ি তে আবার m সংখ্যক কলাম ও থাকবে। এখানে n,m <= 10000. এবং বলা আছে, কোন কোন সাড়ি তে আবার কলাম নাও থাকতে পারে, মানে ব্যাপারটা এভাবে চিন্তা করলে দেখা যায়, এমন সাড়ি থাকতে পারে যেখানে 10000 এর মতন কলাম আছে, আবার এমন সাড়িও থাকতে পারে যেখানে অনেক কম কলাম আছে। 10000 টা সাড়ি থাকতে পারে যার প্রতিটি মাত্র 5-6 টি কলাম নিয়ে আছে।আর বলা আছে, সাড়ি এবং কলাম মিলে 1000000 এর বেশি কোন ভ্যালু নেই। এখন কথা হল, আমরা যদি এরকম একটা scenario কল্পনা করি তাহলে আমরা 2D (Dimensional ) অ্যারে এর কথা ভাবতে পারি এভাবে,

int a[10000][10000]; // ইনটিজার টাইপ এর একটি অ্যারে, a
এটা কিন্তু বেশ বড়সড় একটা অ্যারে। আমার কম্পিউটার মাথা ঘুরে পড়ে যাবে তাকে এই পরিমান মেমরি অ্যালোকেট করতে বললে, কিন্তু আমার আসলে এত বেশি জায়গা লাগছে না, কারন আমাকে বলেই দেয়া হয়েছে ডাটা সবমিলে সর্বোচ্চ 1000000 টা থাকতে পারে। এধরণের সময়, আমরা ডাইনামিক মেমরি অ্যালোকেট করি - ঠিক যতটুকু মেমরি দরকার ঠিক ততটুকুই নেই। যেটা ম্যানুয়ালি করা বেশ কষ্টকর, আর সেটায় মেমরি পরিষ্কারও করে দিতে হয় কাজ শেষে, নইলে সব ডাটা জমতে জমতে কম্পিউটারের crash করার সম্ভাবনা প্রায় ৮৫% (:P)।
ভেক্টর হলো একটা অ্যারে, যেটায় ডাইনামিকালি জিনিসপাতি ঢুকিয়ে রাখা যায়। মানে, এটাও একটা অ্যারে, কিন্তু সেটা ঠিক ততটুকু মেমরি খায়, যতটুকু খাওয়া লাগে।

ভেক্টর এর হেডার ফাইল ঃ #include<vector>
ভেক্টর ডিক্লেয়ার করে এভাবেঃ  vector< int > a;

যদি অন্য কোন টাইপের ডাটা নিতে চাই তাইলে int এর জায়গায় সেই ডাটার নাম লিখতে হবে। যেমন এটা আরো কিছু অ্যারে।
vector< double > hash;
vector< long long > balti;
vector< char > cow;
vector< float > dalim;

ভেক্টরে কোন ডাটা রাখতে হলে, সেই ভেক্টরের শেষে ডাটাটাকে পুশ করতে হয়।
a.push_back( 100 );       // push_back() function
আর ভেক্টরে কয়টা ডাটা আছে সেটা আমরা জানতে পারি .size() ফাংশনকে কল করে। যেমন আমি একটা ভেক্টরে কিছু ইন্টেজার ঢুকাবো, তারপর সবাইকে প্রিন্ট করবো, সেটার কোড হবে এরকমঃ

int main() {
vector< int > v;
v.push_back( 1 );
v.push_back( 2 );
v.push_back( 3 );
v.push_back( 4 );
for( int i = 0; i < v.size(); i++ )
cout << v[i] << endl;
return 0;
}

বাকি সব কিছুতে ভেক্টরকে সাধারণ অ্যারের মত ব্যবহার করা যায়। যেমন আমি 0th এলিমেন্টটা পাল্টে দিতে পারি v[0] = 10000 লিখে। আরেকটা সুবিধা হচ্ছে আমরা অ্যারেতে সরাসরি কপি করতে পারি না । কিন্তু ভেক্টরে সেটা করা যায়ঃ

int main() {
vector< int > v, cp;
v.push_back( 1 );
v.push_back( 2 );
v.push_back( 3 );
v.push_back( 4 );
cp = v; // copying
for( int i = 0; i < cp.size();  i++ )
cout << cp[i] << endl;
return 0;
}

ভেক্টরে যদি আমি 2D ডাটা রাখতে চাই তাহলে সেটা দুভাবে করা যায়
vector< int > v[100];
vector< vector< int > > v;

প্রথমটি বেশি preferable, তবে এখানে  row  ১০০ টাই থাকবে,আমি ১ টি row ব্যবহার করলেও প্রোগ্রাম ১০০ টার জন্য জায়গা নিয়ে রাখবে।
পরেরটির কলাম ও ডাইনামিকালি চেঞ্জ করা যাবে।
* vector< vector< int >> v; এভাবে লিখলে >> এর জন্য কিছু কম্পাইলর কিন্তু এরর দিবে।
তাই সাবধানতা অবলম্বন করে spacing ব্যবহার করা ভালো।

সমস্যা

১. ১০ থেকে ১০০০০ এর মাঝের সকল বেজোড় সংখ্যা ভেক্টরের মাঝে নিয়ে প্রিন্ট কর।
২. N সংখ্যক ইন্টিজার এবং k একটি সংখ্যা দেয়া হবে। তোমাকে বলতে হবে k সংখ্যাটি N সংখ্যক                 ইন্টিজার এর মাঝে কতবার আছে?
৩. N সংখ্যক ইন্টিজার কে ছোট থেকে বড় আকারে প্রিন্ট কর।
৪. N সংখ্যক ইন্টিজার দেয়া হবে। প্রতিটি ইন্টিজার কতবার করে আছে (ascending order) প্রিন্ট কর।
Input :
6
10 10 2 3 2 8
Output :
2 is 2 times.
3 is 1 times.
8 is 1 times.
10 is 2 times.