当前位置：首页 > news >正文

C语言栈详解

news 2025/5/29 10:17:09

一、什么是栈？

栈（Stack）是一种后进先出（LIFO, Last In First Out）的线性数据结构。它只允许在一端（栈顶）进行插入和删除操作。常见于函数调用、表达式求值、括号匹配、撤销操作等场景。

二、栈的结构定义

在C语言中，常用顺序表（动态数组）实现栈。每个栈结构体包含：

数据区（动态数组）
栈顶指针
容量

// 数据类型定义
typedef int STDatatype;

// 栈结构体
typedef struct Stack {STDatatype* a; // 动态数组int top;       // 栈顶指针，指向栈顶元素的下一个位置int capacity;  // 当前容量
} ST;

三、栈的基本操作

1. 初始化栈

// 初始化栈
void StackInit(ST* ps)
{assert(ps);ps->a = NULL; ps->top = 0; // -1//初始化时，top给的是0，意味着top指向栈顶数据的下一个//初始化时，top给的是-1，意味着top指向栈顶数据ps->capacity = 0;
}

2. 销毁栈

//销毁栈
void StackDestroy(ST* ps)
{assert(ps);if (ps->a){free(ps->a);}ps->a = NULL;ps->top = 0;ps->capacity = 0;
}

3. 入栈（Push）

图解：

代码实现：

//入栈
void StackPush(ST* ps, STDatatype x)
{assert(ps);// 检查空间够不够，不够就增容if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//三目运算符，如果capacity==0成立则返回4，不成立则capacity*2STDatatype* tmp = realloc(ps->a, sizeof(STDatatype) * newcapacity);if (tmp == NULL){printf("rellaoc fail\n");exit(-1);}ps->a = tmp;ps->capacity = newcapacity;}ps->a[ps->top] = x;ps->top++;
}

4. 出栈（Pop）

图解：

代码实现：

//出栈
void StackPop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));--ps->top;
}

5. 获取栈顶元素

// 获取栈顶元素
STDatatype StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->a[ps->top - 1];
}

6. 获取栈中有效元素个数

// 获取栈中有效元素个数
int StackSize(ST* ps)
{assert(ps);return ps->top;
}

7. 判断栈是否为空

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;//return表达式，表达式为真返回true，表达式为假返回false
}

四、完整示例

头文件：

#pragma once
#include<assert.h>
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>// 静态
//#define N 100
//typedef int STDatatype;
//struct Stack
//{
//	STDatatype a[N];
//	int top;    // 栈顶
//};typedef int STDatatype;
typedef struct Stack
{STDatatype* a;int top;		// 栈顶int capacity;   //容量空间大小
}ST;
// 初始化栈
void StackInit(ST* ps);
//销毁栈
void StackDestroy(ST* ps);
//入栈
void StackPush(ST* ps, STDatatype x);
//出栈
void StackPop(ST* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(ST* ps);
// 获取栈中有效元素个数
int StackSize(ST* ps);
// 获取栈顶元素
STDatatype StackTop(ST* ps);

.c文件

#include "Stack.h"
// 初始化栈
void StackInit(ST* ps)
{assert(ps);ps->a = NULL; ps->top = 0; // -1//初始化时，top给的是0，意味着top指向栈顶数据的下一个//初始化时，top给的是-1，意味着top指向栈顶数据ps->capacity = 0;
}
//销毁栈
void StackDestroy(ST* ps)
{assert(ps);if (ps->a){free(ps->a);}ps->a = NULL;ps->top = 0;ps->capacity = 0;
}
//入栈
void StackPush(ST* ps, STDatatype x)
{assert(ps);// 检查空间够不够，不够就增容if (ps->top == ps->capacity){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//三目运算符，如果capacity==0成立则返回4，不成立则capacity*2STDatatype* tmp = realloc(ps->a, sizeof(STDatatype) * newcapacity);if (tmp == NULL){printf("rellaoc fail\n");exit(-1);}ps->a = tmp;ps->capacity = newcapacity;}ps->a[ps->top] = x;ps->top++;
}
//出栈
void StackPop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));--ps->top;
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;//return表达式，表达式为真返回true，表达式为假返回false
}
// 获取栈中有效元素个数
int StackSize(ST* ps)
{assert(ps);return ps->top;
}
// 获取栈顶元素
STDatatype StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->a[ps->top - 1];
}

测试文件：

#include "Stack.h"void test()
{ST st;StackInit(&st);StackPush(&st, 1);StackPush(&st, 2);StackPush(&st, 3);StackPush(&st, 4);while (!StackEmpty(&st))//取栈中的所有元素{printf("%d ", StackTop(&st));//取栈顶元素StackPop(&st);}printf("\n");
}int main()
{test();return 0;
}