"《算法导论》之‘栈’"：栈的三种实现（静态数组、动态数组及指针）

　　本文有关栈的介绍部分参考自网站数据结构。

　 1. 栈

　  1.1 栈的定义

　　栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。
　　（1）通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。
　　（2）当表中没有元素时称为空栈。
　　（3）栈为后进先出（Last In First Out）的线性表，简称为LIFO表。
    　栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中"最新"的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。
      

　　【示例】元素是以a₁，a₂，…，a_n的顺序进栈，退栈的次序却是a_n，a_n-1，…，a₁。

　  1.2 栈的运算

　　（1）initStack（S）
    　构造一个空栈S。
　　（2）isEmpty（S）
    　判栈空。若S为空栈，则返回TRUE，否则返回FALSE。
　　（3）isFull（S）
    　判栈满。若S为满栈，则返回TRUE，否则返回FALSE。
　　 注意：
　    该运算只适用于栈的顺序存储结构。
　　（4）push（S，x）
    　进栈。若栈S不满，则将元素x插入S的栈顶。
　　（5）pop（S）
    　退栈。若栈S非空，则将S的栈顶元素删去，并返回该元素。
　　（6）top（S）
    　取栈顶元素。若栈S非空，则返回栈顶元素，但不改变栈的状态。

　 2. 栈的三种实现

　　我在实现的时候，栈的基本函数都有（isEmpty、push、pop、top）。因为我是用面向对象的方法来设计栈，所以栈的初始化、拷贝构造、赋值运算符重载等也都具备。另外，我采取了C++中的模板类来设计栈，使得该栈设计能适应更多的场合。

　  2.1 基于静态数组

　　基于静态数组的栈的最大特点就是栈的大小是固定的，用户在初始化之后就无法改变。在编译期，编译器就已经给这个栈分配好内存，在“内存的栈”上分配。

　　这是我所设计的栈模板类：

 template<class T, int defCapacity = >
 class Stack
 {
 public:
     Stack();
     virtual ~Stack();
     bool isEmpty();
     bool push(T val);   // 进栈。若栈不满，则将元素插入栈顶。
     T top();            // 取栈顶元素。若栈S非空，则返回栈顶元素，但不改变栈的状态。
     bool pop();         // 退栈。若栈非空，则将栈顶元素删去，并返回是否退栈成功的标志。
                         // 这里没有采用返回被删栈顶元素的原因在于这里写的是一个模板，
                         // 当栈为空的时候不方便返回。当然，这个问题是可以通过断言或
                         // 抛异常来解决的。具体做法可根据具体情况来定。
     int getSizeOfStack();

 private:
     T stack[defCapacity];
     int sizeOfStack;

 };

　　具体实现代码为：

 #include <iostream>
 #include <cassert>
 using namespace std;

 // const int CAPACITY = 1024;

 template<class T, int defCapacity = >
 class Stack
 {
 public:
     Stack();
     virtual ~Stack();
     bool isEmpty();
     bool push(T val);    // 进栈。若栈不满，则将元素插入栈顶。
     T top();            // 取栈顶元素。若栈S非空，则返回栈顶元素，但不改变栈的状态。
     bool pop();            // 退栈。若栈非空，则将栈顶元素删去，并返回是否退栈成功的标志。
                         // 这里没有采用返回被删栈顶元素的原因在于这里写的是一个模板，
                         // 当栈为空的时候不方便返回。当然，这个问题是可以通过断言或
                         // 抛异常来解决的。具体做法可根据具体情况来定。
     int getSizeOfStack();

 private:
     T stack[defCapacity];
     int sizeOfStack;

 };

 template<class T, int defCapacity>
 Stack<T, defCapacity>::Stack()
 {
     sizeOfStack = ;
 }

 template<class T, int defCapacity>
 Stack<T, defCapacity>::~Stack()
 {

 }

 template<class T, int defCapacity>
 bool Stack<T, defCapacity>::isEmpty()
 {
     return sizeOfStack == ;
 }

 template<class T, int defCapacity>
 bool Stack<T, defCapacity>::push(T val)
 {
     // assert(sizeOfStack < defCapacity);
     bool isSuccess = true;
     if (sizeOfStack == defCapacity)
     {
         cerr << "There is no space for new elements." << endl;
         isSuccess = false;
     }
     else
     {
         stack[sizeOfStack] = val;
         sizeOfStack++;
     }
     return isSuccess;
 }

 template<class T, int defCapacity>
 T Stack<T, defCapacity>::top()
 {
     return stack[sizeOfStack - ];
 }

 template<class T, int defCapacity>
 bool Stack<T, defCapacity>::pop()
 {
     // assert(sizeOfStack > 0);
     bool isSuccess = true;
     if (sizeOfStack == )
     {
         cerr << "There is no element in stack." << endl;
         isSuccess = false;
     }
     else
     {
         sizeOfStack--;
     }
     return isSuccess;
 }

 template<class T, int defCapacity>
 int Stack<T, defCapacity>::getSizeOfStack()
 {
     return sizeOfStack;
 }

