本文主要向大家介绍了 C/C++知识点之C++采用模板实现栈的方法，通过具体的内容向大家展示，希望对大家学习C/C++知识点有所帮助。

今天又看了遍《effective C++》,手动实现了一下条款42中的栈，贴出来当博客的处女贴。

首先栈的声明如下，采用了模板传入类型，而栈的底层采用是个链表。

// stack.h
// by Chwen 2014-10-27 

#include
#include 
#include 

using namespace std;

// 栈声明

template
class Stack
{
public:
    Stack();
    ~Stack();

    void push(const T& node);
    T Top();
    void pop();
    int size()const;
    bool Empty() const;
    void clear();

private:
    struct StackNode
    {
        T data;
        StackNode* next;
        StackNode(const T& Newdata, StackNode* nextNode)
            :data(Newdata),next(nextNode)
        {}
    };
　　 
    StackNode * top;
    // 防止默认拷贝和默认赋值
    Stack(const Stack& rhs);
    Stack& operator=(const Stack& rhs);
    int mySize;
};

 
　　而对应的cpp实现如下：

// stack.cpp
 
#include "stack.h"
using namespace std;

// 栈实现

template
Stack::Stack()
    :top(nullptr),mySize(0)
{

}

template
Stack::~Stack()
{
    clear();
}

template
void Stack::push(const T& node)
{
    top = new StackNode(node,top);
    mySize ++;
}

template
T Stack::Top()
{
    if (Empty())
    {
        _DEBUG_ERROR("Error, stack is empty!");
    }
    return top->data;
}

template
void Stack::pop()
{
    if (Empty())
    {
        _DEBUG_ERROR("Error, stack is empty!");
    }
    StackNode* topOfStack = top;
    top = top->next;
    delete topOfStack;
    topOfStack = nullptr;
    mySize --;
    return;
}

template
bool Stack::Empty() const
{
    return top == nullptr;
}

template
void Stack::clear()
{
    while (top)
    {
        StackNode* topOfStack = top;
        top = top->next;
        delete topOfStack;

    }
    mySize = 0;
}
template
int Stack::size()const
{
    return mySize;
}

以上即是采用模板实现的栈的所有代码，可以实现栈的push,  pop, top, clear 等操作。
以下写了一个简单的测试代码：

void funv()
{
 
    Stack s;

    for(int i = 0; i < 10; ++i)
    {
        s.push(i);
    }
    for(int j = s.size()-1 ; j >= 0; --j)
    {
        cout<< "node: " << s.Top() <<endl;
        s.pop();
    }

    s.clear();

}
int main (){　　funv(); 　　getchar(); 　　return 0;}

 
之后effective C++指出了另一种更精巧的方式实现，即私有继承。
代码实现如下：

// stack.h
// by Chwen 2014-10-27 
#include
#include 
#include 

class commonStack
{
protected:
    commonStack();
    ~commonStack();

    void push(void* node);
    void* Top();
    void pop();
    int size()const;
    bool Empty() const;
    void clear();

    
private:
    struct StackNode
    {
        void* data;
        StackNode* next;
        StackNode(void* Newdata, StackNode* nextNode)
            :data(Newdata),next(nextNode)
        {}
    };

    StackNode * top;
    // 防止默认拷贝和默认赋值
    commonStack(const commonStack& rhs);
    commonStack& operator=(const commonStack& rhs);
    int mySize;
};

template 
class Stack:private commonStack
{
public:
    void push(T * ty){commonStack::push(static_cast(ty));}
    T* top(){return static_cast(commonStack::Top());}
    void pop(){return commonStack::pop();}
    int size(){return commonStack::size();}
    bool Empty()const{ return commonStack::Empty(); }
    void clear(){return commonStack::clear();}
 

};

 
对应的cpp 如下：
 

 
#include "stack.h"
 
using namespace std;

commonStack::commonStack()
    :top(nullptr),mySize(0)
{

}

 
commonStack::~commonStack()
{
    clear();
}

 
void commonStack::push(void* node)
{
    top = new StackNode(node,top);
    mySize ++;
}

 
void* commonStack::Top()
{
    if (Empty())
    {
        _DEBUG_ERROR("Error, stack is empty!");
    }
    return top->data;
}

 
void commonStack::pop()
{
    if (Empty())
    {
        _DEBUG_ERROR("Error, stack is empty!");
    }
    StackNode* topOfStack = top;
    top = top->next;
    delete topOfStack;
    topOfStack = nullptr;
    mySize --;
    return;
}

 
bool  commonStack::Empty() const
{
    return top == nullptr;
}
 
void commonStack::clear()
{
    while (top)
    {
        StackNode* topOfStack = top;
        top = top->next;
        delete topOfStack;

    }
    mySize = 0;
}
 
int commonStack::size()const
{
    return mySize;
}

这里commonStack将原模板类的T改为了void*, 之后使用protected保护该类不会被其他不明群众调用，而是给出了一个模板接口类私有继承这个类，这样一来，既起到了保护作用，又在低损耗的情况下给出了方便易用的接口，巧夺天工的设计。
测试代码如下：

void funcInt()
{
    int* a[10];
    for(int i = 0 ; i < 10; ++i)
    {
        a[i] = new int(i);
    }

    Stack s;
    
    for(int j = 0 ; j < 10; ++j)
    {
        s.push(a[j]);
    }

    int k = s.size();
    int* t = s.top();
    s.pop();
    if(s.Empty())
    {
        cout<<"empty"<<endl;
    }
    s.clear();
    
    for(int i = 0 ; i < 10; ++i)
    {
        delete a[i] ;
    }

}

void funcString()
{
    string* str[10];
    for(int i = 0 ; i < 10; ++i)
    {
        str[i] = new string("a");
    }

    Stack s;

    for(int j = 0 ; j < 10; ++j)
    {
        s.push(str[j]);
    }

    int k = s.size();
    string* t = s.top();
    s.pop();
    if(s.Empty())
    {
        cout<<"empty"<<endl;
    }
    s.clear();

    for(int i = 0 ; i < 10; ++i)
    {
        delete str[i] ;
    }
}

int main ()
{
    funcInt();
    funcString();
    getchar();
    return 0;
}

测试代码没有输出，可以断点看数据。
 
之后我又去看了一眼STL对栈的实现，它默认使用deque作为栈的底层实现。

template<class _Ty,
class _Container = deque<_ty> >

class stack
{
// 栈实现
}

调用的时候直接std::stack 即默认使用deque作为栈底层容器。
用户也可以指定其他方式，比如std::stack<int, std::list >, 这样就使用了list作为栈的底层容器。
让我感到awesome的是STL实现的精巧和灵活性，居然是可指定底层的一种实现方法，太精巧了。

本文由职坐标整理并发布，希望对同学们有所帮助。了解更多详情请关注职坐标编程语言C/C+频道！