【C++】一篇文章带你深入了解stack、queue 和 priority_queue

一、stack的介绍和使用

1.1 stack的介绍

stack的介绍文档

1. stack是一种容器适配器，专门用在具有LIFO(后进先出)操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。
2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类。
4. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。

---

1.2 stack的使用

1.2.1.1 stack对象的构造

stack();   构造空栈

---

1.2.1.2 stack对象的容量操作

1.2.1.2.1 empty()函数

bool empty() const;		判断是否为空

int main()
{
	stack<int> st;
	cout << st.empty() << endl;

	st.push(1);
	cout << st.empty() << endl;

	return 0;
}

---

1.2.1.2.2 size()函数

size_type size() const;      获取元素个数

int main()
{
	stack<int> st;
	cout << st.size() << endl;

	for (int i = 0; i < 10; i++)
	{
		st.push(i);
	}
	cout << st.size() << endl;

	return 0;
}

---

1.2.1.3 stack对象的增删查改及访问

1.2.1.3.1 push()函数

void push (const value_type& val);  	入栈

int main()
{
	stack<int> st;

	for (int i = 0; i < 10; i++)
	{
		st.push(i);
	}

	return 0;
}

---

1.2.1.3.2 pop()函数

void pop();	  出栈

---

1.2.1.3.3 top()函数

访问栈顶元素
	  value_type& top();
const value_type& top() const;

---

1.3 stack的模拟实现

1.3.1 stack中 push 和 pop 的实现

namespace aj
{
    template<class T, class Container = deque<T>>
    class stack
    {
    public:
        void push(const T& x)
        {
            _con.push_back(x);
        }

        void pop()
        {
            _con.pop_back();
        }

    private:
        Container _con;
    };
};

---

1.3.2 stack中 empty 、size 和 top 的实现

namespace aj
{
    template<class T, class Container = deque<T>>
    class stack
    {
    public:
        T& top()
        {
            return _con.back();
        }

        const T& top()const
        {
            return _con.back();
        }

        size_t size()const
        {
            return _con.size();
        }

        bool empty()const
        {
            return _con.empty();
        }

    private:
        Container _con;
    };
};

---

1.3.3 stack 实现汇总及函数测试

namespace aj
{
    template<class T, class Container = deque<T>>
    class stack
    {
    public:
        stack()
        {}

        void push(const T& x)
        {
            _con.push_back(x);
        }

        void pop()
        {
            _con.pop_back();
        }

        T& top()
        {
            return _con.back();
        }

        const T& top()const
        {
            return _con.back();
        }

        size_t size()const
        {
            return _con.size();
        }

        bool empty()const
        {
            return _con.empty();
        }

    private:
        Container _con;
    };
};

void test_Stack()
{
    aj::stack<int> st;

    st.push(1);
    st.push(2);
    st.push(4);
    st.push(6);
    st.push(9);
    st.push(0);

    while (!st.empty())
    {
        cout << "top:" << st.top() << "    ";
        cout << "size:" << st.size() << "    ";
        cout << "empty:" << st.empty() << endl;
        st.pop();
    }
}

---

二、queue的介绍和使用

2.1 queue的介绍

queue的介绍文档

1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。
2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。
4. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。

---

2.2 queue的使用

2.2.1 queue的构造函数

queue();	  构造空队列

int main()
{
	queue<int> q;

	return 0;
}

---

2.2.2 queue对象的容量操作

2.2.2.1 empty()函数

bool empty() const;	  判断是否为空

int main()
{
	queue<int> q;
	cout << q.empty() << endl;

	q.push(1);
	cout << q.empty() << endl;

	return 0;
}

---

2.2.2.2 size()函数

size_type size() const;	  获取元素个数

int main()
{
	queue<int> q;
	cout << q.size() << endl;

	for (int i = 0; i < 10; i++)
	{
		q.push(i);
	}
	cout << q.size() << endl;

	return 0;
}

---

2.2.3 queue对象的增删查改及访问

2.2.3.1 push()函数

void push (const value_type& val);	  入队列

int main()
{
	queue<int> q;

	for (int i = 0; i < 5; i++)
	{
		q.push(i);
	}

	return 0;
}

---

2.2.3.2 pop()函数

void pop();	  出队列

int main()
{
	queue<int> q;

	for (int i = 0; i < 5; i++)
	{
		q.push(i);
	}

	q.pop();
	q.pop();

	return 0;
}

---

2.2.3.3 front()函数

返回队头的元素
	  value_type& front();
const value_type& front() const;

int main()
{
	queue<int> q;

	for (int i = 0; i < 5; i++)
	{
		q.push(i);
	}

	while (!q.empty())
	{
		cout << q.front() << ' ';
		q.pop();
	}

	cout << endl;

	return 0;
}

---

2.2.3.4 back()函数

返回队尾的元素
	  value_type& back();
const value_type& back() const;

---

2.3 queue的模拟实现

2.3.1 queue中 push 和 pop 的实现

namespace aj
{
    template<class T, class Container = deque<T>>
    class queue
    {
    public:
        void push(const T& x)
        {
            _con.push_back(x);
        }

