? ? 采用鏈式存儲的棧成為鏈式棧(或簡稱鏈棧),?鏈棧的優點是便于多個棧共享存儲空間和提高其效率,?且不存在棧滿上溢的情況(因為鏈棧是靠指針鏈接到一起,只要內存夠大,?則鏈棧理論上可以存儲的元素是沒有上限的);

? ? 與順序棧相比,?由于順序棧是采用的數組實現,?因此一旦數組填滿,?則必須重新申請內存,?并將所有元素”搬家”,?而鏈棧則省略了這一”耗時耗力”的工作,?但卻需要付出附加一個指針的代價;

? ? 鏈棧通常采用單鏈表實現,?并規定所有的操作都必須實在單鏈表的表頭進行,?而且w我們的鏈棧沒有頭結點,?m_top直接指向棧頂元素;

鏈式棧的圖示如下:

鏈棧節點構造:

template <typename Type> class ChainNode {template <typename T>friend ostream &operator<<(ostream &os, const LinkStack<T> &stack);friend class LinkStack<Type>; private:ChainNode(const Type &_data, ChainNode *_next = NULL):data(_data), next(_next) {}Type data;ChainNode *next; };

鏈棧設計:

template <typename Type> class LinkStack {template <typename T>friend ostream &operator<<(ostream &os, const LinkStack<T> &stack); public:LinkStack(): m_top(NULL) {}~LinkStack(){makeEmpty();}bool isEmpty() const{return m_top == NULL;}void pop() throw(std::out_of_range);const Type &top() const throw(std::out_of_range);void push(const Type &data);void makeEmpty();private:ChainNode<Type> *m_top; };

棧的三大操作:

template <typename Type> const Type &LinkStack<Type>::top() const throw (std::out_of_range) {if (isEmpty())throw std::out_of_range("stack is empty, can`t get data");return m_top->data; } template <typename Type> void LinkStack<Type>::pop() throw (std::out_of_range) {if (isEmpty())throw std::out_of_range("stack is empty, can`t delete");ChainNode<Type> *deleteNode = m_top;m_top = m_top->next;delete deleteNode; } template <typename Type> void LinkStack<Type>::push(const Type &data) {//此處是整個鏈棧的關鍵點// 該操作會生成一個節點,// 并自動將m_top上移一格,// 而且將m_top原先指向的節點, 作為新生成的節點的下一節點//注意此處//如果第一次運行push, 則原m_top為NULL// 新m_top指向第一個元素m_top = new ChainNode<Type>(data, m_top); }

清空整個棧:

template <typename Type> void LinkStack<Type>::makeEmpty() {while (!isEmpty()){pop();} }

輸出棧內所有內容:

template <typename Type> ostream &operator<<(ostream &os, const LinkStack<Type> &stack) {ChainNode<Type> *currentNode = stack.m_top;while (currentNode != NULL){cout << currentNode->data << ' ';currentNode = currentNode->next;}return os; }

測試代碼:

int main() {LinkStack<int> test;for (int i = 0; i < 10; ++i){test.push(rand()%100);}cout << test << endl;cout << "top = " << test.top() << endl;test.pop();cout << "top = " << test.top() << endl;test.push(1);cout << "top = " << test.top() << endl;while (!test.isEmpty()){test.pop();}cout << test << endl;test.push(11);test.push(22);test.push(33);cout << test << endl;test.makeEmpty();try{cout << "top = " << test.top() << endl;}catch (const std::exception &e){cerr << e.what() << endl;}return 0; }

總結

以上是生活随笔為你收集整理的数据结构基础(13) --链式栈的设计与实现的全部內容，希望文章能夠幫你解決所遇到的問題。

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