首页 > 代码库 > C++采用模板实现栈的方法
C++采用模板实现栈的方法
今天又看了遍《effective C++》,手动实现了一下条款42中的栈，贴出来当博客的处女贴。
首先栈的声明如下，采用了模板传入类型，而栈的底层采用是个链表。
// stack.h// by Chwen 2014-10-27 #include<stdio.h>#include <stdlib.h>#include <iostream>using namespace std;// 栈声明template<typename T>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<typename T>Stack<T>::Stack() :top(nullptr),mySize(0){}template<typename T>Stack<T>::~Stack(){ clear();}template<typename T>void Stack<T>::push(const T& node){ top = new StackNode(node,top); mySize ++;}template<typename T>T Stack<T>::Top(){ if (Empty()) { _DEBUG_ERROR("Error, stack is empty!"); } return top->data;}template<typename T>void Stack<T>::pop(){ if (Empty()) { _DEBUG_ERROR("Error, stack is empty!"); } StackNode* topOfStack = top; top = top->next; delete topOfStack; topOfStack = nullptr; mySize --; return;}template<typename T>bool Stack<T>::Empty() const{ return top == nullptr;}template<typename T>void Stack<T>::clear(){ while (top) { StackNode* topOfStack = top; top = top->next; delete topOfStack; } mySize = 0;}template<typename T>int Stack<T>::size()const{ return mySize;}
以上即是采用模板实现的栈的所有代码，可以实现栈的push, pop, top, clear 等操作。
以下写了一个简单的测试代码：
void funv(){ Stack<int> 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<stdio.h>#include <stdlib.h>#include <iostream>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 <typename T>class Stack:private commonStack{public: void push(T * ty){commonStack::push(static_cast<void*>(ty));} T* top(){return static_cast<T*>(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<int> 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<string> 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<int> 即默认使用deque作为栈底层容器。
用户也可以指定其他方式，比如std::stack<int, std::list<int> >, 这样就使用了list作为栈的底层容器。
让我感到awesome的是STL实现的精巧和灵活性，居然是可指定底层的一种实现方法，太精巧了。回头再去看一下《STL源码剖析》。
只罗列了代码，没太详细的介绍原理，感兴趣的可以直接去看《effective C++》和《STL源码剖析》，以及STL的stack代码。
引用请注明出处，http://www.cnblogs.com/chwen/p/4055474.html 非常感谢，随时交流。
C++采用模板实现栈的方法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。