首页 > 代码库 > 栈的三种实现（静态数组、动态数组及指针）
栈的三种实现（静态数组、动态数组及指针）
本文有关栈的介绍部分参考自网站数据结构。
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 基于静态数组
基于静态数组的栈的最大特点就是栈的大小是固定的，用户在初始化之后就无法改变。在编译期，编译器就已经给这个栈分配好内存，在“内存的栈”上分配。
这是我所设计的栈模板类：
1 template<class T, int defCapacity = 1024> 2 class Stack 3 { 4 public: 5 Stack(); 6 virtual ~Stack(); 7 bool isEmpty(); 8 bool push(T val); // 进栈。若栈不满，则将元素插入栈顶。 9 T top(); // 取栈顶元素。若栈S非空，则返回栈顶元素，但不改变栈的状态。10 bool pop(); // 退栈。若栈非空，则将栈顶元素删去，并返回是否退栈成功的标志。11 // 这里没有采用返回被删栈顶元素的原因在于这里写的是一个模板，12 // 当栈为空的时候不方便返回。当然，这个问题是可以通过断言或13 // 抛异常来解决的。具体做法可根据具体情况来定。14 int getSizeOfStack();15 16 private:17 T stack[defCapacity];18 int sizeOfStack;19 20 };
具体实现代码为：
1 #include <iostream> 2 #include <cassert> 3 using namespace std; 4 5 // const int CAPACITY = 1024; 6 7 template<class T, int defCapacity = 1024> 8 class Stack 9 {10 public:11 Stack();12 virtual ~Stack();13 bool isEmpty();14 bool push(T val); // 进栈。若栈不满，则将元素插入栈顶。15 T top(); // 取栈顶元素。若栈S非空，则返回栈顶元素，但不改变栈的状态。16 bool pop(); // 退栈。若栈非空，则将栈顶元素删去，并返回是否退栈成功的标志。17 // 这里没有采用返回被删栈顶元素的原因在于这里写的是一个模板，18 // 当栈为空的时候不方便返回。当然，这个问题是可以通过断言或19 // 抛异常来解决的。具体做法可根据具体情况来定。20 int getSizeOfStack();21 22 private:23 T stack[defCapacity];24 int sizeOfStack;25 26 };27 28 29 template<class T, int defCapacity>30 Stack<T, defCapacity>::Stack()31 {32 sizeOfStack = 0;33 }34 35 template<class T, int defCapacity>36 Stack<T, defCapacity>::~Stack()37 {38 39 }40 41 template<class T, int defCapacity>42 bool Stack<T, defCapacity>::isEmpty()43 {44 return sizeOfStack == 0;45 }46 47 template<class T, int defCapacity>48 bool Stack<T, defCapacity>::push(T val)49 {50 // assert(sizeOfStack < defCapacity);51 bool isSuccess = true;52 if (sizeOfStack == defCapacity)53 {54 cerr << "There is no space for new elements." << endl;55 isSuccess = false;56 }57 else58 {59 stack[sizeOfStack] = val;60 sizeOfStack++;61 }62 return isSuccess;63 }64 65 template<class T, int defCapacity>66 T Stack<T, defCapacity>::top()67 {68 return stack[sizeOfStack - 1];69 }70 71 template<class T, int defCapacity>72 bool Stack<T, defCapacity>::pop()73 {74 // assert(sizeOfStack > 0);75 bool isSuccess = true;76 if (sizeOfStack == 0)77 {78 cerr << "There is no element in stack." << endl;79 isSuccess = false;80 }81 else82 {83 sizeOfStack--;84 }85 return isSuccess;86 }87 88 template<class T, int defCapacity>89 int Stack<T, defCapacity>::getSizeOfStack()90 {91 return sizeOfStack;92 }
Boost单元测试代码为：
1 #define BOOST_TEST_MODULE Stack_Test_Module 2 3 #include "stdafx.h" 4 #include "../Stack/stack.hpp" 5 6 const int MAXSIZE = 3; 7 struct Stack_Fixture 8 { 9 public:10 Stack_Fixture()11 {12 testStack = new Stack<int, MAXSIZE>();13 }14 15 ~Stack_Fixture()16 {17 delete testStack;18 }19 20 Stack<int, MAXSIZE> * testStack;21 };22 23 24 25 BOOST_FIXTURE_TEST_SUITE(Stack_Test_Fixture, Stack_Fixture)26 27 BOOST_AUTO_TEST_CASE( Stack_Test ) 28 {29 // isEmpty ------------------------------------30 BOOST_REQUIRE(testStack->isEmpty() == true);31 32 // isEmpty ------------------------------------33 BOOST_REQUIRE(testStack->getSizeOfStack() == 0);34 35 // push & top ---------------------------------36 BOOST_REQUIRE(testStack->push(1) == true);37 BOOST_REQUIRE(testStack->top() == 1);38 BOOST_REQUIRE(testStack->getSizeOfStack() == 1);39 40 BOOST_REQUIRE(testStack->push(2) == true);41 BOOST_REQUIRE(testStack->top() == 2);42 BOOST_REQUIRE(testStack->getSizeOfStack() == 2);43 44 BOOST_REQUIRE(testStack->push(3) == true);45 BOOST_REQUIRE(testStack->top() == 3);46 BOOST_REQUIRE(testStack->getSizeOfStack() == 3);47 48 BOOST_REQUIRE(testStack->push(3) == false);49 BOOST_REQUIRE(testStack->top() == 3);50 BOOST_REQUIRE(testStack->getSizeOfStack() == 3);51 52 // pop & top ----------------------------------53 BOOST_REQUIRE(testStack->pop() == true);54 BOOST_REQUIRE(testStack->top() == 2);55 BOOST_REQUIRE(testStack->getSizeOfStack() == 2);56 57 BOOST_REQUIRE(testStack->pop() == true);58 BOOST_REQUIRE(testStack->top() == 1);59 BOOST_REQUIRE(testStack->getSizeOfStack() == 1);60 61 BOOST_REQUIRE(testStack->pop() == true);62 BOOST_REQUIRE(testStack->getSizeOfStack() == 0);63 64 BOOST_REQUIRE(testStack->pop() == false);65 66 }67 68 69 BOOST_AUTO_TEST_SUITE_END()
2.2 基于动态数组
基于动态数组的栈的特点是栈的大小是可以运行时改变的，即可以通过重新分配栈来实现栈的扩容与压缩。还有，跟基于静态数组的栈不一样的是，基于动态数组的栈是在程序运行时才分配（堆上分配）。
栈模板类：
1 template<class T, int defCapacity> 2 class Stack 3 { 4 public: 5 Stack(); 6 virtual ~Stack(); 7 Stack(const Stack& orig); // 拷贝构造函数 8 Stack& operator=(const Stack& orig); // 赋值运算符重载 9 bool isEmpty();10 bool push(T val); // 进栈。若栈不满，则将元素插入栈顶。11 T top(); // 取栈顶元素。若栈S非空，则返回栈顶元素，但不改变栈的状态。12 bool pop(); // 退栈。若栈非空，则将栈顶元素删去，并返回是否退栈成功的标志。13 // 这里没有采用返回被删栈顶元素的原因在于这里写的是一个模板，14 // 当栈为空的时候不方便返回。当然，这个问题是可以通过断言或15 // 抛异常来解决的。具体做法可根据具体情况来定。16 int getSizeOfStack();17 18 private:19 T * stack;20 int capacity;21 int sizeOfStack;22 23 };
具体实现代码为：
1 #include <iostream> 2 #include <cassert> 3 using namespace std; 4 5 template<class T, int defCapacity> 6 class Stack 7 { 8 public: 9 Stack(); 10 virtual ~Stack(); 11 Stack(const Stack& orig); // 拷贝构造函数 12 Stack& operator=(const Stack& orig); // 赋值运算符重载 13 bool isEmpty(); 14 bool push(T val); // 进栈。若栈不满，则将元素插入栈顶。 15 T top(); // 取栈顶元素。若栈S非空，则返回栈顶元素，但不改变栈的状态。 16 bool pop(); // 退栈。若栈非空，则将栈顶元素删去，并返回是否退栈成功的标志。 17 // 这里没有采用返回被删栈顶元素的原因在于这里写的是一个模板， 18 // 当栈为空的时候不方便返回。当然，这个问题是可以通过断言或 19 // 抛异常来解决的。具体做法可根据具体情况来定。 20 int getSizeOfStack(); 21 22 private: 23 T * stack; 24 int capacity; 25 int sizeOfStack; 26 27 }; 28 29 template<class T, int defCapacity> 30 Stack<T, defCapacity>::Stack() 31 { 32 capacity = defCapacity; 33 //assert(capacity > 0); 34 stack = new T[capacity]; 35 //assert(stack != NULL); 36 sizeOfStack = 0; 37 } 38 39 template<class T, int defCapacity> 40 Stack<T, defCapacity>::~Stack() 41 { 42 delete[] stack; 43 } 44 45 template<class T, int defCapacity> 46 Stack<T, defCapacity>::Stack(const Stack& orig) 47 { 48 capacity = defCapacity; // 需要特别注意的是，调用拷贝构造函数时并不会“提前”调用构造函数 49 //assert(capacity > 0); 50 if (capacity < orig.capacity) 51 { 52 capacity = orig.capacity; 53 } 54 sizeOfStack = orig.sizeOfStack; 55 stack = new T[capacity]; 56 //assert(stack != NULL); 57 for (int i = 0; i < sizeOfStack; i++) 58 { 59 stack[i] = orig.stack[i]; 60 } 61 } 62 63 template<class T, int defCapacity> 64 Stack<T, defCapacity>& Stack<T, defCapacity>::operator=(const Stack& orig) // 这里需要非常注意返回值要写为 65 // Stack<T, defCapacity>而不是Stack 66 { 67 if (capacity < orig.capacity) 68 { 69 capacity = orig.capacity; 70 stack = new T[capacity]; 71 //assert(stack != NULL); 72 } 73 74 sizeOfStack = orig.sizeOfStack; 75 for (int i = 0; i < sizeOfStack; i++) 76 { 77 stack[i] = orig.stack[i]; 78 } 79 80 return *this; 81 } 82 83 template<class T, int defCapacity> 84 bool Stack<T, defCapacity>::isEmpty() 85 { 86 return sizeOfStack == 0; 87 } 88 89 template<class T, int defCapacity> 90 bool Stack<T, defCapacity>::push(T val) 91 { 92 // assert(sizeOfStack < defCapacity); 93 bool isSuccess = true; 94 if (sizeOfStack == capacity) 95 { 96 cerr << "There is no space for new elements." << endl; 97 isSuccess = false; 98 } 99 else100 {101 stack[sizeOfStack] = val;102 sizeOfStack++;103 }104 return isSuccess;105 }106 107 template<class T, int defCapacity>108 T Stack<T, defCapacity>::top()109 {110 return stack[sizeOfStack - 1];111 }112 113 template<class T, int defCapacity>114 bool Stack<T, defCapacity>::pop()115 {116 // assert(sizeOfStack > 0);117 bool isSuccess = true;118 if (sizeOfStack == 0)119 {120 cerr << "There is no element in stack." << endl;121 isSuccess = false;122 }123 else124 {125 sizeOfStack--;126 }127 return isSuccess;128 }129 130 template<class T, int defCapacity>131 int Stack<T, defCapacity>::getSizeOfStack()132 {133 return sizeOfStack;134 }
Boost单元测试代码为：
1 #define BOOST_TEST_MODULE Stack_Test_Module 2 3 #include "stdafx.h" 4 #include "../Stack/stack.hpp" 5 6 const int MAXSIZE = 3; 7 struct Stack_Fixture 8 { 9 public: 10 Stack_Fixture() 11 { 12 testStack = new Stack<int, MAXSIZE>(); 13 } 14 ~Stack_Fixture() 15 { 16 delete testStack; 17 } 18 Stack<int, MAXSIZE> * testStack; 19 }; 20 21 BOOST_FIXTURE_TEST_SUITE(Stack_Test_Fixture, Stack_Fixture) 22 23 BOOST_AUTO_TEST_CASE(Stack_Test) 24 { 25 // isEmpty ------------------------------------ 26 BOOST_REQUIRE(testStack->isEmpty() == true); 27 28 // isEmpty ------------------------------------ 29 BOOST_REQUIRE(testStack->getSizeOfStack() == 0); 30 31 // push & top --------------------------------- 32 BOOST_REQUIRE(testStack->push(1) == true); 33 BOOST_REQUIRE(testStack->top() == 1); 34 BOOST_REQUIRE(testStack->getSizeOfStack() == 1); 35 36 BOOST_REQUIRE(testStack->push(2) == true); 37 BOOST_REQUIRE(testStack->top() == 2); 38 BOOST_REQUIRE(testStack->getSizeOfStack() == 2); 39 40 BOOST_REQUIRE(testStack->push(3) == true); 41 BOOST_REQUIRE(testStack->top() == 3); 42 BOOST_REQUIRE(testStack->getSizeOfStack() == 3); 43 44 BOOST_REQUIRE(testStack->push(3) == false); 45 BOOST_REQUIRE(testStack->top() == 3); 46 BOOST_REQUIRE(testStack->getSizeOfStack() == 3); 47 48 // pop & top ---------------------------------- 49 BOOST_REQUIRE(testStack->pop() == true); 50 BOOST_REQUIRE(testStack->top() == 2); 51 BOOST_REQUIRE(testStack->getSizeOfStack() == 2); 52 53 BOOST_REQUIRE(testStack->pop() == true); 54 BOOST_REQUIRE(testStack->top() == 1); 55 BOOST_REQUIRE(testStack->getSizeOfStack() == 1); 56 57 BOOST_REQUIRE(testStack->pop() == true); 58 BOOST_REQUIRE(testStack->getSizeOfStack() == 0); 59 60 BOOST_REQUIRE(testStack->pop() == false); 61 } 62 63 BOOST_AUTO_TEST_CASE(Stack_CopyConstructor_Test) 64 { 65 // initialize --------------------------------- 66 BOOST_REQUIRE(testStack->push(1) == true); 67 BOOST_REQUIRE(testStack->push(2) == true); 68 BOOST_REQUIRE(testStack->push(3) == true); 69 70 Stack<int, MAXSIZE> * testStack2 = new Stack<int, MAXSIZE>(*testStack); 71 72 BOOST_REQUIRE(testStack2->getSizeOfStack() == 3); 73 BOOST_REQUIRE(testStack2->top() == 3); 74 75 BOOST_REQUIRE(testStack2->pop() == true); 76 BOOST_REQUIRE(testStack2->top() == 2); 77 BOOST_REQUIRE(testStack2->getSizeOfStack() == 2); 78 79 BOOST_REQUIRE(testStack2->pop() == true); 80 BOOST_REQUIRE(testStack2->top() == 1); 81 BOOST_REQUIRE(testStack2->getSizeOfStack() == 1); 82 83 BOOST_REQUIRE(testStack2->pop() == true); 84 BOOST_REQUIRE(testStack2->getSizeOfStack() == 0); 85 86 BOOST_REQUIRE(testStack2->pop() == false); 87 } 88 89 BOOST_AUTO_TEST_CASE(Stack_EqualOperator_Test) 90 { 91 // initialize --------------------------------- 92 BOOST_REQUIRE(testStack->push(1) == true); 93 BOOST_REQUIRE(testStack->push(2) == true); 94 BOOST_REQUIRE(testStack->push(3) == true); 95 96 Stack<int, MAXSIZE> * testStack2 = new Stack<int, MAXSIZE>(); 97 *testStack2 = *testStack; 98 99 BOOST_REQUIRE(testStack2->getSizeOfStack() == 3);100 BOOST_REQUIRE(testStack2->top() == 3);101 102 BOOST_REQUIRE(testStack2->pop() == true);103 BOOST_REQUIRE(testStack2->top() == 2);104 BOOST_REQUIRE(testStack2->getSizeOfStack() == 2);105 106 BOOST_REQUIRE(testStack2->pop() == true);107 BOOST_REQUIRE(testStack2->top() == 1);108 BOOST_REQUIRE(testStack2->getSizeOfStack() == 1);109 110 BOOST_REQUIRE(testStack2->pop() == true);111 BOOST_REQUIRE(testStack2->getSizeOfStack() == 0);112 113 BOOST_REQUIRE(testStack2->pop() == false);114 }115 116 BOOST_AUTO_TEST_SUITE_END()
2.3 基于指针
基于指针的栈也是在程序运行时才动态分配内存的。不过，它跟前两者不一样的是，它的内存利用效率高，不会存在内存浪费的问题。当然，这也就需要额外更多的内存申请及释放操作。
栈模板类：
1 template<class T> 2 class Node 3 { 4 public: 5 T data; 6 Node * next; 7 }; 8 9 template<class T>10 class Stack11 {12 public:13 typedef Node<T> * NodePointer;14 15 public:16 Stack();17 virtual ~Stack();18 Stack(const Stack& orig); // 拷贝构造函数19 Stack& operator=(const Stack& orig); // 赋值运算符重载20 bool isEmpty();21 bool push(T val); // 进栈。若栈不满，则将元素插入栈顶。22 T top(); // 取栈顶元素。若栈S非空，则返回栈顶元素，但不改变栈的状态。23 bool pop(); // 退栈。若栈非空，则将栈顶元素删去，并返回是否退栈成功的标志。24 // 这里没有采用返回被删栈顶元素的原因在于这里写的是一个模板，25 // 当栈为空的时候不方便返回。当然，这个问题是可以通过断言或26 // 抛异常来解决的。具体做法可根据具体情况来定。27 int getSizeOfStack();28 29 private:30 NodePointer stack;31 32 };
具体实现代码为：
1 #include <iostream> 2 #include <cassert> 3 using namespace std; 4 5 template<class T> 6 class Node 7 { 8 public: 9 T data; 10 Node * next; 11 }; 12 13 template<class T> 14 class Stack 15 { 16 public: 17 typedef Node<T> * NodePointer; 18 19 public: 20 Stack(); 21 virtual ~Stack(); 22 Stack(const Stack& orig); // 拷贝构造函数 23 Stack& operator=(const Stack& orig); // 赋值运算符重载 24 bool isEmpty(); 25 bool push(T val); // 进栈。若栈不满，则将元素插入栈顶。 26 T top(); // 取栈顶元素。若栈S非空，则返回栈顶元素，但不改变栈的状态。 27 bool pop(); // 退栈。若栈非空，则将栈顶元素删去，并返回是否退栈成功的标志。 28 // 这里没有采用返回被删栈顶元素的原因在于这里写的是一个模板， 29 // 当栈为空的时候不方便返回。当然，这个问题是可以通过断言或 30 // 抛异常来解决的。具体做法可根据具体情况来定。 31 int getSizeOfStack(); 32 33 private: 34 NodePointer stack; 35 36 }; 37 38 template<class T> 39 Stack<T>::Stack() 40 { 41 stack = NULL; 42 } 43 44 template<class T> 45 Stack<T>::~Stack() 46 { 47 NodePointer ptr = stack, tmpPtr; 48 while (ptr != NULL) 49 { 50 tmpPtr = ptr; 51 ptr = ptr->next; 52 delete tmpPtr; 53 } 54 } 55 56 template<class T> 57 Stack<T>::Stack(const Stack& orig) 58 { 59 stack = NULL; // 需要特别注意的是，调用拷贝构造函数时并不会“提前”调用构造函数 60 NodePointer tmpPtr = orig.stack; 61 while (tmpPtr != NULL) 62 { 63 push(tmpPtr->data); 64 tmpPtr = tmpPtr->next; 65 } 66 } 67 68 template<class T> 69 Stack<T>& Stack<T>::operator=(const Stack& orig) // 这里需要非常注意返回值要写为 70 // Stack<T>而不是Stack 71 { 72 //stack = NULL; 在这里可以不用，因为调用“赋值运算符”前会提前调用构造函数 73 NodePointer tmpPtr = orig.stack; 74 while (tmpPtr != NULL) 75 { 76 push(tmpPtr->data); 77 tmpPtr = tmpPtr->next; 78 } 79 80 return *this; 81 } 82 83 template<class T> 84 bool Stack<T>::isEmpty() 85 { 86 return stack == NULL; 87 } 88 89 template<class T> 90 bool Stack<T>::push(T val) 91 { 92 bool isSuccess = true; 93 NodePointer ptr = new Node<T>(), tmpPtr; 94 //assert(ptr != NULL); 95 //isSuccess = false; 96 ptr->data =http://www.mamicode.com/ val; 97 if (stack == NULL) // when the stack is empty 98 { 99 stack = ptr;100 ptr->next = NULL;101 }102 else // others103 {104 tmpPtr = stack;105 int len = getSizeOfStack();106 int count = 0;107 while (tmpPtr != NULL && count < len - 1)108 {109 tmpPtr = tmpPtr->next;110 count++;111 }112 tmpPtr->next = ptr;113 ptr->next = NULL;114 }115 116 return isSuccess;117 }118 119 template<class T>120 T Stack<T>::top()121 {122 NodePointer tmpPtr = stack;123 int len = getSizeOfStack();124 int count = 0;125 while (tmpPtr != NULL && count < len - 1)126 {127 tmpPtr = tmpPtr->next;128 count++;129 }130 131 return tmpPtr->data;132 }133 134 template<class T>135 bool Stack<T>::pop()136 {137 bool isSuccess = true;138 int len = getSizeOfStack();139 if (len == 0)140 {141 cerr << "There is no element in stack." << endl;142 isSuccess = false;143 }144 else145 {146 NodePointer tmpPtr = stack, tmpPtr2;147 if (len == 1)148 {149 delete tmpPtr;150 stack = NULL;151 }152 else153 {154 int count = 0;155 while (tmpPtr != NULL && count < len - 2)156 {157 tmpPtr = tmpPtr->next;158 count++;159 }160 tmpPtr2 = tmpPtr->next;161 tmpPtr->next = NULL;162 delete tmpPtr2;163 }164 }165 166 return isSuccess;167 }168 169 template<class T>170 int Stack<T>::getSizeOfStack()171 {172 int len = 0;173 NodePointer ptr = stack;174 while (ptr != NULL)175 {176 len++;177 ptr = ptr->next;178 }179 return len;180 }
Boost单元测试代码为：
1 #define BOOST_TEST_MODULE Stack_Test_Module 2 3 #include "stdafx.h" 4 #include "../Stack/stack.hpp" 5 6 struct Stack_Fixture 7 { 8 public: 9 Stack_Fixture() 10 { 11 testStack = new Stack<int>(); 12 } 13 ~Stack_Fixture() 14 { 15 delete testStack; 16 } 17 Stack<int> * testStack; 18 }; 19 20 BOOST_FIXTURE_TEST_SUITE(Stack_Test_Fixture, Stack_Fixture) 21 22 BOOST_AUTO_TEST_CASE(Stack_Test) 23 { 24 // isEmpty ------------------------------------ 25 BOOST_REQUIRE(testStack->isEmpty() == true); 26 27 // isEmpty ------------------------------------ 28 BOOST_REQUIRE(testStack->getSizeOfStack() == 0); 29 30 // push & top --------------------------------- 31 BOOST_REQUIRE(testStack->push(1) == true); 32 BOOST_REQUIRE(testStack->top() == 1); 33 BOOST_REQUIRE(testStack->getSizeOfStack() == 1); 34 35 BOOST_REQUIRE(testStack->push(2) == true); 36 BOOST_REQUIRE(testStack->top() == 2); 37 BOOST_REQUIRE(testStack->getSizeOfStack() == 2); 38 39 BOOST_REQUIRE(testStack->push(3) == true); 40 BOOST_REQUIRE(testStack->top() == 3); 41 BOOST_REQUIRE(testStack->getSizeOfStack() == 3); 42 43 // pop & top ---------------------------------- 44 BOOST_REQUIRE(testStack->pop() == true); 45 BOOST_REQUIRE(testStack->top() == 2); 46 BOOST_REQUIRE(testStack->getSizeOfStack() == 2); 47 48 BOOST_REQUIRE(testStack->pop() == true); 49 BOOST_REQUIRE(testStack->top() == 1); 50 BOOST_REQUIRE(testStack->getSizeOfStack() == 1); 51 52 BOOST_REQUIRE(testStack->pop() == true); 53 BOOST_REQUIRE(testStack->getSizeOfStack() == 0); 54 55 BOOST_REQUIRE(testStack->pop() == false); 56 } 57 58 BOOST_AUTO_TEST_CASE(Stack_CopyConstructor_Test) 59 { 60 // initialize --------------------------------- 61 BOOST_REQUIRE(testStack->push(1) == true); 62 BOOST_REQUIRE(testStack->push(2) == true); 63 BOOST_REQUIRE(testStack->push(3) == true); 64 65 Stack<int> * testStack2 = new Stack<int>(*testStack); 66 67 BOOST_REQUIRE(testStack2->getSizeOfStack() == 3); 68 BOOST_REQUIRE(testStack2->top() == 3); 69 70 BOOST_REQUIRE(testStack2->pop() == true); 71 BOOST_REQUIRE(testStack2->top() == 2); 72 BOOST_REQUIRE(testStack2->getSizeOfStack() == 2); 73 74 BOOST_REQUIRE(testStack2->pop() == true); 75 BOOST_REQUIRE(testStack2->top() == 1); 76 BOOST_REQUIRE(testStack2->getSizeOfStack() == 1); 77 78 BOOST_REQUIRE(testStack2->pop() == true); 79 BOOST_REQUIRE(testStack2->getSizeOfStack() == 0); 80 81 BOOST_REQUIRE(testStack2->pop() == false); 82 } 83 84 BOOST_AUTO_TEST_CASE(Stack_EqualOperator_Test) 85 { 86 // initialize --------------------------------- 87 BOOST_REQUIRE(testStack->push(1) == true); 88 BOOST_REQUIRE(testStack->push(2) == true); 89 BOOST_REQUIRE(testStack->push(3) == true); 90 91 Stack<int> * testStack2 = new Stack<int>(); 92 *testStack2 = *testStack; 93 94 BOOST_REQUIRE(testStack2->getSizeOfStack() == 3); 95 BOOST_REQUIRE(testStack2->top() == 3); 96 97 BOOST_REQUIRE(testStack2->pop() == true); 98 BOOST_REQUIRE(testStack2->top() == 2); 99 BOOST_REQUIRE(testStack2->getSizeOfStack() == 2);100 101 BOOST_REQUIRE(testStack2->pop() == true);102 BOOST_REQUIRE(testStack2->top() == 1);103 BOOST_REQUIRE(testStack2->getSizeOfStack() == 1);104 105 BOOST_REQUIRE(testStack2->pop() == true);106 BOOST_REQUIRE(testStack2->getSizeOfStack() == 0);107 108 BOOST_REQUIRE(testStack2->pop() == false);109 }110 111 BOOST_AUTO_TEST_SUITE_END()
本篇博文的代码均托管到Taocode : http://code.taobao.org/p/datastructureandalgorithm/src/.
栈的三种实现（静态数组、动态数组及指针）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。