链栈

【概述】

链栈是采取链式存储的栈，其不存在栈满上溢的情况，通常采用不带头结点的单链表来实现，且一般规定所有的操作都在单链表表头进行，以保证出栈、入栈、取栈顶操作的时间复杂度为 $O(1)$

链栈的实现类如下：

template <typename T> 
struct LNode {      //单链表结点
    T data;         //数据域
    LNode<T> *next; //指针域
};
template <typename T> 
class LinkStack {
  public:
    LinkStack();          //初始化栈
    int getLen();         //求栈长
    bool empty();         //判空
    bool pop(T &elem);    //出栈
    bool push(T elem);    //入栈
    bool getTop(T &elem); //取栈顶
    void print();         //输出
  private:
    LNode<T> *first;     //头指针
};

【初始化】

由于采用不带头结点的单链表，因此在初始化时直接令头指针指向为 NULL 即可

template <typename T> 
LinkStack<T>::LinkStack() { //初始化栈
    first = NULL;
}

【求栈长】

由于采用的是链式存储结构，因此在求栈长时，要从头指针开始枚举，枚举到链表尾部，时间复杂度为 $O(n)$

template <typename T> 
int LinkStack<T>::getLen() { //求栈长
    LNode<T> *p = first;
    int len = 0;
    while (p != NULL) {
        len++;
        p = p->next;
    }
    return len;
}

【判空】

判空时，只需判断头指针 first 是否为 NULL 即可

template <typename T>
bool LinkStack<T>::empty() { //判空
    if (first == NULL)
        return true;
    return false;
}

【出栈】

在出栈时，首先进行下溢判断，之后令头指针指向的结点出栈，释放空间，再令头指针后移

template <typename T> 
bool LinkStack<T>::pop(T &elem) { //出栈
    if (empty()) //下溢判断
        return false;
    LNode<T> *p = first;
    elem = p->data;
    first = first->next;
    free(p);
    return true;
}

【入栈】

在入栈时，首先进行申请空间，之后采用头插法将新元素入栈

template <typename T> 
bool LinkStack<T>::push(T elem) { //入栈
    LNode<T> *p = (LNode<T> *)malloc(sizeof(LNode<T>));
    if (p == NULL) //空间分配失败
        return false;
    p->data = elem;
    p->next = first;
    first = p;
    return true;
}

【取栈顶】

在取栈顶时，首先进行下溢判断，之后输出头指针指向结点的数据域即可

template <typename T> 
bool LinkStack<T>::getTop(T &elem) { //取栈顶
    if (empty()) //下溢判断
        return false;
    elem = first->data;
    return true;
}

【输出】

在输出时，从栈顶开始，将栈中所有元素依次出栈，进行输出即可

template <typename T> 
void LinkStack<T>::print() { //输出
    int elem;
    while (!empty()) { //将所有元素依次出栈进行输出
        pop(elem);
        cout << elem << " ";
    }
    cout << endl;
}