        void pop()
        {
            _con.pop_front();
        }
    private:
        Container _con;
    };
}

---

2.3.2 queue中 empty 和 size 的实现

namespace aj
{
    template<class T, class Container = deque<T>>
    class queue
    {
    public:
        size_t size()const
        {
            return _con.size();
        }

        bool empty()const
        {
            return _con.empty();
        }

    private:
        Container _con;
    };
}

---

2.3.3 queue中 front 和 back 的实现

namespace aj
{
    template<class T, class Container = deque<T>>
    class queue
    {
    public:
        T& back()
        {
            return _con.back();
        }

        const T& back()const
        {
            return _con.back();
        }

        T& front()
        {
            return _con.front();

        }

        const T& front()const
        {
            return _con.front();
        }

    private:
        Container _con;
    };
}

---

2.3.4 queue 实现汇总及函数测试

namespace aj
{
    template<class T, class Container = deque<T>>
    class queue
    {
    public:
        queue()
        {}

        void push(const T& x)
        {
            _con.push_back(x);
        }

        void pop()
        {
            _con.pop_front();
        }

        T& back()
        {
            return _con.back();
        }

        const T& back()const
        {
            return _con.back();
        }

        T& front()
        {
            return _con.front();

        }

        const T& front()const
        {
            return _con.front();
        }

        size_t size()const
        {
            return _con.size();
        }

        bool empty()const
        {
            return _con.empty();
        }

    private:
        Container _con;
    };
}

void test_Queue()
{
    aj::queue<int> qu;

    qu.push(1);
    qu.push(2);
    qu.push(4);
    qu.push(6);
    qu.push(9);
    qu.push(0);

    while (!qu.empty())
    {
        cout << "front:" << qu.front() << "    ";
        cout << "back:" << qu.back() << endl;

        qu.pop();
    }
}

---

三、priority_queue的介绍和使用

3.1 priority_queue的介绍

priority_queue的介绍文档

1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。
3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，priority_queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。
5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

---

3.2 priority_queue的使用

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆。

---

3.2.1 priority_queue的构造函数

构造一个空的优先级队列
priority_queue (const Compare& comp = Compare(),
                     const Container& ctnr = Container());
                     
构造并使用默认的比较函数和底层容器类型来初始化优先队列
template <class InputIterator>
         priority_queue (InputIterator first, InputIterator last,
                         const Compare& comp = Compare(),
                         const Container& ctnr = Container());

int main()
{
	priority_queue<int> pq;

	return 0;
}

int main()
{
	string s("Love");
	priority_queue<int> pq(s.begin(),s.end());

	return 0;
}

---

3.2.2 priority_queue对象的容量操作

3.2.2.1 empty()函数

bool empty() const;	  判断是否为空

int main()
{
	priority_queue<int> pq;
	cout << pq.empty() << endl;

	pq.push(1);
	cout << pq.empty() << endl;

	return 0;
}

---

3.2.2.2 size()函数

size_type size() const;	  获取元素个数

---

3.2.3 priority_queue对象的增删查改及访问

3.2.3.1 push()函数

void push (const value_type& val);	  
向优先级队列中插入一个元素val

int main()
{
	priority_queue<int> pq;

	for (int i = 0; i < 3; i++)
	{
		pq.push(i);
	}

	return 0;
}

---

3.2.3.2 pop()函数

void pop();	 
删除优先级队列中最大(最小)元素，即堆顶元素

---

3.2.3.3 top()函数

const value_type& top() const;
返回优先级队列中最大(最小)元素，即堆顶元素

int main()
{
	priority_queue<int> pq;

	for (int i = 0; i < 3; i++)
	{
		pq.push(i);
	}

	while (!pq.empty())
	{
		cout << pq.top() << ' ';
		pq.pop();
	}

	cout << endl;

	return 0;
}

---

3.3 priority_queue的模拟实现

3.3.1 priority_queue 中 向上调整函数 和 向下调整函数 的实现

namespace aj
{
    template<class T>
    class less
    {
    public:
        bool operator()(const T& x1, const T& x2)
        {
            return x1 < x2;
        }
    };

    template<class T>
    class greater
    {
    public:
        bool operator()(const T& x1, const T& x2)
        {
            return x1 > x2;
        }
    };

    template <class T, class Container = vector<T>, class Compare = less<T> >
    class priority_queue
    {
    public:
        void adjust_up(int child)
        {
            int parent = (child - 1) / 2;
            while (child > 0)
            {
                if (comp(c[parent] , c[child]))
                {
                    swap(c[child], c[parent]);
                    child = parent;
                    parent = (child - 1) / 2;
                }
                else
                {
                    break;
                }
            }
        }

        void adjust_down(int parent)
        {
            size_t child = parent * 2 + 1;
            while (child < c.size())
            {
                if (child + 1 < c.size() && comp(c[child] , c[child + 1]))
                {
                    child++;
                }

                // if (c[parent] < c[child])
                if (comp(c[parent] , c[child]))
                {
                    swap(c[child], c[parent]);
                    parent = child;
                    child = parent * 2 + 1;
                }
                else
                {
                    break;
                }
            }
        }