stack.hpp

　　Boost单元测试代码为：

 #define BOOST_TEST_MODULE Stack_Test_Module

 #include "stdafx.h"
 #include "../Stack/stack.hpp"

 const int MAXSIZE = ;
 struct Stack_Fixture
 {
 public:
     Stack_Fixture()
     {
         testStack = new Stack<int, MAXSIZE>();
     }

     ~Stack_Fixture()
     {
         delete testStack;
     }

     Stack<int, MAXSIZE> * testStack;
 };

 BOOST_FIXTURE_TEST_SUITE(Stack_Test_Fixture, Stack_Fixture)

 BOOST_AUTO_TEST_CASE( Stack_Test )
 {
     // isEmpty ------------------------------------
     BOOST_REQUIRE(testStack->isEmpty() == true);

     // isEmpty ------------------------------------
     BOOST_REQUIRE(testStack->getSizeOfStack() == );

     // push & top ---------------------------------
     BOOST_REQUIRE(testStack->push() == true);
     BOOST_REQUIRE(testStack->top() == );
     BOOST_REQUIRE(testStack->getSizeOfStack() == );

     BOOST_REQUIRE(testStack->push() == true);
     BOOST_REQUIRE(testStack->top() == );
     BOOST_REQUIRE(testStack->getSizeOfStack() == );

     BOOST_REQUIRE(testStack->push() == true);
     BOOST_REQUIRE(testStack->top() == );
     BOOST_REQUIRE(testStack->getSizeOfStack() == );

     BOOST_REQUIRE(testStack->push() == false);
     BOOST_REQUIRE(testStack->top() == );
     BOOST_REQUIRE(testStack->getSizeOfStack() == );

     // pop & top ----------------------------------
     BOOST_REQUIRE(testStack->pop() == true);
     BOOST_REQUIRE(testStack->top() == );
     BOOST_REQUIRE(testStack->getSizeOfStack() == );

     BOOST_REQUIRE(testStack->pop() == true);
     BOOST_REQUIRE(testStack->top() == );
     BOOST_REQUIRE(testStack->getSizeOfStack() == );

     BOOST_REQUIRE(testStack->pop() == true);
     BOOST_REQUIRE(testStack->getSizeOfStack() == );

     BOOST_REQUIRE(testStack->pop() == false);

 }

 BOOST_AUTO_TEST_SUITE_END()

BoostUnitTest.cpp

　  2.2 基于动态数组

　　基于动态数组的栈的特点是栈的大小是可以运行时改变的，即可以通过重新分配栈来实现栈的扩容与压缩。还有，跟基于静态数组的栈不一样的是，基于动态数组的栈是在程序运行时才分配（堆上分配）。

