链栈的原理和链表的原理一样，通过一个next指针把一个个的节点链起来：
初始时，栈底指针和栈顶指针都为空，每插入一个节点，栈顶指针改变，当前插入节点的next指针指向之前的栈顶元素。
同样，在使用top()和pop()两个方法时，也要先判断栈是否为空。
一、栈节点
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#define uint unsigned int template <typename T> class CStackNode { public: CStackNode() : data(0), pre(0), next(0) {}; CStackNode(T e, CStackNode* next = 0) : data(e), next(next) {}; ~CStackNode() { next = 0; }; T getData() const{ return data; }; void setNext(CStackNode* e){ next = p; }; CStackNode *getNext() const{ return next; }; private: T data; CStackNode *next; }; |
二、栈
2.1 类定义
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#include "StackNode.h" template <typename T> class CMyStack { public: CMyStack(); ~CMyStack(); void push(T t); T top() const; T pop(); uint size() const; bool empty() const; private: CStackNode<T>* bottom; CStackNode<T>* cur; uint len; }; |
2.2 类实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
template<typename T> inline CMyStack<T>::CMyStack() { bottom = cur = 0; len = 0; } template<typename T> inline CMyStack<T>::~CMyStack() { if (!bottom) return; CStackNode<T>* p = cur, *q; while (p) { q = p->getNext(); delete p; p = q; } bottom = cur = 0; len = 0; } // 压栈 template<typename T> inline void CMyStack<T>::push(T t) { CStackNode<T> *pNode = new CStackNode<T>(t); pNode->setNext(cur); cur = pNode; // 如果栈为空，设置bottom的值 if (!bottom) bottom = cur; len++; } // 获取栈顶元素 template<typename T> inline T CMyStack<T>::top() const { return cur->getData(); } // 出栈 template<typename T> inline T CMyStack<T>::pop() { T tmp = cur->getData(); CStackNode<T> *dNode = cur; cur = cur->getNext(); // 删除节点 delete dNode; len -= 1; // 当前结点是最后一个 if (!cur) bottom = 0; return tmp; } // 返回栈大小 template<typename T> inline uint CMyStack<T>::size() const { return len; } // 判断栈是否为空 template<typename T> inline bool CMyStack<T>::empty() const { return len == 0; } |
![[leetcode]226-翻转二叉树](https://www.dyxmq.cn/wp-content/themes/begin/prune.php?src=https://www.dyxmq.cn/wp-content/uploads/2020/02/cff55-image8d13f59af4ceb4d0.png&w=280&h=210&a=&zc=1)
![[leetcode]145-二叉树的后序遍历](https://www.dyxmq.cn/wp-content/themes/begin/prune.php?src=https://www.dyxmq.cn/wp-content/uploads/2020/02/ce5a3-image6343ae7c83fc33ae.png&w=280&h=210&a=&zc=1)
评论