【C++庖丁解牛】stack的介绍和使用 | queue的介绍和使用 | priority

目录

• 1. stack的介绍和使用
• • 1.1 stack的介绍
  • 1.2 stack的存储结构
  • 1.3 stack的特点
  • 1.4. stack的使用
  • 2. queue的介绍和使用
  • • 2.1 queue的介绍
    • 2.2 queue的存储结构
    • 2.3 queue的特点
    • 2.4 queue的使用
    • 3. priority_queue的介绍和使用
    • • 3.1 priority_queue的介绍
      • 3.2 priority_queue的存储结构
      • 3.3 priority_queue的特点
      • 3.4 priority_queue的使用

        ---

        1. stack的介绍和使用

        1.1 stack的介绍

        1. stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。
        2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
        3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：

        empty：判空操作

        back：获取尾部元素操作

        push_back：尾部插入元素操作

        pop_back：尾部删除元素操作

        1. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。

        1.2 stack的存储结构

        stack（栈）是一种先进后出（First In Last Out）的数据结构，只有一个入口和出口，那就是栈顶，除了获取栈顶元素外，没有其他方法可以获取到内部的其他元素，其结构图如下：

        

        stack这种单向开口的数据结构很容易由双向开口的deque和list形成，只需要根据stack的性质对应移除某些接口即可实现，stack的源码如下：

        template 
        class stack
        {
        	...
        protected:
            Sequence c;
        public:
            bool empty(){return c.empty();}
            size_type size() const{return c.size();}
            reference top() const {return c.back();}
            const_reference top() const{return c.back();}
            void push(const value_type& x){c.push_back(x);}
            void pop(){c.pop_back();}
        };
        

        从stack的数据结构可以看出，其所有操作都是围绕Sequence完成，而Sequence默认是deque数据结构。stack这种“修改某种接口，形成另一种风貌”的行为，成为adapter(配接器)。常将其归类为container adapter而非container

        stack除了默认使用deque作为其底层容器之外，也可以使用双向开口的list，只需要在初始化stack时，将list作为第二个参数即可。由于stack只能操作顶端的元素，因此其内部元素无法被访问，也不提供迭代器。

        1.3 stack的特点

        stack是一种常见的容器，它遵循后进先出（LIFO）的原则。以下是stack容器的特点：

        1. 元素的插入和删除只能在容器的顶部进行，即只能在栈顶进行push和pop操作。
        2. stack容器没有迭代器，因此不能通过迭代器访问容器中的元素。
        3. stack容器的大小可以动态增长，不需要事先指定容器的大小。
        4. 可以使用top()函数来获取栈顶元素的值，但不会删除该元素。
        5. 可以使用empty()函数来判断栈是否为空。
        6. 可以使用size()函数来获取栈中元素的个数。

        1.4. stack的使用

        函数说明	接口说明
        stack()	构造空的栈
        empty()	检测stack是否为空
        size()	返回stack中元素的个数
        top()	返回栈顶元素的引用
        push()	将元素val压入stack中
        pop()	将stack中尾部的元素弹出

        下面是一个示例代码，演示了如何使用这些成员函数：

        #include 
        #include 
        using namespace std;
        int main() {
            stack myStack;
            // 使用push()添加元素到stack
            myStack.push(10);
            myStack.push(20);
            myStack.push(30);
            // 使用top()获取stack顶部的元素
            cout 
                cout 
                cout 
        	...
        protected:
            Sequence c;
        public:
            bool empty(){return c.empty();}
            size_type size() const{return c.size();}
            reference front() const {return c.front();}
            const_reference front() const{return c.front();}
            void push(const value_type& x){c.push_back(x);}
            void pop(){c.pop_front();}
        };
        
            queue
                cout 
        	...
        protected:
            Sequence c; // 底层容器
            Compare comp; // 元素大小比较标准
        public:
            bool empty() const {return c.empty();}
            size_type size() const {return c.size();}
            const_reference top() const {return c.front()}
            void push(const value_type& x)
            {
                c.push_heap(x);
                push_heap(c.begin(), c.end(),comp);
            }
            void pop()
            {
                pop_heap(c.begin(), c.end(),comp);
                c.pop_back();
            }
        };
        
        	int ia[9] = {0,4,1,2,3,6,5,8,7 };
        	priority_queue
        		cout 
        		cout 
        	// 默认情况下，创建的是大堆，其底层按照小于号比较
        	vector3,2,7,6,0,4,1,9,8,5};
        	priority_queue
        public:
        	Date(int year = 1900, int month = 1, int day = 1)
        		: _year(year)
        		, _month(month)
        		, _day(day)
        	{}
        	bool operator
        		return (_year