目录

1.链栈的概念

2.链栈的链式存储实现

1.初始化

2.销毁        

3.清空栈

4.判断栈空

5.栈长        

6.获取栈顶元素        

7.入栈

8.出栈

9.遍历

10.完整代码

---

1.链栈的概念

    链栈是指采用链式存储结构实现的栈。通常使用单链表来表示。链栈的示意图如下：

        图1.链栈示意图

2.链栈的链式存储实现

        链栈的定义如下：

#define ElementType int
typedef int Status;
typedef struct StackNode {ElementType data;struct StackNode *next;
} StackNode, *LinkStack;

1.初始化

        链栈的初始化只需要将指针置为空来表示链栈为空。

// 初始化链栈
Status initLinkStack(LinkStack &linkStack) {linkStack = nullptr; // 将链栈指针初始化为 nullptrreturn 1;
}

2.销毁        

        这个方法会释放链栈中所有节点的内存，将链栈的头指针置空，以表示链栈已经被销毁。

// 销毁链栈
void destroyLinkStack(LinkStack &linkStack) {LinkStack p = linkStack;while (p) {LinkStack temp = p;p = p->next;delete temp;}linkStack = nullptr; // 将链栈指针设置为 nullptr
}

3.清空栈

         释放链栈中每个节点的内存，使链栈变为空栈。

// 清空链栈
void clearLinkStack(LinkStack &linkStack) {while (linkStack != nullptr) {LinkStack temp = linkStack; // 暂存当前节点linkStack = linkStack->next; // 移动到下一个节点delete temp; // 释放当前节点的内存}
}

4.判断栈空

        这个方法会检查链栈是否为空，如果链栈头指针为空，则说明链栈为空，返回 true，否则返回 false。        

// 判断链栈是否为空
Status linkStackEmpty(LinkStack linkStack) {return linkStack == nullptr;
}

5.栈长        

        遍历链栈，统计链栈中节点的个数，并返回该值。

// 获取链栈的长度
int getLinkStackLength(LinkStack linkStack) {int length = 0;StackNode *current = linkStack;while (current != nullptr) {length++;current = current->next;}return length;
}

6.获取栈顶元素        

        获取链栈的栈顶元素，并通过指针参数 element 返回栈顶元素的值。

// 获取链栈的栈顶元素
Status getLinkStackTop(LinkStack linkStack, ElementType &element) {if (linkStack == nullptr || linkStack->next == nullptr) {return 0;}element = linkStack->next->data;return 1;
}

7.入栈

        该方法用于将元素压入链栈，将新元素插入到链栈的顶部。

        图2.入栈过程

// 入链栈
Status pushLinkStack(LinkStack &linkStack, ElementType element) {StackNode *newNode = new StackNode;if (!newNode) {return 0;}newNode->data = element;newNode->next = linkStack;linkStack = newNode;return 1;
}

8.出栈

        该方法用于从链栈中弹出栈顶元素。

        链栈出栈过程如下图所示：

        图3.出栈过程

// 出链栈
Status popLinkStack(LinkStack &linkStack, ElementType &element) {if (linkStack == nullptr) {return 0;}StackNode *temp = linkStack;element = temp->data;linkStack = temp->next;delete temp;return 1;
}

9.遍历

        遍历链栈。

// 遍历链栈
void traverseLinkStack(LinkStack linkStack) {StackNode *p = linkStack;while (p != nullptr) {cout << p->data << "\t";p = p->next;}cout << endl;
}

10.完整代码

#include <iostream>
using namespace std;#define ElementType int
typedef int Status;typedef struct StackNode {ElementType data;struct StackNode *next;
} StackNode, *LinkStack;// 初始化链栈
Status initLinkStack(LinkStack &linkStack) {linkStack = nullptr; // 将链栈指针初始化为 nullptrreturn 1;
}// 销毁链栈
void destroyLinkStack(LinkStack &linkStack) {LinkStack p = linkStack;while (p) {LinkStack temp = p;p = p->next;delete temp;}linkStack = nullptr; // 将链栈指针设置为 nullptr
}// 判断链栈是否为空
bool linkStackEmpty(LinkStack linkStack) {return linkStack == nullptr;
}// 获取链栈的长度
int getLinkStackLength(LinkStack linkStack) {int length = 0;StackNode *current = linkStack;while (current != nullptr) {length++;current = current->next;}return length;
}// 获取链栈的栈顶元素
Status getLinkStackTop(LinkStack linkStack, ElementType &element) {if (linkStack == nullptr || linkStack->next == nullptr) {return 0;}element = linkStack->next->data;return 1;
}// 入链栈
Status pushLinkStack(LinkStack &linkStack, ElementType element) {StackNode *newNode = new StackNode;if (!newNode) {return 0;}newNode->data = element;newNode->next = linkStack;linkStack = newNode;return 1;
}// 出链栈
Status popLinkStack(LinkStack &linkStack, ElementType &element) {if (linkStack == nullptr) {return 0;}StackNode *temp = linkStack;element = temp->data;linkStack = temp->next;delete temp;return 1;
}// 遍历链栈
void traverseLinkStack(LinkStack linkStack) {StackNode *p = linkStack;while (p != nullptr) {cout << p->data << "\t";p = p->next;}cout << endl;
}int main() {LinkStack linkStack = nullptr; // 初始化链栈指针为 nullptrcout << "链栈初始化......" << endl;if (initLinkStack(linkStack)) {cout << "链栈初始化成功" << endl;} else {cout << "链栈初始化失败" << endl;}// 示例入栈操作pushLinkStack(linkStack, 1);pushLinkStack(linkStack, 2);pushLinkStack(linkStack, 3);// 遍历并输出栈中元素cout << "链栈中的元素为：";traverseLinkStack(linkStack);// 输出链栈长度cout << "链栈的长度为：" << getLinkStackLength(linkStack) << endl;// 输出栈顶元素ElementType topElement;if (getLinkStackTop(linkStack, topElement)) {cout << "链栈的栈顶元素为：" << topElement << endl;}// 出栈并输出结果cout << "出栈操作：" << endl;ElementType poppedElement;while (popLinkStack(linkStack, poppedElement)) {cout << "出栈元素：" << poppedElement << endl;}// 测试销毁链栈destroyLinkStack(linkStack);if (linkStackEmpty(linkStack)) {cout << "链栈已销毁" << endl;}return 0;
}