栈的特性：
后进先出/先进后出
栈的常见操作：
Push——压栈
Pop——出栈
Top——求栈顶
Empty——判断栈是否为空
Size——求栈中元素个数
动态栈的模拟实现：
#define _CRT_SECURE_NO_WARNINGS 1 #include<assert.h> template<class T> class Stack { public: Stack() //构造函数 : _arr(NULL) , _size(0) , _capacity(0) {} Stack(const Stack<T>& s) //拷贝构造函数 : _arr(NULL) , _size(s._size) , _capacity(s._capacity) { _arr = new int[s._capacity]; for (size_t i = 0; i < s._size(); ++i) { _arr[i] = s._arr[i]; } } Stack<T>& operator=(const Stack<T>& s) //赋值运算符重载 { if (this != &s) { _capacity = _capacity * 2 + 3; T * tmp = new int[s._capacity]; for (size_t i = 0; i < s._size; ++i) { _arr[i] = s._arr[i]; } delete _arr; arr = tmp; _size = s._size; _capacity = s._capacity; } return *this; } ~Stack() //析构函数 { delete []_arr; _arr = NULL; _size = 0; _capacity = 0; } public: void CheckCapacity() { if (_size >= _capacity) { T* tmp = new int[2 * _capacity + 3]; for (size_t i = 0; i < _size; ++i) { tmp[i] = _arr[i]; } delete[] _arr; _arr = tmp; _capacity = 2 * _capacity + 3; } } void Push(const T& data) //压栈 { CheckCapacity(); _arr[_size] = data; ++_size; } void Pop() { assert(_arr); --_size; } T& Top() { return _arr[_size - 1]; } const T& Top()const { return _arr[_size - 1]; } size_t Size() { return _size; } bool Empty() { return _size == 0; } protected: T *_arr; size_t _size; //栈中有效元素的个数 size_t _capacity; //栈的总容量 }; void TestStack() { Stack<int> s1; s1.Push(1); s1.Push(2); s1.Push(4); s1.Push(3); s1.Push(5); cout << s1.Size() << endl; while (!s1.Empty()) { cout << s1.Top() << " "; s1.Pop(); } } #include<iostream> using namespace std; #include "stack.h" int main() { TestStack(); system("pause"); return 0; }
