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

时间：2021-08-30 09:07:33

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

　 1. 栈

　  1.1 栈的定义

　　栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。
　　（1）通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。
　　（2）当表中没有元素时称为空栈。
　　（3）栈为后进先出（Last In First Out）的线性表，简称为LIFO表。
    　栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中"最新"的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。
      "《算法导论》之‘栈’"：栈的三种实现（静态数组、动态数组及指针）

　　【示例】元素是以a1，a2，…，an的顺序进栈，退栈的次序却是an，an-1，…，a1。

　  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/.

相关文章