C++基础（14）——stack和queue类的使用和模拟实现

西阳未落

8696人浏览 · 2025-09-16 09:48:15

西阳未落 · 2025-09-16 09:48:15 发布

一、stack

栈就是一个专门使用在后进先出（Last In First Out）场景的一个结构，如图所示：

stack的定义方式

第一种：我们可以使用默认的适配器来定义栈（deque）

stack<int> st;

第二种：我们也可以使用特定的适配器来定义栈

stack<int, vector<int>> st1;

stack<int, list<int>> st2;

stack的使用

我们给出了一个表格：

操作	`stack` 函数	功能描述
`push`	`push(value)`	向栈顶插入元素（栈的顶端）
`pop`	`pop()`	从栈顶移除元素（栈的顶端）
`top`	`top()`	获取栈顶元素
`empty`	`empty()`	判断栈是否为空
`size`	`size()`	返回栈的元素个数

举个栗子：

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

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

测试效果如图：

二、queue

队列就是一个和栈相反逻辑的结构，它是先进先出的（First In First Out），如图所示：

queue的定义方式

这个和stack差不多，也是有两种方式：

第一种：使用默认的适配器定义（deque）

queue<int> q;

第二种：使用特定的适配器定义

queue<int, vector<int>> q1;

queue<int, list<int>> q2;

queue的使用

操作	`queue` 函数	功能描述
`enqueue`	`push(value)`	向队列尾部插入元素
`dequeue`	`pop()`	从队列头部移除元素
`front`	`front()`	获取队列头部元素
`back`	`back()`	获取队列尾部元素
`empty`	`empty()`	判断队列是否为空
`size`	`size()`	返回队列中的元素个数

我们举个栗子：

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

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

测试效果如图：

三、模拟实现的相关概念

我们在实现stack和queue的时候要注意了，这两个结构虽然可以存放元素，但是我们的STL没有将这两个划分到容器的一栏中，而是将这两个称为容器适配器，我们这里的实现就是对其他容器的一个包装而已，我们STL里面的默认容器是deque（双端队列）。所以我们这里也是使用deque实现。

我们在c++的一个非官方网站上可以看到，实现这两个的类模板的声明中是有两个参数的，第一个就是我们存储的元素类型，而第二个就是我们指定的容器类型了：

所以我们接下来的实现就会非常的简单了。

四、stack的模拟实现

栈操作	`deque` 方法	说明
`push`	`push_back()`	向栈顶插入元素（`deque` 的后端）
`pop`	`pop_back()`	弹出栈顶元素（`deque` 的后端）
`top`	`back()`	获取栈顶元素（`deque` 的后端）
`empty`	`empty()`	检查栈是否为空（`deque` 的 `empty()`）
`size`	`size()`	获取栈的大小（`deque` 的 `size()`）

我们的实现如下：

namespace xywl {
    template<class T, class Container = std::deque<T>>
    class stack {
        public:
            // 入栈
            void push(const T& x) {
                _conn.push_back(x);
            }
            // 出栈
            void pop() {
                _conn.pop_back();
            }
            // 访问栈顶元素
            const T& top() const {
                return _conn.back();
            }
            // 获取栈的大小
            size_t size() const {
                return _conn.size();
            }
            // 判空
            bool empty() const {
                return _conn.empty();
            }
        private:
            Container _conn;
    };
}

五、queue的模拟实现

队列操作	`deque` 方法	说明
`enqueue`	`push_back(value)`	向队列的尾部插入元素
`dequeue`	`pop_front()`	从队列的头部删除元素
`front`	`front()`	获取队列头部的元素（队列的第一个元素）
`back`	`back()`	获取队列尾部的元素（队列的最后一个元素）
`empty`	`empty()`	检查队列是否为空
`size`	`size()`	获取队列的大小

我们的实现如下：

namespace xywl {
    template<class T, class Container = std::deque<T>>
    class queue {
        public:
            // 入队列
            void push(const T& x) {
                _conn.push_back(x);
            }
            // 出对列
            void pop() {
                _conn.pop_front();
            }
            // 访问队列的头
            const T& front() const {
                return _conn.front();
            }
            // 访问队列的尾
            const T& back() const {
                return _conn.back();
            }
            // 获取队列的大小
            size_t size() const {
                return _conn.size();
            }
            // 判空
            bool empty() const {
                return _conn.empty();
            }
        private:
            std::deque<T> _conn;
    };
}