　　栈模板类：

 template<class T, int defCapacity>
 class Stack
 {
 public:
     Stack();
     virtual ~Stack();
     Stack(const Stack& orig);    // 拷贝构造函数
     Stack& operator=(const Stack& orig);    // 赋值运算符重载
     bool isEmpty();
     bool push(T val);       // 进栈。若栈不满，则将元素插入栈顶。
     T top();                // 取栈顶元素。若栈S非空，则返回栈顶元素，但不改变栈的状态。
     bool pop();             // 退栈。若栈非空，则将栈顶元素删去，并返回是否退栈成功的标志。
                             // 这里没有采用返回被删栈顶元素的原因在于这里写的是一个模板，
                             // 当栈为空的时候不方便返回。当然，这个问题是可以通过断言或
                             // 抛异常来解决的。具体做法可根据具体情况来定。
     int getSizeOfStack();

 private:
     T * stack;
     int capacity;
     int sizeOfStack;

 };

　　具体实现代码为：

 #include <iostream>
 #include <cassert>
 using namespace std;

 template<class T, int defCapacity>
 class Stack
 {
 public:
     Stack();
     virtual ~Stack();
     Stack(const Stack& orig);    // 拷贝构造函数
     Stack& operator=(const Stack& orig);    // 赋值运算符重载
     bool isEmpty();
     bool push(T val);        // 进栈。若栈不满，则将元素插入栈顶。
     T top();                // 取栈顶元素。若栈S非空，则返回栈顶元素，但不改变栈的状态。
     bool pop();                // 退栈。若栈非空，则将栈顶元素删去，并返回是否退栈成功的标志。
                             // 这里没有采用返回被删栈顶元素的原因在于这里写的是一个模板，
                             // 当栈为空的时候不方便返回。当然，这个问题是可以通过断言或
                             // 抛异常来解决的。具体做法可根据具体情况来定。
     int getSizeOfStack();

 private:
     T * stack;
     int capacity;
     int sizeOfStack;

 };

 template<class T, int defCapacity>
 Stack<T, defCapacity>::Stack()
 {
     capacity = defCapacity;
     //assert(capacity > 0);
     stack = new T[capacity];
     //assert(stack != NULL);
     sizeOfStack = ;
 }

 template<class T, int defCapacity>
 Stack<T, defCapacity>::~Stack()
 {
     delete[] stack;
 }

 template<class T, int defCapacity>
 Stack<T, defCapacity>::Stack(const Stack& orig)
 {
     capacity = defCapacity;    // 需要特别注意的是，调用拷贝构造函数时并不会“提前”调用构造函数
     //assert(capacity > 0);
     if (capacity < orig.capacity)
     {
         capacity = orig.capacity;
     }
     sizeOfStack = orig.sizeOfStack;
     stack = new T[capacity];
     //assert(stack != NULL);
     for (int i = ; i < sizeOfStack; i++)
     {
         stack[i] = orig.stack[i];
     }
 }

 template<class T, int defCapacity>
 Stack<T, defCapacity>& Stack<T, defCapacity>::operator=(const Stack& orig)    // 这里需要非常注意返回值要写为
                                                                             // Stack<T, defCapacity>而不是Stack
 {
     if (capacity < orig.capacity)
     {
         capacity = orig.capacity;
         stack = new T[capacity];
         //assert(stack != NULL);
     }

     sizeOfStack = orig.sizeOfStack;
     for (int i = ; i < sizeOfStack; i++)
     {
         stack[i] = orig.stack[i];
     }

     return *this;
 }

 template<class T, int defCapacity>
 bool Stack<T, defCapacity>::isEmpty()
 {
     return sizeOfStack == ;
 }

 template<class T, int defCapacity>
 bool Stack<T, defCapacity>::push(T val)
 {
     // assert(sizeOfStack < defCapacity);
     bool isSuccess = true;
     if (sizeOfStack == capacity)
     {
         cerr << "There is no space for new elements." << endl;
         isSuccess = false;
     }
     else
     {
         stack[sizeOfStack] = val;
         sizeOfStack++;
     }
     return isSuccess;
 }

 template<class T, int defCapacity>
 T Stack<T, defCapacity>::top()
 {
     return stack[sizeOfStack - ];
 }

 template<class T, int defCapacity>
 bool Stack<T, defCapacity>::pop()
 {
     // assert(sizeOfStack > 0);
     bool isSuccess = true;
     if (sizeOfStack == )
     {
         cerr << "There is no element in stack." << endl;
         isSuccess = false;
     }
     else
     {
         sizeOfStack--;
     }
     return isSuccess;
 }

 template<class T, int defCapacity>
 int Stack<T, defCapacity>::getSizeOfStack()
 {
     return sizeOfStack;
 }

