আর্কাইভ

Archive for জুলাই, 2010

C++ STL :: queue

জুলাই 30, 2010 ১টি মন্তব্য

কিঊঃ

আগে আসলে আগে পাবেন, এই রকমের একটা ডাটা স্ট্রাকচার হল কিউ, যাকে আমরা বলি ফার্স্ট ইন ফার্স্ট আউট (FIFO)। এটা C++ STL এর সবচেয়ে বেশি ব্যবহৃত কন্টেইনার ক্লাস। queue এর সামনের দিক থেকে ডাটা এক্সট্র্যাক্ট করা হয়, আর ইনসার্ট করা হয় তার বিপরীত দিক থেকে। তাই, যে সব STL কন্টেইনার push_back() আর pop_front() সাপোর্ট করে সেগুলো দিয়ে কিউ ইমপ্লিমেন্ট করা যায়, যেমন list আর deque. অবশ্য queue এর ডিফল্ট কন্টেইনার হল deque, যদি কিছু বলে না দেয়া হয়। stack এর মত queue ও একটা অ্যাডাপ্টার ক্লাস।

queue ব্যবহার করতে চাইলে std <queue> হেডারটা প্রোগ্রামে ইনক্লুড করতে হবেঃ

#include <queue>
using namespace std;

কন্সট্রাকশনঃ

অন্যান্য কন্টেইনার ক্লাসের মত queue এর সাধারণ কন্সট্রাক্টর queue< type_t > myqueue; এই ধরনের। এছাড়া এক্সপ্লিসিট কন্টেইনার ডিক্লেয়ার করেও queue কন্সট্রাক্ট করা যায়, যেমনঃ

// constructing queues
#include <deque>
#include <list>
#include <queue>
using namespace std;

int main ()
{
	deque< int > mydeck(3,100); // deque with 3 elements
	list< int > mylist(2,200); // list with 2 elements
	
	// implicit declaration
	queue< int > first; // empty queue
	queue< int > second(mydeck); // from a mydeck
	queue< int > third(second); // from another queue
	
	// explicit declaration
	queue< int, list< int > > fourth; // empty queue 
	queue< int, list< int > > fifth(mylist); // from mylist
	queue< int, deque< int > > sixth; // empty queue
	queue< int, deque< int > > seventh(mydeck); // from mydeck
	
	// initialization with operator=
	queue< int > eighth = first; // initialized with first

	return 0;
}

কমপ্লেক্সিটিঃ কন্সট্রাক্টরের সাপেক্ষে কন্সট্যান্ট, অর্থাৎ কন্টেইনারের উপরে নির্ভর করে।

পুশ আর পপঃ

queue এ ডাটা ইন্সার্ট আর এক্সট্র্যাক্ট করার জন্য ২ টা মেম্বার ফাংশন আছে, push() আর pop()। push() এর কাজ হল queue এর শেষে এলিমেন্ট ইন্সার্ট করা আর pop() এর সাহায্যে queue এর সামনে থেকে কোন এলিমেন্ট বের করে দেয়া। যেমনঃ

// queue::push/pop
#include <iostream>
#include <queue>
using namespace std;

int main()
{
	queue< int > Q;
	
	// push 5 integers
	for(int i=1; i<=5; i++) Q.push(i);
	
	// pop 5 integers
	// will be popped in the same order they were pushed
	for( ; !Q.empty() ; )
	{
		cout << Q.front() << endl;
		Q.pop();
	}
	
	return 0;
}

কমপ্লেক্সিটিঃ কন্সট্যান্ট।

ফ্রন্ট আর ব্যাক

queue তে এলিমেন্ট এক্সেসের জন্য ২ টা ফাংশন হল front() আর back(); front() দিয়ে queue এর ফার্স্ট এলিমেন্ট এক্সেস করা যায়, আর back() দিয়ে লাস্ট ইন্সার্ট করা এলিমেন্ট কে পাওয়া যায়। front() আর back() এর এলিমেন্ট কে স্ট্যান্ডার্ড অপারেটর গুলর সাহায্যে মডিফাই করা যায়। যেমনঃ

// queue::front/back
#include <iostream>
#include <queue>
using namespace std;

