一、栈的基本概念
栈（Stack）是一种数据结构，它遵循“后进先出”（LIFO, Last In First Out）的原则。这意味着最后一个插入栈的元素最先被删除，你可以理解成一堆盘子，每次只能取最上面的盘子，删除的时候也只能删除最上面的盘子。这样是不是更容易理解了呢？栈的基本操作包括：
- 入栈（Push）：将一个元素压入栈顶。
- 出栈（Pop）：将栈顶元素弹出并返回该元素。
- 查看栈顶元素（Top）：返回栈顶元素的值，但不弹出该元素。
- 获取栈的大小（Size）：返回栈中元素的个数。
- 栈的创建和销毁：创建一个新的空栈并初始化，销毁栈时释放所有元素的内存。
栈有两种主要的实现方式：数组（顺序栈）和链表（链式栈）。本文将重点介绍链式栈的实现方式。
二、链式栈的实现
链式栈利用链表实现，栈顶对应链表的头结点。每个结点包含一个数据域和一个指向下一个结点的指针。栈的操作在链表的头部进行，具体来说：
- 入栈操作：每次添加新元素时，新元素成为链表的头结点。新的头结点指向原来的头结点。
- 出栈操作：每次删除元素时，删除的是链表的头结点。删除后，原头结点的下一个结点成为新的头结点。
三、栈的结构定义
我们首先定义栈中元素的类型，以及链表结点和栈的结构体。
#include <stdio.h>
#include <stdlib.h>
// 定义栈中元素的类型
#define eleType int
// 定义链表结点的结构体
typedef struct Node
{
eleType data; // 数据域
struct Node* next; // 指针域
} Node;
// 定义栈的结构体
typedef struct
{
Node* head; // 栈顶指针
size_t size; // 栈的大小
} stack;
eleType定义了栈中元素的类型，这里我们定义为int类型。你可以根据需要修改为其他类型。Node结构体表示链表的结点，每个结点包含一个数据域和一个指向下一个结点的指针。stack结构体表示栈，包含一个指向栈顶结点的指针head和栈的大小size。
四、栈的创建
栈的创建函数用于初始化栈，使其处于空状态。
// 栈的创建函数
void StackCreate(stack* stk)
{
stk->head = NULL; // 初始化栈顶指针为NULL
stk->size = 0; // 初始化栈的大小为0
}
StackCreate函数接收一个指向stack结构体的指针stk，将stk的head初始化为NULL，表示栈为空。- 同时，将
stk的size初始化为0，表示栈的元素个数为零。
五、栈的销毁
栈的销毁函数用于释放栈中所有结点的内存，并将栈重置为初始状态。
// 栈的销毁函数
void StackDestroy(stack* stk)
{
while (stk->head) // 从头结点开始遍历，直到空结点
{
Node* next = stk->head->next; // 将头结点的后继结点存入到next变量中
free(stk->head); // 释放头结点所占空间
stk->head = next; // 将栈的头结点更新为next
}
stk->size = 0; // 重置栈的大小为0
}
StackDestroy函数接收一个指向stack结构体的指针stk，循环遍历栈中的每个结点。- 在循环中，保存当前结点的下一个结点指针，释放当前结点的内存，然后将栈顶指针
head更新为下一个结点。 - 最后，将
size重置为0，表示栈已被清空。
六、入栈操作
入栈操作将一个新元素添加到栈顶。（一盘碟子上面加碟子doge~）
// 入栈函数
void StackPush(stack* stk, eleType element)
{
Node* newNode = (Node*)malloc(sizeof(Node)); // 创建动态链表结点
newNode->data = element; // 将元素element赋值给data成员变量
newNode->next = stk->head; // 将next结点指向栈当前的头结点
stk->head = newNode; // 更新头结点为newNode
stk->size++; // 更新栈的大小加1
}
StackPush函数接收一个指向stack结构体的指针stk和一个元素element。- 创建一个新的结点
newNode，将element赋值给newNode的数据域data。 - 将
newNode的指针域next指向当前的栈顶结点head。 - 将
stk的head更新为newNode，表示新结点成为栈顶。 - 将
size加1，更新栈的大小。
七、出栈操作
出栈操作将栈顶元素移除，并返回该元素的值。（把最上面的碟子取下来doge~）
// 出栈函数
eleType StackPop(stack* stk)
{
if (stk->size == 0)
{
printf("Stack underflow!\n");
exit(1); // 判断栈是否为空，如果为空，退出程序
}
eleType result = stk->head->data; // 获取栈顶元素
Node* next = stk->head->next; // 保存下一个结点
free(stk->head); // 释放当前栈顶结点
stk->head = next; // 更新栈顶指针
stk->size--; // 栈的大小减1
return result; // 返回栈顶元素
}
StackPop函数接收一个指向stack结构体的指针stk。- 首先检查栈是否为空，如果
size为0，打印错误信息并退出程序。 - 获取当前栈顶元素的数据域
data并保存到result。 - 保存当前栈顶结点的下一个结点指针
next。 - 释放当前栈顶结点的内存。
- 将
stk的head更新为next，即栈顶指针指向下一个结点。 - 将
size减1，更新栈的大小。 - 返回保存的栈顶元素
result。
八、获取栈顶元素
该函数用于返回栈顶元素的值，但不移除该元素。
// 获取栈顶元素函数
eleType StackTop(stack* stk)
{
if (stk->size == 0)
{
printf("Stack is empty!\n");
exit(1); // 判断栈是否为空，如果为空，退出程序
}
return stk->head->data; // 返回栈顶元素
}
StackTop函数接收一个指向stack结构体的指针stk。- 首先检查栈是否为空，如果
size为0，打印错误信息并退出程序。 - 返回当前栈顶结点的数据域
data。
九、获取栈的大小
该函数用于返回栈中元素的个数。
// 获取栈的大小函数
int StackSize(stack* stk)
{
return stk->size; // 返回栈的大小
}
StackSize函数接收一个指向stack结构体的指针stk。- 返回栈的大小
size。
十、示例代码
我们通过一个示例来展示如何使用上述函数来操作栈。
int main()
{
stack stk;
StackCreate(&stk);
StackPush(&stk, 10);
StackPush(&stk, 20);
StackPush(&stk, 30);
printf("Stack top element: %d\n", StackTop(&stk));
printf("Stack size: %d\n", StackSize(&stk));
printf("Popped element: %d\n", StackPop(&stk));
printf("Stack top element: %d\n", StackTop(&stk));
printf("Stack size: %d\n", StackSize(&stk));
StackDestroy(&stk);
printf("Stack size after destroy: %d\n", StackSize(&stk));
return 0;
}
- 创建一个栈
stk并初始化。 - 将
10,20,30三个元素依次压入栈。 - 获取并打印栈顶元素和栈的大小。
- 弹出一个元素并打印弹出的元素、当前栈顶元素和栈的大小。
- 销毁栈并打印销毁后的栈的大小。
输出结果：
Stack top element: 30
Stack size: 3
Popped element: 30
Stack top element: 20
Stack size: 2
Stack size after destroy: 0
总结
通过定义链表结点和栈结构体，我们能够创建、销毁、入栈、出栈、查看栈顶元素以及获取栈的大小。使用链表实现栈的关键在于对头结点的操作：
- 入栈：每次添加新元素时，我们创建一个新的结点并将其设为新的头结点，新结点指向原来的头结点。
- 出栈：每次删除元素时，我们删除当前的头结点，更新头结点为下一个结点。
这种实现方式充分利用了链表的动态内存分配特性，使得栈操作简单且高效。
希望对大家有所帮助，求赞支持一下~
标签：结点,实现,元素,栈顶,head,stk,链式,C语言,size From： https://blog.csdn.net/Broken_x/article/details/139476146