stack.hpp

　　Boost单元测试代码为：

 #define BOOST_TEST_MODULE Stack_Test_Module

 #include "stdafx.h"
 #include "../Stack/stack.hpp"

 const int MAXSIZE = ;
 struct Stack_Fixture
 {
 public:
     Stack_Fixture()
     {
         testStack = new Stack<int, MAXSIZE>();
     }
     ~Stack_Fixture()
     {
         delete testStack;
     }
     Stack<int, MAXSIZE> * testStack;
 };

 BOOST_FIXTURE_TEST_SUITE(Stack_Test_Fixture, Stack_Fixture)

 BOOST_AUTO_TEST_CASE(Stack_Test)
 {
     // isEmpty ------------------------------------
     BOOST_REQUIRE(testStack->isEmpty() == true);

     // isEmpty ------------------------------------
     BOOST_REQUIRE(testStack->getSizeOfStack() == );

     // push & top ---------------------------------
     BOOST_REQUIRE(testStack->push() == true);
     BOOST_REQUIRE(testStack->top() == );
     BOOST_REQUIRE(testStack->getSizeOfStack() == );

     BOOST_REQUIRE(testStack->push() == true);
     BOOST_REQUIRE(testStack->top() == );
     BOOST_REQUIRE(testStack->getSizeOfStack() == );

     BOOST_REQUIRE(testStack->push() == true);
     BOOST_REQUIRE(testStack->top() == );
     BOOST_REQUIRE(testStack->getSizeOfStack() == );

     BOOST_REQUIRE(testStack->push() == false);
     BOOST_REQUIRE(testStack->top() == );
     BOOST_REQUIRE(testStack->getSizeOfStack() == );

     // pop & top ----------------------------------
     BOOST_REQUIRE(testStack->pop() == true);
     BOOST_REQUIRE(testStack->top() == );
     BOOST_REQUIRE(testStack->getSizeOfStack() == );

     BOOST_REQUIRE(testStack->pop() == true);
     BOOST_REQUIRE(testStack->top() == );
     BOOST_REQUIRE(testStack->getSizeOfStack() == );

     BOOST_REQUIRE(testStack->pop() == true);
     BOOST_REQUIRE(testStack->getSizeOfStack() == );

     BOOST_REQUIRE(testStack->pop() == false);
 }

 BOOST_AUTO_TEST_CASE(Stack_CopyConstructor_Test)
 {
     // initialize ---------------------------------
     BOOST_REQUIRE(testStack->push() == true);
     BOOST_REQUIRE(testStack->push() == true);
     BOOST_REQUIRE(testStack->push() == true);

     Stack<int, MAXSIZE> * testStack2 = new Stack<int, MAXSIZE>(*testStack);

     BOOST_REQUIRE(testStack2->getSizeOfStack() == );
     BOOST_REQUIRE(testStack2->top() == );

     BOOST_REQUIRE(testStack2->pop() == true);
     BOOST_REQUIRE(testStack2->top() == );
     BOOST_REQUIRE(testStack2->getSizeOfStack() == );

     BOOST_REQUIRE(testStack2->pop() == true);
     BOOST_REQUIRE(testStack2->top() == );
     BOOST_REQUIRE(testStack2->getSizeOfStack() == );

     BOOST_REQUIRE(testStack2->pop() == true);
     BOOST_REQUIRE(testStack2->getSizeOfStack() == );

     BOOST_REQUIRE(testStack2->pop() == false);
 }

 BOOST_AUTO_TEST_CASE(Stack_EqualOperator_Test)
 {
     // initialize ---------------------------------
     BOOST_REQUIRE(testStack->push() == true);
     BOOST_REQUIRE(testStack->push() == true);
     BOOST_REQUIRE(testStack->push() == true);

     Stack<int, MAXSIZE> * testStack2 = new Stack<int, MAXSIZE>();
     *testStack2 = *testStack;

     BOOST_REQUIRE(testStack2->getSizeOfStack() == );
     BOOST_REQUIRE(testStack2->top() == );

     BOOST_REQUIRE(testStack2->pop() == true);
     BOOST_REQUIRE(testStack2->top() == );
     BOOST_REQUIRE(testStack2->getSizeOfStack() == );

     BOOST_REQUIRE(testStack2->pop() == true);
     BOOST_REQUIRE(testStack2->top() == );
     BOOST_REQUIRE(testStack2->getSizeOfStack() == );

     BOOST_REQUIRE(testStack2->pop() == true);
     BOOST_REQUIRE(testStack2->getSizeOfStack() == );

     BOOST_REQUIRE(testStack2->pop() == false);
 }

 BOOST_AUTO_TEST_SUITE_END()