int main ()
{
	queue<int> myqueue;
	
	myqueue.push(77);
	myqueue.push(16);
	cout << "myqueue.front() = " << myqueue.front() << endl;
	cout << "myqueue.back() = " << myqueue.back() << endl;
	
	// modify front element
	myqueue.front() -= myqueue.back();
	cout << "myqueue.front() is now " << myqueue.front() << endl;
	
	// modify back element
	myqueue.back() += myqueue.front();
	cout << "myqueue.back() is now " << myqueue.back() << endl;

	return 0;
}

কমপ্লেক্সিটিঃ কন্সট্যান্ট।

কিউ কি খালি?

queue এ এই মুহূর্তে কত গুলা এলিমেন্ট আছে সেটা জানা যায় size() ফাংশনের মাধ্যমে, আর empty() ফাংশন টা boolean, queue খালি থাকলে true দেয়, না হলে false; queue খালি কি না, সেটা চেক করা হয় empty() দিয়ে, কখনই size() এর ভ্যালু ০ কিনা এটা দেখে queue খালি কিনা, সেই টেস্ট করা উচিৎ না, আর queue তে pop() করার আগে আবশ্যই দেখে নিতে হবে queue এ কোন এলিমেন্ট আছে কিনা, তা না হলে run-time error হতে পারে। নিচের কোডে size() আর empty() এর প্রয়োগ দেখানো হলঃ

// queue::size/empty
#include <iostream>
#include <queue>
using namespace std;

int main ()
{
	queue<int> Q;
	
	// just push some elements
	for(int i = 0; i < 5; i++) Q.push(i*i);
	
	cout << "Queue has " << Q.size() << " elements" << endl;
	
	Q.pop(); // not a good way, first check for Q.empty()
	
	if(!Q.empty()) Q.pop(); // this is the porper way
	
	while(!Q.empty()) Q.pop(); // pop all element
	
	if(Q.size()==0) cout << "Q is empty" << endl; // not a good way
	if(Q.empty()) cout << "Q is empty" << endl; // this is the proper way
	
	return 0;
}

কমপ্লেক্সিটিঃ কন্সট্যান্ট।

ব্যবহারঃ

FIFO ডাটা স্ট্রাকচার হিসাবে, BFS ট্রাভার্সাল, বিভিন্ন গ্রাফ এলগরিদমে queue ইম্পলিমেন্ট করা হয়।

বিস্তারিতঃ http://www.cplusplus.com/reference/stl/queue/

Advertisements

C++ STL :: stack

জুলাই 29, 2010 12 comments

স্ট্যাকঃ

STL কন্টেইনারদের মধ্যে সম্ভবত সবচেয়ে সিম্পল ডাটা স্ট্রাকচার হল stack, এটা একটা লাস্ট ইন ফার্স্ট আউট (LIFO) ডাটা স্ট্রাকচার, মানে হল যে সবার শেষে আসবে, সে সবার আগে ভাগবে… সোজা কথায় এই কন্টেইনারের শুধুমাত্র একটা দিকেই ডাটা ইন্সার্ট বা এক্সট্র্যাক্ট করা হয়। আর STL এ stack তার ডিফল্ট ইন্টার্নাল ডাটা স্ট্রাকচার হিসাবে ব্যবহার করে STL এরই deque কন্টেইনার, তবে চাইলে vector বা list ও ব্যবহার করা যেতে পারে। যে সব কন্টেইনার push_back() আর pop_back() মেথড ২ টা সাপোর্ট করে সেগুলোকেই stack এর কন্টেইনার ক্লাস হিসাবে ব্যবহার করা যায়। stack আসলে একটা অ্যাডাপ্টার ক্লাস, অর্থাৎ, এটা তৈরি করা হয় এর ইন্টারনাল কন্টেইনারের স্পেসিফিক কিছু ফাংশনকে এলিমেন্ট একসেসের অনুমতি দিয়ে।

stack ব্যবহার করতে চাইলে সর্বপ্রথম কাজটা হল std <stack> হেডারটা প্রোগ্রামে ইনক্লুড করাঃ

#include <stack>
using namespace std;

কন্সট্রাক্টরঃ

অন্যান্য STL কন্টেইনার ক্লাসের মত stack এরও সাধারণ কন্সট্রাক্টর stack< type_t > myStack; এই রকমের, তবে আরো অনেকভাবে ডিক্লেয়ার করা যায়। যেমনঃ

