您好,歡迎來到網暖!
?
當前位置:網暖 » 站長資訊 » 建站基礎 » 網絡技術 » 文章詳細 訂閱RssFeed

STL中有關deque、stack、queue、priority_queue

來源:網絡整理 瀏覽:369次 時間:2020-02-29
deque

deque中的修改類接口STL中有關deque、stack、queue、priority_queue
由于deque是雙端隊列,所以有頭插頭刪和尾插尾刪操作。
下面的棧和隊列的底層都是通過的deque實現的。
為什么要用deque作為其底層數據結構呢?
主要是因為:棧和隊列都只需在一頭進行操作,故不需要迭代器,只要具有pushback和popback的功能即可,在元素增長時deque比vector效率更高、內存使用率高,所以用deque作為底層數據結構更合適。

stack

STL中有關deque、stack、queue、priority_queue
根據文檔里的內容我們可以看到stack中有這些接口。
在使用時要包含stack頭文件
因為其底層是用deque實現的:所以有關它的模擬實現也就是對deque的一個封裝。
例如:

template<class T,class Container=deque<T>>    class stack//棧    {    public:        stack()        {        }        void push(const T&data)        {            _con.push_back(data);        }        private:        Container _con;    }


queue

STL中有關deque、stack、queue、priority_queue
注意隊列不同的是由front和back操作,分別是隊首和隊尾元素。



priority_queue優先隊列

底層使用堆實現的!
創建優先隊列的默認是按照大堆(比較參數是less)方式!也就是說每個根節點都大于它的孩子節點。

構造函數:std::priority_queue<int, std::vector<int>, std::greater<int> >
third (myints,myints+4);
上例是構造了一個小堆類型的優先級隊列
它的模板參數列表:template&lt;class T, class Container=vector&lt;T&gt;, class Compare=less&lt;T&gt;&gt;
所以如果想要用小堆創建對象時要把第三個參數改為great。

這里我們把庫函數中的less這個函數拿來看一下:

template<class _Ty = void>    struct less        : public binary_function<_Ty, _Ty, bool>    {   // functor for operator<    bool operator()(const _Ty& _Left, const _Ty& _Right) const        {   // apply operator< to operands        return (_Left < _Right);        }    };

如果在優先級隊列內存放自定義類型數據,需要需要用戶提供<、>的重載,有時也要對提供比較器規則,參考less和greater在庫函數中的實現,即對()進行重載。


模擬實現優先級隊列:

namespace mine    {        template <class T, class Container = vector<T>, class Compare = less<T>>//默認(less)創建的是大堆        class priority_queue        {        public:            priority_queue()                :c()            {}            template<class Iterator>            priority_queue(Iterator first, Iterator last)//區間構造,將root進行向下調整                : c(first, last)            {                // 將c中的元素調整成堆的結構                int count = c.size();                int root = ((count - 2) >> 1);                for (; root >= 0; root--)                    AdjustDown(root);            }            void push(const T & data)            {                c.push_back(data);                AdjustUP(c.size()-1);//傳入下標            }            void pop()//頭刪的話先將頭元素與最后一個元素交換,把最后一個元素刪掉后再執行向下排序            {                if (empty())                    return;                else                {                    swap(c.front(), c.back());                    c.pop_back();                    AdjustDown(0);                }            }            int size()const            {                return c.size();            }            bool empty()const            {                return c.empty();            }            const T & top()const            {                return c.front();            }        private:            //這里的向上調整和向下調整都是大堆模式            void AdjustDown(int parent)//向下調整算法,把較小元素調整下去            {                int child = parent * 2 + 1;//child代表下標                while (child < c.size())                {                    //找到以parent為根的較大的孩子                    //如果根有右孩子并且左孩子比右孩子小,讓child等于右孩子                    //即child此時為較大的孩子                    if (child + 1 < c.size() && com(c[child], c[child + 1]))                    {                        child = child + 1;                    }                    //如果孩子節點比父親節點大則交換                    if (com(c[parent], c[child]))                    {                        swap(c[child], c[parent]);                        parent = child;                        child = parent * 2 + 1;                    }                    else                        return;                }            }            void AdjustUP(int child)//向上調整算法,將較大元素調整上去            {                int parent = (child - 1) >> 1;                while (child)//沒有到根的話繼續循環                {                    //如果父親節點比孩子節點小,交換                    //將較大節點調整到根位置                    if (com(c[parent], c[child]))                    {                        swap(com(c[parent], c[child]));                        child = parent;                        parent = (child - 1) >> 1;                    }                    else                    {                        return;                    }                }            }        private:            Container c;            Compare com;        };    }

這里最重要的就是向上調整和向下調整算法,同時也要注意比較規則在其中的用法。詳細過程見代碼注釋。

推薦站點

  • 騰訊騰訊

    騰訊網(www.QQ.com)是中國瀏覽量最大的中文門戶網站,是騰訊公司推出的集新聞信息、互動社區、娛樂產品和基礎服務為一體的大型綜合門戶網站。騰訊網服務于全球華人用戶,致力成為最具傳播力和互動性,權威、主流、時尚的互聯網媒體平臺。通過強大的實時新聞和全面深入的信息資訊服務,為中國數以億計的互聯網用戶提供富有創意的網上新生活。

    www.qq.com
  • 搜狐搜狐

    搜狐網是全球最大的中文門戶網站,為用戶提供24小時不間斷的最新資訊,及搜索、郵件等網絡服務。內容包括全球熱點事件、突發新聞、時事評論、熱播影視劇、體育賽事、行業動態、生活服務信息,以及論壇、博客、微博、我的搜狐等互動空間。

    www.sohu.com
  • 網易網易

    網易是中國領先的互聯網技術公司,為用戶提供免費郵箱、游戲、搜索引擎服務,開設新聞、娛樂、體育等30多個內容頻道,及博客、視頻、論壇等互動交流,網聚人的力量。

    www.163.com
  • 新浪新浪

    新浪網為全球用戶24小時提供全面及時的中文資訊,內容覆蓋國內外突發新聞事件、體壇賽事、娛樂時尚、產業資訊、實用信息等,設有新聞、體育、娛樂、財經、科技、房產、汽車等30多個內容頻道,同時開設博客、視頻、論壇等自由互動交流空間。

    www.sina.com.cn
  • 百度一下百度一下

    百度一下,你就知道

    www.baidu.com
?
陕西11选5走势图前3直