BoostUnitTest.cpp

　  2.3 基于指针

　　基于指针的栈也是在程序运行时才动态分配内存的。不过，它跟前两者不一样的是，它的内存利用效率高，不会存在内存浪费的问题。当然，这也就需要额外更多的内存申请及释放操作。

　　栈模板类：

 template<class T>
 class Node
 {
 public:
     T data;
     Node * next;
 };

 template<class T>
 class Stack
 {
 public:
     typedef Node<T> * NodePointer;

 public:
     Stack();
     virtual ~Stack();
     Stack(const Stack& orig);    // 拷贝构造函数
     Stack& operator=(const Stack& orig);    // 赋值运算符重载
     bool isEmpty();
     bool push(T val);       // 进栈。若栈不满，则将元素插入栈顶。
     T top();                // 取栈顶元素。若栈S非空，则返回栈顶元素，但不改变栈的状态。
     bool pop();             // 退栈。若栈非空，则将栈顶元素删去，并返回是否退栈成功的标志。
                             // 这里没有采用返回被删栈顶元素的原因在于这里写的是一个模板，
                             // 当栈为空的时候不方便返回。当然，这个问题是可以通过断言或
                             // 抛异常来解决的。具体做法可根据具体情况来定。
     int getSizeOfStack();

 private:
     NodePointer stack;

 };

