用C++模块实现栈

栈这种数据结构是一个工具性的数据结构，通常被其它复杂数据结构所使用。比如实现二叉树的遍历的非递归算法。下面就用C++模板实现栈数据结构的一个较完整代码！在书本《数据结构（C语言版）--严慰明》提到栈可以用数组，也可以用链表实现，这里只用链表实现这一数据结构。

//Stack.h
//双链表栈数据结构C++模块的实现
//理论知识参考《数据结构（C语言版）--严慰明》
#ifndef _STACK_H_
#define _STACK_H_
#include <iostream>
using namespace std;
namespace _STACK_
{
 //栈中的元素
 template <typename T>
 class StackNode
 {
 public:
  StackNode()
  {
   this->mElement = 0;
   this->mpNext = NULL;
   this->mpPrev = NULL;
  }

  ~StackNode()
  {
   this->mElement = 0;
   this->mpNext = NULL;
   this->mpPrev = NULL;
  }

  T& getElement(void)
  {
   return mElement;
  }

  //重载"<<"操作符，以便对栈节点输出，注意以friend重载“<<”操作符要加上"<>"
  friend ostream& operator << <>(ostream& ost,StackNode<T>& src)
  {
   ost << src.mElement;
   return ost;
  }

 //protected:
  T mElement; //存放的数据
  StackNode<T>* mpNext; //指向后继节点指针
  StackNode<T>* mpPrev; //指向前驱节点指针
  template <typename T>
  friend class Stack;
 };

 template <typename T>
 class Stack
 {
 public:
  Stack();
  ~Stack();
  bool push(const T& element);
  T pop(void);
  bool isEmpty(void);
  bool clear(void);
  int size();
  friend ostream& operator<< <>(ostream& ost,Stack<T>& src);
 protected:
  StackNode<T>* createNode(const T& element);
 protected:
  StackNode<T>* mpHead;
  StackNode<T>* mpTop;
 };

 template <typename T>
 Stack<T>::Stack()
 {
  T i = T();
  //创建一个带有头节点的双链栈，这个节点不存入任何数据
  this->mpHead = this->createNode(i);
  this->mpTop = this->mpHead;
 }

 template <typename T>
 Stack<T>::~Stack()
 {
  this->clear();
  delete this->mpHead;
  this->mpHead = NULL;
  this->mpTop = NULL;
 }

 template <typename T>
 StackNode<T>* Stack<T>::createNode(const T& element)
 {
  StackNode<T>* pNode = new StackNode<T>;
  if (pNode)
  {
   pNode->mElement = element;
   pNode->mpNext = NULL;
   pNode->mpPrev = NULL;
  }
  return pNode;
 }

 template <typename T>
 bool Stack<T>::push(const T& element)
 {
  StackNode<T>* pNode = createNode(element);
  if(this->mpHead->mpNext == NULL)
  {
   this->mpHead->mpNext = pNode;
   pNode->mpPrev = this->mpHead;
  }
  else
  {
   this->mpTop->mpNext = pNode;
   pNode->mpPrev = this->mpTop;
  }
  this->mpTop = pNode;
  return true;
 }

 template <typename T>
 T Stack<T>::pop(void)
 {
  if (this->mpTop != this->mpHead)
  {
   StackNode<T>* pNode = this->mpTop;
   this->mpTop = this->mpTop->mpPrev;
   T elem = pNode->mElement;
   pNode ->mpNext = pNode->mpPrev = NULL;
   delete pNode;
   pNode = NULL;
   return elem;
  }
  return (T)0;
 }

 template <typename T>
 bool Stack<T>::isEmpty(void)
 {
  return (this->mpHead == this->mpTop);
 }

 template <typename T>
 bool Stack<T>::clear(void)
 {
  StackNode<T>* pNode = this->mpTop;
  while((pNode = this->mpTop) != this->mpHead)
  {
   this->mpTop =pNode->mpPrev;
   pNode->mpNext = NULL;
   pNode->mpPrev = NULL;
   delete pNode;
   pNode = NULL;
  }
  return true;
 }

 template <typename T>
 int Stack<T>::size()
 {
  int iCount = 0;
  StackNode<T>* pNode = this->mpTop;
  while(pNode != this->mpHead)
  {
   iCount++;
   pNode = pNode->mpPrev;
  }
  return iCount;
 }

 template <typename T>
 ostream& operator<< <>(ostream& ost,Stack<T>& src)
 {
  StackNode<T>* pNode = src.mpTop;
  while( src.mpHead)
  {
   ost << *pNode << " ";
   pNode = pNode->mpPrev;
  }
  return ost;
 }
}
#endif

以上就是栈数据结构的实现。