加载中

手写数据结构·线性表15:链式栈

链式栈(LinkedStack)

template<class T>
class LinkedStack {
    struct Node {
        T data;
        Node* next;
        Node(const T& x,Node* p=nullptr){ data=x; next=p; }
    };

    Node* topPointer;
    int n;

public:
    LinkedStack(){ topPointer=nullptr; n=0; }
    ~LinkedStack(){ clear(); }

    bool empty() const { return topPointer==nullptr; }
    int size() const { return n; }

    void push(const T& x){
        topPointer=new Node(x,topPointer);
        n++;
    }

    bool pop(){
        if(empty()) return false;

        Node* q=topPointer;
        topPointer=topPointer->next;
        delete q;
        n--;
        return true;
    }

    T& top(){
        if(empty()) throw underflow_error("LinkedStack::top on empty stack");
        return topPointer->data;
    }

    void clear(){
        while(!empty()) pop();
    }
};

工程细节

  • 栈顶指针就是链首指针;入栈头插,出栈删首,两者均为 O(1)。
  • 入栈时新结点先指向旧栈顶,再更新 topPointer。出栈先保存旧栈顶、更新指针,再释放旧结点。
  • 空栈不能读取 top();pop() 在空栈返回 false。清空反复出栈,最后 topPointer == nullptr 且 n == 0。

跳转

下一个:链式队列

上一个:双向循环链表

本文作者:flowwalker之码艺Blog

本文链接:/coding-notes-blog/posts/5a74646e/

版权声明:本文采用 CC BY-NC-SA 4.0 许可协议