　　具体实现代码为：

 #include <iostream>
 #include <cassert>
 using namespace std;

 template<class T>
 class Node
 {
 public:
     T data;
     Node * next;
 };

 template<class T>
 class Stack
 {
 public:
     typedef Node<T> * NodePointer;

 public:
     Stack();
     virtual ~Stack();
     Stack(const Stack& orig);    // 拷贝构造函数
     Stack& operator=(const Stack& orig);    // 赋值运算符重载
     bool isEmpty();
     bool push(T val);        // 进栈。若栈不满，则将元素插入栈顶。
     T top();                // 取栈顶元素。若栈S非空，则返回栈顶元素，但不改变栈的状态。
     bool pop();                // 退栈。若栈非空，则将栈顶元素删去，并返回是否退栈成功的标志。
                             // 这里没有采用返回被删栈顶元素的原因在于这里写的是一个模板，
                             // 当栈为空的时候不方便返回。当然，这个问题是可以通过断言或
                             // 抛异常来解决的。具体做法可根据具体情况来定。
     int getSizeOfStack();

 private:
     NodePointer stack;

 };

 template<class T>
 Stack<T>::Stack()
 {
     stack = NULL;
 }

 template<class T>
 Stack<T>::~Stack()
 {
     NodePointer ptr = stack, tmpPtr;
     while (ptr != NULL)
     {
         tmpPtr = ptr;
         ptr = ptr->next;
         delete tmpPtr;
     }
 }

 template<class T>
 Stack<T>::Stack(const Stack& orig)
 {
     stack = NULL;    // 需要特别注意的是，调用拷贝构造函数时并不会“提前”调用构造函数
     NodePointer tmpPtr = orig.stack;
     while (tmpPtr != NULL)
     {
         push(tmpPtr->data);
         tmpPtr = tmpPtr->next;
     }
 }

 template<class T>
 Stack<T>& Stack<T>::operator=(const Stack& orig)    // 这里需要非常注意返回值要写为
                                                     // Stack<T>而不是Stack
 {
     //stack = NULL; 在这里可以不用，因为调用“赋值运算符”前会提前调用构造函数
     NodePointer tmpPtr = orig.stack;
     while (tmpPtr != NULL)
     {
         push(tmpPtr->data);
         tmpPtr = tmpPtr->next;
     }

     return *this;
 }

 template<class T>
 bool Stack<T>::isEmpty()
 {
     return stack == NULL;
 }

 template<class T>
 bool Stack<T>::push(T val)
 {
     bool isSuccess = true;
     NodePointer ptr = new Node<T>(), tmpPtr;
     //assert(ptr != NULL);
     //isSuccess = false;
     ptr->data = val;
     if (stack == NULL)    // when the stack is empty
     {
         stack = ptr;
         ptr->next = NULL;
     }
     else               // others
     {
         tmpPtr = stack;
         int len = getSizeOfStack();
         int count = ;
         while (tmpPtr != NULL && count < len - )
         {
             tmpPtr = tmpPtr->next;
             count++;
         }
         tmpPtr->next = ptr;
         ptr->next = NULL;
     }

     return isSuccess;
 }

 template<class T>
 T Stack<T>::top()
 {
     NodePointer tmpPtr = stack;
     int len = getSizeOfStack();
     int count = ;
     while (tmpPtr != NULL && count < len - )
     {
         tmpPtr = tmpPtr->next;
         count++;
     }

     return tmpPtr->data;
 }

 template<class T>
 bool Stack<T>::pop()
 {
     bool isSuccess = true;
     int len = getSizeOfStack();
     if (len == )
     {
         cerr << "There is no element in stack." << endl;
         isSuccess = false;
     }
     else
     {
         NodePointer tmpPtr = stack, tmpPtr2;
         if (len == )
         {
             delete tmpPtr;
             stack = NULL;
         }
         else
         {
             int count = ;
             while (tmpPtr != NULL && count < len - )
             {
                 tmpPtr = tmpPtr->next;
                 count++;
             }
             tmpPtr2 = tmpPtr->next;
             tmpPtr->next = NULL;
             delete tmpPtr2;
         }
     }

     return isSuccess;
 }

 template<class T>
 int Stack<T>::getSizeOfStack()
 {
     int len = ;
     NodePointer ptr = stack;
     while (ptr != NULL)
     {
         len++;
         ptr = ptr->next;
     }
     return len;
 }

stack.hpp

