栈的简介及C++模板实现( 二 ) _栈的简

测试结果：
栈的大小:5栈是否为空:0栈顶元素：4依次出栈:43210回到顶部
3. 基于单链表的栈以链表为底层的数据结构时，以链表头为作为栈顶较为合适，这样方便节点的插入与删除。压栈产生的新节点将一直出现在链表的头部；

文章插图

3.1 链表节点
/*链表节点结构*/template <typename T>struct Node{ Node(T t) :value(t), next(nullptr){}; Node() :next(nullptr){}; public: T value; Node<T>* next;};

value:栈中元素的值
next:链表节点指针，指向直接后继

3.2 栈的抽象数据类型
基于链表的栈提供的接口与基于数组的栈一致。
/*栈的抽象数据结构*/template <typename T>class LinkStack{public: LinkStack(); ~LinkStack();public:bool isEmpty(); int size(); void push(T t); T pop(); T top(); private:Node<T>* phead; int count;};【栈的简介及C++模板实现】3.3 栈的具体实现
/*返回栈的大小*/template <typename T>int LinkStack<T>::size(){ return count;};/*栈的判空操作*/template <typename T>bool LinkStack<T>::isEmpty(){ return count == 0;};/*插入元素*/template<typename T>void LinkStack<T>::push(T t){ Node <T> *pnode = new Node<T>(t); pnode->next = phead->next; phead->next = pnode; count++;};/*弹栈*/template <typename T>T LinkStack<T>::pop(){ if (phead->next != nullptr) //栈空判断 { Node<T>* pdel = phead->next; phead->next = phead->next->next; T value = https://www.isolves.com/it/cxkf/bk/2019-08-26/pdel->value; delete pdel; count--; return value; }};/*获取栈顶元素*/template T LinkStack::top(){ if (phead->next!=nullptr) return phead->next->value;};3.4 栈的代码测试
int _tmain(int argc, _TCHAR* argv[]){ LinkStack <string> lstack; lstack.push("hello"); lstack.push("to"); lstack.push("you！");cout << "栈的大小:" << lstack.size() << endl; cout <<"栈顶元素:"<< lstack.top() << endl;while (!lstack.isEmpty()) { lstack.pop(); }cout << "栈的大小:" << lstack.size() << endl;getchar(); return 0;}测试结果：
栈的大小:3栈顶元素:you！栈的大小:0回到顶部
4. 栈的完整代码基于数组的栈： https://github.com/huanzheWu/Data-Structure/blob/master/Stack/Main/Main/ArrayStack.h
基于单链表的栈：https://github.com/huanzheWu/Data-Structure/blob/master/singleList/singleList/singleList.h
原创文章，转载请注明出处：http://www.cnblogs.com/QG-whz/p/5170418.html