栈的两种存储结构（顺序存储和链式存储）

骂治并 · 2025-8-10 16:46:57

栈的操作实现

栈的概念

栈是一种后进先出（LIFO）的线性数据结构，只允许在一端（栈顶）进行插入和删除操作。新元素总是添加到栈顶，而删除也总是从栈顶移除最上面的元素。栈常用于函数调用、表达式求值、括号匹配等场景。
代码实现---顺序存储（Array-based Stack）

#include <stdio.h> // 标准输入输出库，用于 printf 等函数
#include <stdbool.h>// 布尔类型库，提供 bool、true、false
#include <stdlib.h> // 标准库，提供 malloc/calloc/free 和 exit 等函数
// 定义栈元素的类型为 int
typedef int DataType_t;
// 定义栈的元素结构体
typedef struct SequenceStack
{
DataType_t *Bottom;
unsigned int Size;
int Top;
} SeqStack_t;
SeqStack_t* SeqStack_init(unsigned int size)
{
//calloc 返回的是 void * 类型指针，可以隐式转换为任何其他指针类型（如 int*、char*），所以强制类型转换不是必须的
SeqStack_t *Manager = (SeqStack_t *)calloc(1,sizeof(SeqStack_t));
if(Manager == NULL){
perror("calloc for Manager is failed!\n");
exit(-1);
}
Manager->Bottom = (DataType_t *)calloc(size,sizeof(DataType_t));
if(Manager->Bottom == NULL){
perror("calloc for stackEelement is failed\n");
free(Manager);
exit(-1);
}
Manager->Size = size;
Manager->Top = -1;//没有元素，初始化为-1，新增一个元素后下标就可以等于0
return Manager;
}
//判断栈是不是满
bool SeqStackIsfull(SeqStack_t *Manager)
{
//假设stacksize是8，Top的值已经为7，则栈满
return (Manager->Top+1 == Manager->Size)?true:false;
}
//判断栈是不是空
bool SeqStackIsEmpty(SeqStack_t *Manager)
{
//Top初始值为-1，下次判断依然是-1则栈是空
return (Manager->Top == -1)?true:false;
}
//入栈
bool SeqStack_Push(SeqStack_t *Manager,DataType_t data)
{
//添加元素需要先判断栈有没有满
if(SeqStackIsfull(Manager)){
printf("SeqStack is Full!\n");
return false;
}
Manager->Bottom[++Manager->Top] = data;
return true;
}
//出栈
DataType_t SeqStack_Pop(SeqStack_t *Manager)
{
if (SeqStackIsEmpty(Manager)) {
printf("SeqStack is Empty!\n");
return;
}
//栈顶元素出栈，Top-1
DataType_t temp = Manager->Bottom[Manager->Top--];
return temp;
}
//遍历栈
void SeqStack_Print(SeqStack_t *Manager)
{
for(int i=0;i<= Manager->Top;i++){
printf("Stack Element[%d] = %d\n",i,Manager->Bottom[i]);
}
}
int main(int argc, char const *argv[])
{
// 初始化大小为 4 的栈
SeqStack_t *stack = SeqStack_init(4);
// 测试空栈出栈
printf("尝试从空栈出栈:\n");
SeqStack_Pop(stack);
// 入栈测试
printf("入栈: 10, 20, 30\n");
SeqStack_Push(stack, 10);
SeqStack_Push(stack, 20);
SeqStack_Push(stack, 30);
// 打印栈
printf("当前栈内容:\n");
SeqStack_Print(stack);
// 测试栈满
printf("继续入栈: 40, 50\n");
SeqStack_Push(stack, 40);
SeqStack_Push(stack, 50); // 应提示栈满
// 出栈两次
printf("出栈两次:\n");
printf("出栈元素: %d\n", SeqStack_Pop(stack));
printf("出栈元素: %d\n", SeqStack_Pop(stack));
// 再打印栈
printf("出栈后内容:\n");
SeqStack_Print(stack);
return 0;
}

复制代码

运行结果

代码实现---链式存储（Linked Stack）

