अंतिम अद्यतन：2026-10-12

STL queue तथा stack सोर्स कोड विश्लेषण¶

0.प्रस्तावना¶

stack तथा queue को कंटेनर क्यों नहीं कहा जाता?

इस अनुभाग में इसी प्रश्न के साथ सोर्स कोड का गहन विश्लेषण करेंगे।

1.stack¶

stack के सोर्स कोड में हम दो बातों पर ध्यान देते हैं: - डिफ़ॉल्ट _Sequence है deque - आंतरिक फंक्शन्स का कार्यान्वयन _Sequence के संगत कंटेनर के फंक्शन्स को कॉल करता है।

template<typename _Tp, typename _Sequence = deque<_Tp> >
class stack
{

public:
    typedef typename _Sequence::value_type                value_type;
    typedef typename _Sequence::reference                 reference;
    typedef typename _Sequence::const_reference           const_reference;
    typedef typename _Sequence::size_type                 size_type;
    typedef          _Sequence                            container_type;

protected:
    //  See queue::c for notes on this name.
    _Sequence c;

public:
     reference
      top()
      {
        __glibcxx_requires_nonempty();
        return c.back();
      }
    void
      push(const value_type& __x)
      { c.push_back(__x); }
}

stack के अंतर्निहित कंटेनर का परीक्षण

stack के लिए, अंतर्निहित कंटेनर vector, deque, list हो सकता है, परंतु map, set नहीं। चूँकि कंपाइलर सर्वांगीण जाँच नहीं करता, जब कॉल किया गया फंक्शन मौजूद नहीं होता तभी संकलन असफल होता है; इसलिए set जैसा कंटेनर भले ही अंतर्निहित कंटेनर नहीं बन सकता, पर यदि उसमें कुछ फंक्शन्स मौजूद हों तो कॉल तब तक सफल रहती है जब तक कॉल किया गया फंक्शन मौजूद न हो।

int test_stack() {
    cout<<"============test_stack============="<<endl;
    clock_t timeStart = clock();
    stack<int, list<int>> c;
    for (long i = 0; i < 100000; i++)
        c.push(i+1);
    cout << "stack.size()= " << c.size() << endl;
    cout << "stack.top()= " << c.top() << endl;
    c.pop();
    cout << "stack.size()= " << c.size() << endl;
    cout << "stack.top()= " << c.top() << endl;
    cout << "use stack milli-seconds : " << (clock() - timeStart) << endl;
    timeStart=clock();
    stack<int, deque<int>> c1;
    for (long i = 0; i < 100000; i++)
        c1.push(i+1);
    cout << "stack.size()= " << c1.size() << endl;
    cout << "stack.top()= " << c1.top() << endl;
    c1.pop();
    cout << "stack.size()= " << c1.size() << endl;
    cout << "stack.top()= " << c1.top() << endl;
    cout << "use stack milli-seconds : " << (clock() - timeStart) << endl;

    // vector可以作为stack的底层容器
    stack<int, vector<int>> c2;
    for (long i = 0; i < 100000; i++)
        c2.push(i+1);
    cout << "stack.size()= " << c2.size() << endl;
    cout << "stack.top()= " << c2.top() << endl;
    c2.pop();
    cout << "stack.size()= " << c2.size() << endl;
    cout << "stack.top()= " << c2.top() << endl;
    cout << "use stack milli-seconds : " << (clock() - timeStart) << endl;
}

2.queue¶

queue के सोर्स कोड में भी हम दो बातों पर ध्यान देते हैं: - डिफ़ॉल्ट _Sequence है deque - आंतरिक फंक्शन्स का कार्यान्वयन _Sequence के संगत कंटेनर के फंक्शन्स को कॉल करता है।

template<typename _Tp, typename _Sequence = deque<_Tp> >
class queue
{
public:
    typedef typename _Sequence::value_type                value_type;
    typedef typename _Sequence::reference                 reference;
    typedef typename _Sequence::const_reference           const_reference;
    typedef typename _Sequence::size_type                 size_type;
    typedef          _Sequence                            container_type;

protected:

    _Sequence c;

public:

    void push(const value_type& __x)
    { c.push_back(__x); }

    void pop()
    { 
        __glibcxx_requires_nonempty();
      c.pop_front();
    }
}

