一.栈的概念及结构
1.1栈的概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作；进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守 后进先出 的原则；
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶；
出栈：栈的删除操作叫做出栈。出数据也在栈顶；
1.2栈的结构
入数据和出数据都是从栈顶入和出；保持后进先出的原则*
1.3栈的实现
栈的实现：数组和链表都可以用来实现栈，保证先进后出原则；
数组：尾插就是进栈 尾删就是出栈（相比链表较为方便）
我这里定义的是Top指向的是栈顶元素的下一个位置
链表：可以选择头插进栈 头删出栈
如果选择的是尾插和尾删的话，需要找尾灯操作，不方便
1.4栈的实现
数组实现栈（相对于链表，数组实现栈更优）
1.4.1功能函数的实现
一般的栈需要完成这几个函数
- 栈的初始化
- 栈的销毁
- 入栈
- 出栈
- 取栈顶元素
- 判断栈是否为空
void StackInit(ST* st); void StackDestory(ST* st); void StackPush(ST* st, STDateType x); void StackPop(ST* st); STDateType GetTop(ST* st); bool StackEmpty(ST* st);
1.定义一个栈的结构体
这里我们实现的是动态的栈 typedef int STDateType; //方便数据类型的替换 typedef struct Stack { STDateType* a; //存储数据的数组 int top; int capacity; //容量 }ST;
2.栈的初始化
这里top的初始化不同，top含义就不同； 1.如果top初始化给0，则每次入栈后top就会++；当入第一个数据时，top++后为1，则top含义为指向的是栈顶元素的下一个元素 2.如果top初始化为-1，则含义为指向栈顶元素 void StackInit(ST* st) { assert(st); st->a = (STDateType* )malloc(4 * sizeof(STDateType)); if (st->a == NULL) { perror("malloc fail"); exit(-1); } st->top = 0; //指向栈顶元素的下一个位置 st->capacity = 4; //初始容量给4 }
3.入栈函数
void StackPush(ST* st, STDateType x) { assert(st); if (st->top == st->capacity) //扩容逻辑与顺序表一样 { //扩容 STDateType* tmp = (STDateType* )realloc(st->a,sizeof(STDateType) * st->capacity *2); if (tmp == NULL) { perror("malloc fail"); exit(-1); } st->a = tmp; st->capacity *= 2; //2倍扩容 } st->a[st->top] = x; //尾插数据 st->top++; }
4.出栈函数
直接将top--；top--后虽然数据没有改变，但是在下一次入栈时会将原数据给覆盖 void StackPop(ST* st) { assert(st); st->top--; }
5.获取栈顶元素
STDateType GetTop(ST* st) { assert(st); assert(st->top); //断言 return st->a[st->top - 1]; //直接返回top后一个位置的元素 }
6.判断栈是否为空
bool StackEmpty(ST* st) { assert(st); return st->top; //返回栈的top,如果为0则为空 非0则不为空； }
7.栈的销毁函数
void StackDestory(ST* st) { assert(st); free(st->a); //释放开辟的空间 st->capacity = st->top = 0; //置空 }
1.5总代码
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int STDateType; typedef struct Stack { STDateType* a; int top; int capacity; }ST; void StackInit(ST* st); void StackDestory(ST* st); void StackPush(ST* st, STDateType x); void StackPop(ST* st); STDateType GetTop(ST* st); bool StackEmpty(ST* st);
#include"Stack.h" void StackInit(ST* st) { assert(st); st->a = (STDateType* )malloc(4 * sizeof(STDateType)); if (st->a == NULL) { perror("malloc fail"); exit(-1); } st->top = 0; st->capacity = 4; } void StackPush(ST* st, STDateType x) { assert(st); if (st->top == st->capacity) { //扩容 STDateType* tmp = (STDateType* )realloc(st->a,sizeof(STDateType) * st->capacity *2); if (tmp == NULL) { perror("malloc fail"); exit(-1); } st->a = tmp; st->capacity *= 2; } st->a[st->top] = x; st->top++; } void StackPop(ST* st) { assert(st); st->top--; } STDateType GetTop(ST* st) { assert(st); assert(st->top); return st->a[st->top - 1]; } bool StackEmpty(ST* st) { assert(st); return st->top; } void StackDestory(ST* st) { assert(st); free(st->a); st->capacity = st->top = 0; }