    private:
        Container c;
        Compare comp;
    };
};

---

3.3.2 priority_queue 中 无参构造函数 和 迭代器区间构造函数的实现

namespace aj
{ 
    template <class T, class Container = vector<T>, class Compare = less<T> >
    class priority_queue
    {
    public:
        priority_queue()
        {};

        template <class InputIterator>
        priority_queue(InputIterator first, InputIterator last)
            :c(first, last)
        {
            for (int i = (size() - 2) / 2; i > 0; --i)
            {
                adjust_up(i);
            }
        }

    private:
        Container c;
        Compare comp;
    };
};

---

3.3.3 priority_queue 中 push 和 pop 的实现

namespace aj
{
    template <class T, class Container = vector<T>, class Compare = less<T> >
    class priority_queue
    {
    public:

        void push(const T& x)
        {
            c.push_back(x);
            adjust_up(c.size() - 1);
        }

        void pop()
        {
            swap(c[0], c[c, size() - 1]);
            c.pop_back();
            adjust_down(0);
        }

    private:
        Container c;
        Compare comp;
    };
};

---

3.3.4 priority_queue 中 empty 、size 和 top 的实现

namespace aj
{
    template <class T, class Container = vector<T>, class Compare = less<T> >
    class priority_queue
    {
    public:
        bool empty() const
        {
            return c.empty();
        }

        size_t size() const
        {
            return c.size();
        }

        const T& top() const
        {
            return c[0];
        }

    private:
        Container c;
        Compare comp;
    };

};

---

3.3.5 priority_queue 实现汇总及函数测试

#pragma once

#include <iostream>
#include<vector>
#include<functional>

using namespace std;

namespace aj
{
    template<class T>
    class less
    {
    public:
        bool operator()(const T& x1, const T& x2)
        {
            return x1 < x2;
        }
    };

    template<class T>
    class greater
    {
    public:
        bool operator()(const T& x1, const T& x2)
        {
            return x1 > x2;
        }
    };

    template <class T, class Container = vector<T>, class Compare = less<T> >
    class priority_queue
    {
    public:
        priority_queue() 
        {};

        template <class InputIterator>
        priority_queue(InputIterator first, InputIterator last)
            :c(first,last)
        {
            for (int i = (size() - 2) / 2; i > 0; --i)
            {
                adjust_up(i);
            }
        }

        bool empty() const
        {
            return c.empty();
        }

        size_t size() const
        {
            return c.size();
        }

        const T& top() const
        {
            return c[0];
        }

        void adjust_up(int child)
        {
            int parent = (child - 1) / 2;
            while (child > 0)
            {
                if (comp(c[parent] , c[child]))
                {
                    swap(c[child], c[parent]);
                    child = parent;
                    parent = (child - 1) / 2;
                }
                else
                {
                    break;
                }
            }
        }

        void adjust_down(int parent)
        {
            size_t child = parent * 2 + 1;
            while (child < c.size())
            {
                if (child + 1 < c.size() && comp(c[child] , c[child + 1]))
                {
                    child++;
                }

                // if (c[parent] < c[child])
                if (comp(c[parent] , c[child]))
                {
                    swap(c[child], c[parent]);
                    parent = child;
                    child = parent * 2 + 1;
                }
                else
                {
                    break;
                }
            }
        }

        void push(const T& x)
        {
            c.push_back(x);
            adjust_up(c.size() - 1);
        }

        void pop()
        {
            swap(c[0], c[c, size() - 1]);
            c.pop_back();
            adjust_down(0);
        }

    private:
        Container c;
        Compare comp;
    };

    void test_priority_queue1()
    {
        priority_queue<int> pq;
        pq.push(1);
        pq.push(2);
        pq.push(3);
        pq.push(4);

        while (!pq.empty())
        {
            // cout << pq.size() << ' ';

            cout << pq.top() << ' ';
            pq.pop();
        }
    }

    void test_priority_queue2()
    {
        string s("I Love You");
        priority_queue<int> pq(s.begin(),s.end());

        while (!pq.empty())
        {
            // cout << pq.size() << ' ';

            cout << pq.top() << ' ';
            pq.pop();
        }
    }
};

---

四、容器适配器

4.1 什么是适配器

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。

---

4.2 STL标准库中stack和queue的底层结构

虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque，比如：

---

4.3 deque的简单介绍

4.3.1 deque的原理介绍

deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示：

那deque是如何借助其迭代器维护其假想连续的结构呢？

---

4.3.2 deque的缺陷

与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。
与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。
但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。

---

4.4 为什么选择deque作为stack和queue的底层默认容器

stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据结构，只要具有
push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list。但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为：

1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。

结合了deque的优点，而完美的避开了其缺陷

---

结尾

如果有什么建议和疑问，或是有什么错误，大家可以在评论区中提出。
希望大家以后也能和我一起进步！！🌹🌹
如果这篇文章对你有用的话，请大家给一个三连支持一下！！🌹🌹