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

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

代码语言：javascript

AI代码解释

#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和逻辑不一样的地方就在于，队首删除，队尾插入：

代码语言：javascript

AI代码解释

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. 测试

代码语言：javascript

AI代码解释

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;
}

运行结果：

（本篇完）