数据结构：第十九节-链式栈

Cpp入门到精通 2024-06-07

135

点击蓝字

山月

关注我们

第十九节链式栈

上一节我们介绍了顺序栈的表示与实现，顺序栈的特点是数据存储在一段连续的内存空间中，并且栈顶元素位于数组的末尾。这节我们介绍另一种为链式结构的栈-链式栈。

我们之前已经学习了顺序表与链表，其实顺序栈和链式栈也是一样的区别。

链式栈是一种基于链表实现的栈结构，它使用链表来存储栈中的元素，并通过指针来连接这些元素。链式栈不需要预先分配固定大小的内存空间，可以根据需要动态地分配和释放内存。

链式栈的基本结构是一个链表，每个节点包含两个部分：数据域和指针域。数据域用于存储栈中的元素值，指针域用于指向下一个节点，构成链式结构。链式栈通常包含一个指向栈顶节点的指针，通过该指针可以方便地对栈进行操作。

接下来我们看链式栈的结构体定义：

struct Node {
    int data;     // 数据域
    Node* next;   // 指针域，指向下一个节点
};


// 定义链式栈结构体
struct LinkedStack {
    Node* top;    // 栈顶指针
};

链式栈的基本操作包括入栈（Push）、出栈（Pop）、获取栈顶元素（Top）、判断栈空（IsEmpty）等。

1.入栈：将一个元素压入栈顶。

void Push(LinkedStack& stack, int value) {
    // 创建新节点
    Node* newNode = new Node;
    newNode->data = value; // 设置新节点的数据域
    newNode->next = stack.top; // 将新节点的指针域指向当前栈顶节点
    stack.top = newNode; // 更新栈顶指针为新节点
}

我们创建一个新的节点，将要入栈的元素存储在节点中，将新节点插入到链表的头部，并更新栈顶指针指向新节点。

2.出栈：从栈顶弹出一个元素。

bool Pop(LinkedStack& stack, int& value) {
    if (IsEmpty(stack)) {
        cout << "栈为空，不能弹出元素！" << endl;
        return false; // 栈为空，无法出栈
    }
    // 获取栈顶节点的数据域值
    value = stack.top->data;
    // 将栈顶指针指向下一个节点
    Node* temp = stack.top;
    stack.top = stack.top->next;
    delete temp; // 释放原栈顶节点的内存空间
    return true; // 出栈成功
}

我们首先检查链式栈是否为空，如果为空则无法出栈，返回 false。否则，将栈顶节点的数据域值存储到 value 中，然后将栈顶指针移动到下一个节点，最后释放原栈顶节点的内存空间，并返回 true 表示出栈成功。在链式栈的删除元素操作中，我们需要释放每个节点的内存空间，而在释放一个节点的内存空间之前，需要先将这个节点的地址存储在 temp 中，以便后续访问。

3.判断栈空：判断栈是否为空。

bool IsEmpty(const LinkedStack& stack) {
    return stack.top == nullptr; // 栈顶指针为空表示栈为空
}

若栈顶指针为空，则栈为空。

4.清空栈：将栈中所有元素清空。

void Clear(LinkedStack& stack) {
    while (stack.top != nullptr) {
        Node* temp = stack.top;
        stack.top = stack.top->next;
        delete temp; // 释放节点的内存空间
    }
}

我们使用循环遍历链式栈，将栈顶指针不断指向下一个节点，然后释放当前节点的内存空间，直到栈顶指针指向空节点，表示链式栈已清空。

5.销毁栈：销毁栈，释放所有内存空间。

void Destroy(LinkedStack& stack) {
    Clear(stack); // 先清空栈
    stack.top = nullptr; // 将栈顶指针置为空
}

释放所有节点的内存空间，并将栈结构体的指针置为空。

6.获取栈的长度：获取栈中元素的个数。

int Size(const LinkedStack& stack) {
    int count = 0;          // 初始化计数器为0
    Node* current = stack.top;  // 将栈顶指针赋值给current
    while (current != nullptr) { // 当前节点不为空时
        count++;                // 计数器加1
        current = current->next;  // 移动到下一个节点
    }
    return count;               // 返回计数器的值，即链式栈的大小
}