江西建设工程信息网站深圳市住房和城乡建设局
简介
- 栈是一种数据结构
- 栈可以用来存放数字
- 一次只能向栈里加入一个数字，一次也只能从栈里获得一个数字
- 栈里到的数字有前后顺序，先进入到的数字在前，后进入的数字在后
- 每次从栈里获取的数字一定是最后面的数字，最后获取的数字一定是最前面的数字
- 这种取数字的方法叫先进后出，后进先出
下面是它存储数据的过程
下面是它取出这三个数据的过程
上面两幅图展示了栈存储数据和取出数据的一个过程，体现了先进后出，后进先出这个特性。
代码实现
以下就是创建栈的数据结构，并且实现其功能的相关函数。
- 定义栈
typedef struct stack{int *arr; // 分配存储区的首地址int cap; // 栈中的元素个数int top; // 入栈和出栈的位置
}stack_t;
- 初始化栈
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
}
- 释放栈
void stack_deinit(stack_t* pstack){// 释放内存，并重置为0和NULLfree(pstack->arr);pstack->arr = NULL;pstack->cap = 0;pstack->top = 0;
}
- 压栈
void stack_push(stack_t* pstack, int data){// 将传入的数据放到栈中pstack->arr[pstack->top++] = data; // 先将数据放入索引为top的位置，然后将top++，往后移
}
- 出栈
int stack_pop(stack_t* pstack){// 当栈中有数据时，此时top肯定是指向最后一个传进去的数据后一个，此时只需将top--，之后再将数据取出即可return pstack->arr[--pstack->top];
}
- 判断栈是否已满
int stack_full(stack_t* pstack){// 因为top索引是从0开始的，有一个数据进来，top就加1，所以top的值就是当前栈中元素的个数，当它等于cap时，说明栈满了return pstack->top >= pstack->cap; // 满了返回真(非0)，没满返回假(0)
}
- 判断栈是否为空
int stack_empty(stack_t* pstack){// 参考第6条，top的值就是当前栈中元素的个数，top值为0说明为空return pstack->top == 0; // 为空返回真(非0)，不为空返回假(0)
}
- 获取栈中的元素个数
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;
}