数据结构-栈（C语言简单实现）

简介

• 栈是一种数据结构
• 栈可以用来存放数字
• 一次只能向栈里加入一个数字，一次也只能从栈里获得一个数字
• 栈里到的数字有前后顺序，先进入到的数字在前，后进入的数字在后
• 每次从栈里获取的数字一定是最后面的数字，最后获取的数字一定是最前面的数字
• 这种取数字的方法叫先进后出，后进先出

下面是它存储数据的过程

下面是它取出这三个数据的过程

上面两幅图展示了栈存储数据和取出数据的一个过程，体现了先进后出，后进先出这个特性。

代码实现

以下就是创建栈的数据结构，并且实现其功能的相关函数。

1. 定义栈

typedef struct stack{int *arr;  // 分配存储区的首地址int cap;  // 栈中的元素个数int top;  // 入栈和出栈的位置
}stack_t;

2. 初始化栈

void stack_init(stack_t* pstack, int cap){pstack->arr = malloc(sizeof(int) * cap);  // 分配内存给存储区if(pstack->arr == NULL){printf("栈的存储区分配失败!\n");return;}pstack->cap = cap;  // 初始化传入的元素个数pstack->top = 0;  // 一开始入栈的索引是在0
}

3. 释放栈

void stack_deinit(stack_t* pstack){// 释放内存，并重置为0和NULLfree(pstack->arr);pstack->arr = NULL;pstack->cap = 0;pstack->top = 0;
}

4. 压栈

void stack_push(stack_t* pstack, int data){// 将传入的数据放到栈中pstack->arr[pstack->top++] = data;  // 先将数据放入索引为top的位置，然后将top++，往后移
}

5. 出栈

int stack_pop(stack_t* pstack){// 当栈中有数据时，此时top肯定是指向最后一个传进去的数据后一个，此时只需将top--，之后再将数据取出即可return pstack->arr[--pstack->top];
}

6. 判断栈是否已满

int stack_full(stack_t* pstack){// 因为top索引是从0开始的，有一个数据进来，top就加1，所以top的值就是当前栈中元素的个数，当它等于cap时，说明栈满了return pstack->top >= pstack->cap;  // 满了返回真(非0)，没满返回假(0)
}

7. 判断栈是否为空

int stack_empty(stack_t* pstack){// 参考第6条，top的值就是当前栈中元素的个数，top值为0说明为空return pstack->top == 0;  // 为空返回真(非0)，不为空返回假(0)
}

8. 获取栈中的元素个数

int stack_size(stack_t* pstack){// 参考第6条，top的值就是当前栈中元素的个数return pstack->top;
}

实例代码

创建三个文件: stack.c，stack.h，main.c

• stack.c定义栈具体的函数

#include "stack.h"// 初始化栈
void stack_init(stack_t* pstack, int cap){pstack->arr = malloc(sizeof(int) * cap);if(pstack->arr == NULL){printf("栈的存储区分配失败!\n");return;}pstack->cap = cap;pstack->top = 0;
}// 释放栈
void stack_deinit(stack_t* pstack){free(pstack->arr);pstack->arr = NULL;pstack->cap = 0;pstack->top = 0;
}// 压栈
void stack_pull(stack_t* pstack, int data){pstack->arr[pstack->top++] = data;
}// 出栈
int stack_pop(stack_t* pstack){return pstack->arr[--pstack->top];
}// 判断栈是否已满
int stack_full(stack_t* pstack){return pstack->top >= pstack->cap;
}// 判断栈是否为空
int stack_empty(stack_t* pstack){return pstack->top == 0;
}// 获取栈中的元素个数
int stack_size(stack_t* pstack){return pstack->top;
}

• stack.h声明栈的相关函数和定义栈

#ifndef __STACK_H  // 头卫士
#define __STACK_H
#include <stdio.h>
#include <stdlib.h>// 定义栈的数据结构
typedef struct stack{int* arr;int cap;int top;
}stack_t;// 声明栈的函数
extern void stack_init(stack_t* pstack, int cap);
extern void stack_deinit(stack_t* pstack);
extern void stack_pull(stack_t* pstack, int data);
extern int stack_pop(stack_t* pstack);
extern int stack_full(stack_t* pstack);
extern int stack_empty(stack_t* pstack);
extern int stack_size(stack_t* pstack);
#endif

• main.c主函数使用栈

#include "stack.h"int main(void){// 1. 声明一个栈: stackstack_t stack;// 2. 初始化stackstack_init(&stack, 5);// 3. 将栈放满数据int data = 100;printf("开始放入数据: ");while(!stack_full(&stack)){// 没满的状态下，放入数据printf("%d ", data);stack_pull(&stack, data++);}printf("结束!\n");printf("此时栈中元素个数为: %d\n\n", stack_size(&stack));// 4. 将栈中的数据一个个取出来printf("开始取出数据: ");while(!stack_empty(&stack)){// 非空的状态，取数据data = stack_pop(&stack);printf("%d ", data);}printf("结束!\n");printf("此时栈中元素个数为: %d\n\n", stack_size(&stack));// 5. 释放栈stack_deinit(&stack);return 0;
}