/**
* @fire name:Linkedstack.c
* @brief:/**
* @fire name:SeqList.c
* @brief:这个程序实现栈的入栈、出栈（链式存储）
* @author:13642563766@163.com
* @date:2025/7/18
* @version:1.0
* @note:None
* Copyright (c) 2021-2022 13642563766@163.com All right Reserved
*/
#include <stdio.h>
#include <stdlib.h>
// 定义栈中存储的数据类型为 int
typedef int DataType;
// 链栈的节点结构体：每个节点包含数据和指向下一个节点的指针
typedef struct StackNode {
DataType data;
struct StackNode *next;
}StackNode;
// 链栈管理结构体：用于管理整个栈的状态
typedef struct{
int size;
StackNode *top;// 指向栈顶节点的指针（NULL 表示空栈）
}LinkedStack;
// 为 LinkedStack* 定义别名 Stack，表示一个栈的指针
typedef LinkedStack* Stack;
/**
* 初始化栈
* @param s 指向栈指针的指针（二级指针），用于返回栈的地址
* @return 成功返回 1，失败返回 0
*/
int InitStack(Stack *s)
{
*s = (Stack)malloc(sizeof(LinkedStack));
if(*s == NULL){
return 0;
}
(*s)->top = NULL;
(*s)->size = 0;
return 1;
}
/**
* 入栈操作：将一个新元素压入栈顶
* @param s 栈指针
* @param data 要入栈的数据
* @return 成功返回 1，失败返回 0
*/
int Push(Stack s, DataType data)
{
if (s == NULL) {
return 0; // 指针无效
}
StackNode *newNode = (StackNode*)malloc(sizeof(StackNode));
if (newNode == NULL) {
return 0; // 指针无效
}
// 设置新节点的数据和指针
newNode->next = s->top;/
newNode->data = data;
s->top = newNode;//更新top指向新结点
s->size++;//每入栈一个元素size++
return 1;
}
/**
* 出栈操作：弹出栈顶元素，并通过指针返回其值
* @param s 栈指针
* @param data 用于接收出栈元素值的输出参数
* @return 成功返回 1，栈为空或指针无效返回 0
*/
int Pop(Stack s, DataType *data)
{
if(s == NULL || s->top == NULL){
return 0; // 栈为空或栈指针无效，无法出栈
}
// 保存当前栈顶节点，便于后续释放
StackNode *Temp = s->top;
// 将栈顶指针移动到下一个节点
s->top = s->top->next;
*data = Temp->data;
free(Temp);
s->size--;
return 1;
}
//获得栈顶元素的值
int GetTop(Stack s, DataType *data)
{
if(s == NULL || s->top == NULL){
return 0; // 栈为空或栈指针无效
}
*data = s->top->data;
return 1;
}
int IsEmpty(Stack s)
{
if(s == NULL){
return 1;
}
return(s->top == NULL);
}
/**
* 销毁整个栈，释放所有内存
* @param s 指向栈的指针的指针
*/
void DestroyStack(Stack *s) {
if (s == NULL || *s == NULL) {
return;
}
StackNode *current = (*s)->top;
StackNode *next;
// 逐个释放节点
while (current != NULL) {
next = current->next;
free(current);
current = next;
}
// 释放栈结构本身
free(*s);
*s = NULL; // 防止野指针
}
int main() {
Stack myStack;
DataType value;
// 1. 初始化栈
if (!InitStack(&myStack)) {
printf("初始化栈失败！\n");
return -1;
}
printf("栈初始化成功。\n");
// 2. 入栈操作
printf("入栈: 10, 20, 30\n");
Push(myStack, 10);
Push(myStack, 20);
Push(myStack, 30);
// 3. 查看栈顶元素
if (GetTop(myStack, &value)) {
printf("当前栈顶元素: %d\n", value);
} else {
printf("栈为空，无法获取栈顶元素。\n");
}
// 4. 出栈操作
printf("开始出栈:\n");
while (!IsEmpty(myStack)) {
if (Pop(myStack, &value)) {
printf("弹出: %d\n", value);
}
}
// 5. 再次尝试出栈 (栈已空)
if (Pop(myStack, &value)) {
printf("弹出: %d\n", value);
} else {
printf("栈已空，无法弹出元素。\n");
}
// 6. 销毁栈
DestroyStack(&myStack);
printf("栈已销毁。\n");
return 0;
}

复制代码

运行结果

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

账号		自动登录	找回密码
密码			立即注册

栈的两种存储结构（顺序存储和链式存储）

浏览过的版块

签约作者