C++ STL :: queue

কিঊঃ

আগে আসলে আগে পাবেন, এই রকমের একটা ডাটা স্ট্রাকচার হল কিউ, যাকে আমরা বলি ফার্স্ট ইন ফার্স্ট আউট (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/

About these ads
  1. কোন মন্তব্য নেই এখনও
  1. অক্টোবর 18, 2010 at 6:41 পুর্বাহ্ন

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / পরিবর্তন )

Twitter picture

You are commenting using your Twitter account. Log Out / পরিবর্তন )

Facebook photo

You are commenting using your Facebook account. Log Out / পরিবর্তন )

Google+ photo

You are commenting using your Google+ account. Log Out / পরিবর্তন )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 45 other followers

%d bloggers like this: