【C++】STL--从零实现stack栈和queue队列的所有关键操作

小陈又菜

发布于 2025-12-24 10:57:49

120

个人主页：小陈又菜的主页 个人追求：做一个有梦想的程序员！ 个人准则：想多了都是问题，做多了都是答案！

1. Stack

1.1. stack的介绍 stack官方文档

stack是一个容器适配器，在专门具有后进先出的上下文环境中，只能从容器的一端进行操作
stack作为一个容器适配器，它封装了一个STL标准容器（又叫做底层容器），但是针对后进先出的，stack只暴露特定的操作，隐藏了容器的其他非必要功能
stack封装的底层容器可以是任何标准容器（list、vector、deque）。要求容器必须具有一下操作：
- empty() 判空操作
- back() 获取末尾元素
- push_back() 尾插
- pop_back() 尾删
如果并没有指定底层容器，就默认是deque

1.2. stack的使用及其模拟实现

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

1.2.1. stack()

因为我们是将stack写成一个自定义类型，所以构造函数、析构函数都不需要我们自己写，编译器会自动调用。

1.2.2. 其他接口

stack是以deque为底层容器的容器适配器的一个对象，所以stack的相关接口都可以使用底层容器的，换句话说stack封装了deque。

所以服用deque来实现stack的接口的话就比较简单了：

#include <iostream>
#include <deque>
using namespace std;
namespace stk
{
	//stack
	template<class T, class Container = deque<T>>
	class stack
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_back();
		}
		const T& top()
		{
			return _con.back();
		}

		size_t size()
		{
			return _con.size();
		}
		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};

2. queue

2.1. queue的介绍 queue官方文档

队列是一种容器适配器，专门用于先进先出的上下问环境中，其中从元素一端插入插入元素，另一端提取元素
与stack一样，queue也是一个封装了底层容器的容器适配器的一个对象
底层容器可以是标准类容器模版之一，该底层容器应该包含下面操作：
- empty：检测队列是否为空
- size：返回队列中有效元素的个数
- front：返回队头元素的引用
- back：返回队尾元素的引用
- push_back：在队列尾部入队列
- pop_front：在队列头部出队列
默认情况下，如果没有指定底层容器，则会使用标准容器deque

2.2. queue使用及其模拟实现

函数声明	接口说明
queue()	构造空的队列
empty()	检测队列是否为空，是返回 true ，否则返回 false
size()	返回队列中有效元素的个数
front()	返回队头元素的引用
back()	返回队尾元素的引用
push()	在队尾将元素 val 入队列
pop()	将队头元素出队列

2.2.1. queue()

与stack一样，会自动调用析构函数和构造函数：

2.2.2. 其他接口

queue与stack和逻辑不一样的地方就在于，队首删除，队尾插入：

namespace stk
{
	//stack
	template<class T, class Container = deque<T>>
	class stack
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_back();
		}
		const T& top()
		{
			return _con.back();
		}

		size_t size()
		{
			return _con.size();
		}
		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};

	template<class T, class Container = deque<T>>
	class queue
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_front();
		}
		const T& front()
		{
			return _con.front();
		}
		const T& back()
		{
			return _con.back();
		}

		size_t size()
		{
			return _con.size();
		}
		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};
}

3. 测试

using namespace stk;
using namespace std;

void test_stack() {
    cout << "============ Testing Stack ============" << endl;

    // 测试默认容器（deque）
    stack<int> s1;
    cout << "Stack with default container (deque):" << endl;

    // 测试push和size
    s1.push(10);
    s1.push(20);
    s1.push(30);
    cout << "Size after pushing 3 elements: " << s1.size() << endl;
    cout << "Top element: " << s1.top() << endl;

    // 测试pop
    s1.pop();
    cout << "Top after pop: " << s1.top() << endl;
    cout << "Size after pop: " << s1.size() << endl;

    // 测试empty
    cout << "Is empty? " << (s1.empty() ? "Yes" : "No") << endl;

    // 清空栈
    s1.pop();
    s1.pop();
    cout << "Is empty after popping all? " << (s1.empty() ? "Yes" : "No") << endl;
    cout << endl;

    // 测试vector作为底层容器
    stack<int, vector<int>> s2;
    cout << "Stack with vector container:" << endl;
    s2.push(100);
    s2.push(200);
    cout << "Top: " << s2.top() << endl;
    cout << "Size: " << s2.size() << endl;
    cout << endl;
}

void test_queue() {
    cout << "============ Testing Queue ============" << endl;

    // 测试默认容器（deque）
    queue<int> q1;
    cout << "Queue with default container (deque):" << endl;

    // 测试push
    q1.push(10);
    q1.push(20);
    q1.push(30);
    cout << "Size after pushing 3 elements: " << q1.size() << endl;
    cout << "Front element: " << q1.front() << endl;
    cout << "Back element: " << q1.back() << endl;

    // 测试pop
    q1.pop();
    cout << "Front after pop: " << q1.front() << endl;
    cout << "Back after pop: " << q1.back() << endl;
    cout << "Size after pop: " << q1.size() << endl;

    // 测试empty
    cout << "Is empty? " << (q1.empty() ? "Yes" : "No") << endl;

    // 清空队列
    q1.pop();
    q1.pop();
    cout << "Is empty after popping all? " << (q1.empty() ? "Yes" : "No") << endl;
    cout << endl;

    // 测试list作为底层容器
    queue<int, list<int>> q2;
    cout << "Queue with list container:" << endl;
    q2.push(100);
    q2.push(200);
    q2.push(300);
    cout << "Front: " << q2.front() << endl;
    cout << "Back: " << q2.back() << endl;
    cout << "Size: " << q2.size() << endl;
    cout << endl;
}

void test_edge_cases() {
    cout << "============ Testing Edge Cases ============" << endl;

    // 测试空栈/队列的操作
    stack<int> s;
    queue<int> q;

    cout << "Empty stack size: " << s.size() << endl;
    cout << "Empty queue size: " << q.size() << endl;
    cout << "Is stack empty? " << (s.empty() ? "Yes" : "No") << endl;
    cout << "Is queue empty? " << (q.empty() ? "Yes" : "No") << endl;
    cout << endl;

    // 测试字符串类型
    stack<string> str_stack;
    str_stack.push("Hello");
    str_stack.push("World");
    cout << "String stack top: " << str_stack.top() << endl;

    queue<string> str_queue;
    str_queue.push("First");
    str_queue.push("Second");
    cout << "String queue front: " << str_queue.front() << endl;
    cout << "String queue back: " << str_queue.back() << endl;
}

int main() {
    cout << "Testing STK Container Adapters Implementation" << endl;
    cout << "=============================================" << endl << endl;

    test_stack();
    test_queue();
    test_edge_cases();

    cout << "============ All Tests Completed ============" << endl;
    return 0;
}

运行结果：