栈
栈是一种特殊的线性表，其特性是仅能在表尾进行插入或删除的操作，栈中元素的操作是按照后进先出的原则进行，因此栈又称为后进先出线性表（Last In First Out，LIFO数据结构）。
-
栈顶：表尾端称为栈顶
-
栈底：表头端称为栈底
-
空栈：不含任何元素的空表称为空栈
-
出栈：从栈中删除一个元素的操作称为出栈
-
入栈：从栈中增加一个元素的操作称为入栈
顺序栈实现
栈有两种存储实现方法，一种是顺序存储实现，一种链式存储实现。考虑简单性和日常使用方便，这里使用顺序存储的方式实现，链式实现可以参照单链表实现。
实现要点：
1.顺序栈使用动态内存分配连续存储空间，当空间不足时，重新申请扩展。
2.使用栈顶和栈底指针指向栈顶和栈底位置。
3.栈顶指针指向栈顶元素下一个空位置上，因此栈顶指针和栈底指针相等时为空栈。
代码运行结果
输入10个数，后进先出，逆序输出。
请输入数据总个数:10
请依次输入10个整数:0 1 2 3 4 5 6 7 8 9
顺序栈输出结果:9 8 7 6 5 4 3 2 1 0
代码实现
*/
#include <stdio.h>
#include <stdlib.h>
// 栈初始大小
#define STACK_INIT_SIZE 5
// 栈空间增量大小
#define STACK_INCREMENT_SIZE 10
// 定义栈结构
typedef struct {
// 栈底指针
int *base;
// 栈顶指针
int *top;
// 栈大小
int size;
}stack;
// 创建和初始化栈
stack *create_init_stack()
{
// 创建栈结构
stack *s = (stack *)malloc(sizeof(stack));
if(s == NULL)
return NULL;
// 分配栈空间
s->base = (int *)malloc(STACK_INIT_SIZE * sizeof(int));
if(s->base == NULL)
return NULL;
s->size = STACK_INIT_SIZE;
// 初始栈为空
s->top = s->base;
return s;
}
// 入栈
int push(stack *s, int data)
{
if(s == NULL)
return -1;
// 判断是否栈满
if(s->top - s->base >= s->size)
{
s->base = (int *)realloc(s->base, \
(s->size + STACK_INCREMENT_SIZE) * sizeof(int));
if(s->base == NULL)
return -1;
s->top = s->base + s->size;
s->size = s->size + STACK_INCREMENT_SIZE;
}
*(s->top) = data;
s->top++;
return 0;
}
// 出栈
int pop(stack *s, int *data)
{
if(s == NULL || data == NULL)
return -1;
// 判断是否栈空
if(s->top == s->base)
return -1;
*data = *(--s->top);
return 0;
}
// 查看栈中所有元素
// 只要调用出栈操作即可
void print_stack(stack *s)
{
int t;
while(pop(s, &t) != -1)
printf("%d ", t);
printf("\n");
}
// 销毁和释放
void free_stack(stack *s)
{
if(s != NULL)
{
free(s->base);
free(s);
}
}
int main(void)
{
// 创建栈保存数据
stack *s = create_init_stack();
int n,d;
printf("请输入数据总个数:");
scanf("%d", &n);
printf("请依次输入%d个整数:", n);
int i;
for(i=0; i<n; i++)
{
scanf("%d", &d);
push(s, d);
}
printf("顺序栈输出结果:");
print_stack(s);
// 释放内存空间
free_stack(s);
return 0;
}
其实做为一个学习者，有一个学习的氛围跟一个交流圈子特别重要这里我推荐一个C/C++基础交流583650410，不管你是小白还是转行人士欢迎入驻，大家一起交流成长。
网友评论