　　Boost单元测试代码为：

 #define BOOST_TEST_MODULE Stack_Test_Module

 #include "stdafx.h"
 #include "../Stack/stack.hpp"

 struct Stack_Fixture
 {
 public:
     Stack_Fixture()
     {
         testStack = new Stack<int>();
     }
     ~Stack_Fixture()
     {
         delete testStack;
     }
     Stack<int> * testStack;
 };

 BOOST_FIXTURE_TEST_SUITE(Stack_Test_Fixture, Stack_Fixture)

 BOOST_AUTO_TEST_CASE(Stack_Test)
 {
     // isEmpty ------------------------------------
     BOOST_REQUIRE(testStack->isEmpty() == true);

     // isEmpty ------------------------------------
     BOOST_REQUIRE(testStack->getSizeOfStack() == );

     // push & top ---------------------------------
     BOOST_REQUIRE(testStack->push() == true);
     BOOST_REQUIRE(testStack->top() == );
     BOOST_REQUIRE(testStack->getSizeOfStack() == );

     BOOST_REQUIRE(testStack->push() == true);
     BOOST_REQUIRE(testStack->top() == );
     BOOST_REQUIRE(testStack->getSizeOfStack() == );

     BOOST_REQUIRE(testStack->push() == true);
     BOOST_REQUIRE(testStack->top() == );
     BOOST_REQUIRE(testStack->getSizeOfStack() == );

     // pop & top ----------------------------------
     BOOST_REQUIRE(testStack->pop() == true);
     BOOST_REQUIRE(testStack->top() == );
     BOOST_REQUIRE(testStack->getSizeOfStack() == );

     BOOST_REQUIRE(testStack->pop() == true);
     BOOST_REQUIRE(testStack->top() == );
     BOOST_REQUIRE(testStack->getSizeOfStack() == );

     BOOST_REQUIRE(testStack->pop() == true);
     BOOST_REQUIRE(testStack->getSizeOfStack() == );

     BOOST_REQUIRE(testStack->pop() == false);
 }

 BOOST_AUTO_TEST_CASE(Stack_CopyConstructor_Test)
 {
     // initialize ---------------------------------
     BOOST_REQUIRE(testStack->push() == true);
     BOOST_REQUIRE(testStack->push() == true);
     BOOST_REQUIRE(testStack->push() == true);

     Stack<int> * testStack2 = new Stack<int>(*testStack);

     BOOST_REQUIRE(testStack2->getSizeOfStack() == );
     BOOST_REQUIRE(testStack2->top() == );

     BOOST_REQUIRE(testStack2->pop() == true);
     BOOST_REQUIRE(testStack2->top() == );
     BOOST_REQUIRE(testStack2->getSizeOfStack() == );

     BOOST_REQUIRE(testStack2->pop() == true);
     BOOST_REQUIRE(testStack2->top() == );
     BOOST_REQUIRE(testStack2->getSizeOfStack() == );

     BOOST_REQUIRE(testStack2->pop() == true);
     BOOST_REQUIRE(testStack2->getSizeOfStack() == );

     BOOST_REQUIRE(testStack2->pop() == false);
 }

 BOOST_AUTO_TEST_CASE(Stack_EqualOperator_Test)
 {
     // initialize ---------------------------------
     BOOST_REQUIRE(testStack->push() == true);
     BOOST_REQUIRE(testStack->push() == true);
     BOOST_REQUIRE(testStack->push() == true);

     Stack<int> * testStack2 = new Stack<int>();
     *testStack2 = *testStack;

     BOOST_REQUIRE(testStack2->getSizeOfStack() == );
     BOOST_REQUIRE(testStack2->top() == );

     BOOST_REQUIRE(testStack2->pop() == true);
     BOOST_REQUIRE(testStack2->top() == );
     BOOST_REQUIRE(testStack2->getSizeOfStack() == );

     BOOST_REQUIRE(testStack2->pop() == true);
     BOOST_REQUIRE(testStack2->top() == );
     BOOST_REQUIRE(testStack2->getSizeOfStack() == );

     BOOST_REQUIRE(testStack2->pop() == true);
     BOOST_REQUIRE(testStack2->getSizeOfStack() == );

     BOOST_REQUIRE(testStack2->pop() == false);
 }

 BOOST_AUTO_TEST_SUITE_END()

BoostUnitTest.cpp

　　本篇博文的代码均托管到Taocode : http://code.taobao.org/p/datastructureandalgorithm/src/.