【實現類】

template <class T> struct Node{T data;Node *next; }; template <class T> class linkStack{ public:linkStack();~linkStack();void push(T x);//入棧T pop();//出棧T getTop();//獲取棧頂元素bool empty();//判斷是否為空 private:Node<T> *top; //棧頂指針 };

【構造函數】

將棧首指針設為 NULL?即可

template <class T> linkStack<T>::linkStack(){top=NULL; }

【析構函數】

template <class T> linkStack<T>::~linkStack(){while(top!=NULL){//棧不為空Node<T> *p;p=top->next;//工作指針暫存下一元素delete top;//刪除棧頂元素top=p;//棧頂指針指向下一元素} }

【進棧】

將新元素存入棧

棧指針指向下一元素

template <class T> void linkStack<T>::push(T x){Node<T> *s=new Node<T>;s->data=x;//新元素入棧s->next=top;//指向棧頂top=s;//棧頂指針指向下一元素 }

【出棧算法】

若 top=NULL，則給出下溢信息

獲取要退棧的元素 x，并刪除退棧元素所占的空間

棧指針指向下一元素

返回退棧元素

template <class T> T linkStack<T>::pop(){if(top==NULL)//溢出判斷throw "下溢";T x=top->data;//取出棧元素Node<T> *p=top;//暫存棧頂元素top=top->next;//指向下一元素delete p;//刪除暫存元素return x;//返回出棧元素 }

【判斷棧空】

判斷棧頂指針是否為 NULL，若 top=NULL，則棧空

template <class T> bool linkStack<T>::empty(){if(top==NULL)return true;return false; }

【取棧頂元素】

判斷棧是否為空

若棧不為空，直接返回棧頂元素 top->data

template <class T> T linkStack<T>::getTop(){if(empty())throw "棧為空";return top->data; }

總結

以上是生活随笔為你收集整理的理论基础 —— 栈 —— 链栈的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。