栈的基本概念与设计思想

栈(Stack)是一种后进先出(LIFO)的数据结构，它只允许在容器的一端进行插入和删除操作。在C++标准库中，std::stack是一个容器适配器，基于其他序列容器实现其功能。

栈的实现详解

1. 头文件与命名空间

cpp

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

namespace ym
{
    // 栈实现
}

• #pragma once：编译器指令，确保头文件只被包含一次

• 命名空间ym：防止与标准库命名冲突，提供封装性

• 包含deque：使用双端队列作为默认底层容器

2. 模板设计

cpp

template<class T, class Container = deque<T>>
class stack
{
    // 类实现
};

• 模板参数T：指定栈中元素的类型

• 模板参数Container：指定底层容器类型，默认为deque<T>

• 容器适配器模式：stack不是独立容器，而是基于其他容器的适配器

3. 核心接口实现

入栈操作(push)

cpp

void push(const T& x)
{
    con.push_back(x);
}

使用底层容器的push_back方法，在栈顶添加元素。

出栈操作(pop)

cpp

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

使用底层容器的pop_back方法，移除栈顶元素。

访问栈顶元素

cpp

T& top()
{
    return con.back();
}

const T& top() const
{
    return con.back();
}

提供两种版本的top()方法：

• 非常量版本：允许修改栈顶元素

• 常量版本：用于const对象，保证对象不被修改

容量查询

cpp

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

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

• size()：返回栈中元素数量

• empty()：判断栈是否为空

• 两个方法都使用const修饰符，保证不修改对象状态

4. 私有数据成员

cpp

private:
    Container con;

• 使用模板参数Container定义的底层容器

• 私有访问权限确保数据封装性

底层容器选择与比较

stack可以基于多种容器实现，每种容器有不同的特性：

1. 默认容器：deque（双端队列）

cpp

ym::stack<int> stack1; // 默认使用deque

• 优点：首尾操作高效(O(1))，内存动态增长

• 缺点：内存不连续，迭代器可能失效

2. 基于vector实现

cpp

ym::stack<int, vector<int>> stack2;

• 优点：内存连续，缓存友好

• 缺点：扩容时需要重新分配内存

3. 基于list实现

cpp

ym::stack<int, list<int>> stack3;

• 优点：不需要连续内存，插入删除高效

• 缺点：内存开销大，缓存不友好

使用示例

cpp

#include "stack.h"
#include <vector>
#include <list>

int main()
{
    // 使用默认deque容器
    ym::stack<int> s1;
    for (int i = 0; i < 5; ++i)
        s1.push(i);
    
    cout << "Stack size: " << s1.size() << endl;
    while (!s1.empty()) {
        cout << s1.top() << " ";
        s1.pop();
    }
    cout << endl;
    
    // 使用vector作为底层容器
    ym::stack<int, vector<int>> s2;
    
    // 使用list作为底层容器
    ym::stack<int, list<int>> s3;
    
    return 0;
}

输出结果：

text

Stack size: 5
4 3 2 1 0

设计模式分析

1. 容器适配器模式

stack是一个典型的容器适配器，它：

• 不自己管理内存，而是委托给底层容器

• 提供统一的接口，隐藏底层实现细节

• 可以通过更换底层容器来调整性能特性

2. 模板编程技巧

• 使用默认模板参数提供便利性

• 通过模板特化支持多种数据类型

• 利用SFINAE特性保证类型安全

3. 异常安全性

所有操作都依赖底层容器的实现，自然具有异常安全性：

• push操作：要么成功，要么保持栈不变

• pop操作：要么成功，要么保持栈不变

• top操作：不会修改栈状态，总是安全

与STL stack的对比

特性	本实现	STL stack
接口一致性	完全一致	标准接口
异常安全	依赖底层容器	强异常安全
可扩展性	可自定义容器	固定容器选择
性能特性	与底层容器相关	高度优化