// constructing stacks
#include <list>
#include <vector>
#include <deque>
#include <stack>
using namespace std;

int main ()
{
    // using default container deque

    stack< int > first; // empty stack
    deque< int > mydeque(3, 100); // deque with 3 elements
    stack< int > second(mydeque); // from mydeque
    stack< int > third(second); // from another stack second

    // explicit container declarations

    stack< int, deque< int > > fourth; // empty stack using deque
    deque< int > newdeque(10, 100); // deque with 10 elements
    stack< int, deque< int > > fifth(newdeque); // from newdeque

    stack< int, vector< int > > sixth;  // empty stack using vector
    vector< int > myvector(2, 200); // vector with 2 elements
    stack< int, vector< int > > seventh(myvector); // from myvector

    stack< int, list< int > > eighth; // empty srack using list
    list< int > mylist(4, 100); // list with 4 elements
    stack< int, list< int > > ninth(mylist); // from mylist

    // can refer to some other stack
    stack< int > tenth = first; // declaration time initialization

    return 0;
}

কমপ্লেক্সিটিঃ কন্টেইনার কন্সট্রাকশনের সাপেক্ষে কন্সট্যান্ট, অতএব কি ধরণের কন্টেইনার ব্যবহার করা হচ্ছে তার উপরে নির্ভর করে।

এলিমেন্ট একসেসঃ

stack ক্লাসের এলিমেন্ট গুলাকে একসেস করার জন্য ৩ টা মেম্বার ফাংশন আছেঃ

  1. top()
  2. push()
  3. pop()

push() ফাংশনটার কাজ stack এর শেষে কোন এলিমেন্ট ইন্সার্ট করা, আর pop() দিয়ে লাস্ট এলিমেন্ট টা বের করে দেয়া। top() এর সাহায্যে কারেন্টলি stack এ সবার উপরের এলিমেন্ট কে পাওয়া যায়। top() এলিমেন্টকে স্ট্যান্ডার্ড অপারেটরদের সাহায্যে মডিফাই করা যায়।

আর, stack এর এলিমেন্ট কাউন্ট করার জন্য ২ টা ফাংশন আছেঃ

  1. size()
  2. empty()

size() ব্যবহার করে জানতে পারি এই মুহূর্তে stack এ কতগুলো এলিমেন্ট আছে, আর empty() একটা boolean ফাংশন, stack খালি থাকলে এটা true দেয়, না হলে false, stack এ pop() মেথডটা ব্যবহার করতে চাইলে আগে অবশ্যই চেক করে নিতে হবে stack এ কিছু আছে কিনা, তা না হলে run-time error হতে পারে।

নিচে এই ফাংশন গুলার কাজ দেখানো হলঃ

// stack::push/pop/top/size/empty
#include <iostream>
#include <stack>
using namespace std;

int main ()
{
    stack< int > mystack;
    // lets push and pop some values
    for (int i=0; i<5; i++) mystack.push(i);

    cout << "Popping out elements...";
    while (!mystack.empty())
    {
        cout << " " << mystack.top();
        mystack.pop();
    }
    cout << endl;

    // changing the value of top
    mystack.push(100);
    mystack.top() += 1000;
    cout << "Now top is: " << mystack.top() << endl;
    mystack.pop();

    // not a good way to check if stack is empty
    if(mystack.size() == 0) cout << "Stack is empty" << endl;
    // better we do this
    if(mystack.empty()) cout << "Stack is empty" << endl;

    return 0;
}

কমপ্লেক্সিটিঃ প্রতিটা ফাংশনের কম্পলেক্সিটি কন্সট্যান্ট।

ব্যবহারঃ

সাধারণত এক্সপ্রেশন / গ্রামার প্রসেসিং, রিকারসিভ এলগরিদমের নন রিকারসিভ প্রয়োগ, DFS ট্রাভার্সাল, LIFO অপারেশনে stack ব্যবহার করা হয়। STL এর stack একটা টেমপ্লেট ক্লাস, তাই যে কোন ডাটা টাইপের জন্য খুব দ্রুত stack ইম্পলিমেন্ট করা যায় STL ব্যবহার করে।

বিস্তারিতঃ http://www.cplusplus.com/reference/stl/stack/