写栈比队列更简单一些，毕竟只有一个数据出入口。
之前用C在程序里模拟栈代替递归的时候，直接搞个数组来实现都是非常轻松愉快的事情。
不多说，放代码。
测试代码
1 #include <iostream> 2 #include "stack.h" 3 using namespace std; 4 using namespace stack; 5 template class Stack<int>; 6 int main(void) 7 { 8 Stack<int> number; 9 10 //测试入栈 11 cout << "/*additem()*/" << endl; 12 number.push(2); 13 number.push(3); 14 number.push(5); 15 number.push(7); 16 number.push(11); 17 number.traverse(); 18 cout << " /*end*/ " << flush; 19 20 //测试获取长度 21 cout << "/*length()*/" << endl; 22 cout << number.size() << endl; 23 cout << "/*end*/ " << flush; 24 25 //测试获得头元素 26 cout << "/*getfirst()*/" << endl; 27 cout << number.getfirst() << endl; 28 cout << "/*end*/ " << flush; 29 30 //测试出栈 31 cout << "/*remove()*/" << endl; 32 number.pop(); 33 number.pop(); 34 number.traverse(); 35 cout << " /*end*/ " << flush; 36 37 //测试清空，并测试从空表中出栈 38 cout << "/*clear(),remove()*/" << endl; 39 number.clear(); 40 number.pop(); 41 cout << "/*end*/ " << flush; 42 43 system("pause"); 44 }
主体代码
1 #ifndef STACK 2 #define STACK 3 #include <iostream> 4 using namespace std; 5 6 namespace stack 7 { 8 9 //节点模板 10 template <typename T> struct Node 11 { 12 Node<T>() : next(nullptr){} 13 Node<T>(const T &item, Node<T>* ptr = nullptr) : data(item), next(ptr){} 14 T data; 15 Node<T>* next; 16 }; 17 //头节点及主体操作 18 template <typename T> class Stack 19 { 20 //构造函数 21 public: 22 Stack<T>() : length(0), front(nullptr){} 23 //接口 24 public: 25 //返回长度 26 unsigned int size()const{ return length; } 27 //返回头指针 28 Node<T>* begin()const{ return front; } 29 //判断是否为空 30 bool empty()const{ return length == 0; } 31 //获得头元素 32 T getfirst()const{ return front->data; } 33 //#查找元素所在地址 34 Node<T>* find(const T &item)const; 35 //#入栈 36 bool push(const T &item); 37 //#出栈 38 bool pop(); 39 //#遍历并输栈元素 40 void traverse()const; 41 //#清空栈 42 void clear(); 43 44 //辅助函数 45 private: 46 //#查找元素前驱 47 Node<T>* find_prev(const T& item)const; 48 //数据 49 private: 50 unsigned int length; 51 Node<T>* front; 52 }; 53 54 //如果元素为头元素或元素不存在则返回nullptr，否则返回前驱 55 template <typename T> Node<T>* Stack<T>::find_prev(const T& item)const 56 { 57 if (length == 0) 58 return nullptr; 59 if (front->data == item) 60 return nullptr; 61 for (Node<T>* iter = front; iter->next != nullptr; iter = iter->next) 62 { 63 if (iter->next->data == item) 64 return iter; 65 } 66 return nullptr; 67 } 68 //调用find_prev，如果元素存在则返回地址，不存在则返回nullptr 69 template <typename T> Node<T>* Stack<T>::find(const T &item)const 70 { 71 Node<T>* iter = find_prev(item); 72 if (length == 0) 73 return nullptr; 74 if (front->data == item) 75 return front; 76 return iter->next; 77 } 78 template <typename T> bool Stack<T>::push(const T &item) 79 { 80 Node<T>* pnew = new Node<T>(item); 81 pnew->next = front; 82 front = pnew; 83 ++length; 84 return true; 85 } 86 template <typename T> bool Stack<T>::pop() 87 { 88 if (length == 0) 89 { 90 cout << "No data!" << endl; 91 return false; 92 } 93 Node<T>* save = front; 94 front = front->next; 95 delete save; 96 --length; 97 return true; 98 } 99 template <typename T> void Stack<T>::traverse()const 100 { 101 if (length != 0) 102 { 103 for (Node<T>* iter = front; iter != nullptr; iter = iter->next) 104 cout << iter->data << ends; 105 } 106 } 107 template <typename T> void Stack<T>::clear() 108 { 109 Node<T>* iter; 110 while (front != nullptr) 111 { 112 iter = front; 113 front = front->next; 114 delete iter; 115 } 116 front = nullptr; 117 length = 0; 118 } 119 } 120 #endif