इसका संगत UML क्लास आरेख इस प्रकार है:

इसी प्रकार, प्रायोरिटी क्यू (priority_queue) vector को डिफ़ॉल्ट कंटेनर के रूप में उपयोग करती है।

template<typename _Tp, typename _Sequence = vector<_Tp>,
typename _Compare  = less<typename _Sequence::value_type> >
class priority_queue
{
public:
    typedef typename _Sequence::value_type                value_type;
    typedef typename _Sequence::reference                 reference;
    typedef typename _Sequence::const_reference           const_reference;
    typedef typename _Sequence::size_type                 size_type;
    typedef          _Sequence                            container_type;

protected:
    //  See queue::c for notes on these names.
    _Sequence  c;
    _Compare   comp;

public:
    reference
    top() 
    {
        __glibcxx_requires_nonempty();
        return c.front();
    }

    void
    push(const value_type& __x)
    {
        c.push_back(__x);
        std::push_heap(c.begin(), c.end(), comp);
    }

}

इन दोनों कंटेनर एडेप्टरों द्वारा समर्थित अंतर्निहित कंटेनरों का परीक्षण:

queue

queue के लिए अंतर्निहित कंटेनर deque हो सकता है, list भी, परंतु vector, map, set नहीं; डिफ़ॉल्ट deque का उपयोग इंसर्शन की दृष्टि से अन्य कंटेनरों के अंतर्निहित होने की तुलना में तेज़ है!

int test_queue() {
    cout<<"============test_queue============="<<endl;
    clock_t timeStart = clock();
    queue<int, list<int>> c;
    for (long i = 0; i < 100000; i++) {
        c.push(i+1);
    }
    cout << "stack.size()= " << c.size() << endl;
    cout << "stack.front()= " << c.front() << endl;
    c.pop();
    cout << "stack.size()= " << c.size() << endl;
    cout << "stack.front()= " << c.front() << endl;
    cout << "use list milli-seconds : " << (clock() - timeStart) << endl;

    timeStart=clock();
    queue<int, deque<int>> c1;
    for (long i = 0; i < 100000; i++) {
        c1.push(i+1);
    }
    cout << "stack.size()= " << c1.size() << endl;
    cout << "stack.front()= " << c1.front() << endl;
    c1.pop();
    cout << "stack.size()= " << c1.size() << endl;
    cout << "stack.front()= " << c1.front() << endl;

    cout << "use deque milli-seconds : " << (clock() - timeStart) << endl;
}

priority_queue

प्रायोरिटी क्यू के लिए, परीक्षण परिणाम बताते हैं कि deque अपनाने पर इंसर्शन डिफ़ॉल्ट vector की तुलना में तेज़ है! अंतर्निहित रूप से vector, deque कंटेनर समर्थित हैं, परंतु list, map, set नहीं।

int test_priority_queue() {
    cout<<"============test_priority_queue============="<<endl;
    clock_t timeStart = clock();

    priority_queue<int, deque<int>> c1;
    for (long i = 0; i < 100000; i++) {
        c1.push(i+1);
    }
    cout << "stack.size()= " << c1.size() << endl;
    cout << "stack.top()= " << c1.top() << endl;
    c1.pop();
    cout << "stack.size()= " << c1.size() << endl;
    cout << "stack.top()= " << c1.top() << endl;

    cout << "use deque milli-seconds : " << (clock() - timeStart) << endl;


    priority_queue<int, vector<int>> c2;
    for (long i = 0; i < 100000; i++)
        c2.push(i+1);
    cout << "stack.size()= " << c2.size() << endl;
    cout << "stack.top()= " << c2.top() << endl;
    c2.pop();
    cout << "stack.size()= " << c2.size() << endl;
    cout << "stack.top()= " << c2.top() << endl;
    cout << "use stack milli-seconds : " << (clock() - timeStart) << endl;
}

अतः stack, queue, priority_queue को कंटेनर नहीं कहा जाता — इन्हें कंटेनर एडेप्टर कहा जाता है।

STL queue तथा stack सोर्स कोड विश्लेषण¶

0.प्रस्तावना¶

1.stack¶

2.queue¶

संबंधित विषय¶

टिप्पणियाँ