[C++知识库]【C++】第七章:STL之stack&&queue的模拟实现

stack&&queue的使用

stack的定义

方式一： 使用默认的适配器定义栈。

stack<int> stk;

方式二： 使用特定的适配器定义栈。

stack<int, vector<int>> stk;
stack<int, list<int>> stk;

注意：如果没有指定适配器，默认使用deque。

stack的使用

#include <iostream>
#include <stack>
using namespace std;

int main()
{
	stack<int> st;
	st.push(1);
	st.push(2);
	st.push(3);
	st.push(4);
	cout << st.size() << endl; //4
	while (!st.empty())
	{
		cout << st.top() << " ";
		st.pop();
	}
	cout << endl; //4 3 2 1
	return 0;
}

queue的定义

方式一： 使用默认的适配器定义队列。

queue<int> q;

方式二： 使用特定的适配器定义队列。

queue<int, vector<int>> q;
queue<int, list<int>> q;

注意：如果没有指定适配器，默认使用deque。

queue的使用

#include <iostream>
#include <queue>
using namespace std;

int main()
{
	queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);
	cout << q.size() << endl; // 4
	while (!q.empty())
	{
		cout << q.front() << " ";
		q.pop();
	}
	cout << endl; //1 2 3 4
	return 0;
}

stack&&queue的模拟实现

stack和queue都叫做容器的适配器，简单的来说就是，这个容器就是另一个容器的一个子集。通过封装了一个功能比较强大的容器，并只体现出这个封装容器的部分功能，从而得到了另一个容器，这就出现了容器的适配器。

如果没有指定适配器，stack和queue的底层默认使用deque作为封装的容器。

#include <iostream>
#include <deque>
using namespace std;

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

        }

        void push(const T& val) {
            _container.push_back(val);
        }

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

        T& top() {
            return _container.back();
        }
        // 注意这里必须要这个接口
        // 因为const对象返回的top()是不可以被修改的
        const T& top() const {
            return _container.back();
        }

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


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

    private:
        Container _container;
    };


}


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

        void push(const T& val) {
            _container.push_back(val);
        }

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

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

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

        T& front() {
            return _container.front();
        }

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

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

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

    private:
        Container _container;      
    };

    void test() {
        queue<int> q;
        q.push(1);
        q.push(2);
        while (!q.empty()) {
            cout << q.front();
            q.pop();
        }
    }
}