🦃一.栈
🐔（1）什么是栈
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈，出数据也在栈顶。
🐣（2）栈的实现：
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。因为栈即插入和删除（入栈和出战栈）都是在线性表的尾部进行操作，数组的尾部的插如和删除的时间复杂度都是 O(1) ,而如果是链式结构，去实现栈结构，针对尾插和尾删的时间复杂度都是 O(n) ,而双向循环带头的链表，虽然可以解决这个问题，但是.......
我们将栈的实现分为以下各个部分：
1.栈的定义 (StactInit)
typedef int STDateType; //数据类型 typedef struct Stact { STDateType* date; //数组 int capacity; //栈的容量 int top; //栈内数据的个数 }ST; ST* StactInit() { ST* Stact = (ST*)malloc(sizeof(ST)); //创建栈的结构 //栈的结构初始化 Stact->capacity = 4; Stact->top = 0; Stact->date = (STDateType*)malloc(sizeof(STDateType)*Stact->capacity); //返回栈 return Stact; }
2.栈的销毁 (StactDestroy)
void StactDestory(ST* Stact) { assert(Stact); //先释放数组申请的空间 free(Stact->date); Stact->date = NULL; Stact->capacity = 0; Stact->top = 0; //在释放栈的结构体空间 free(Stact); }
3.栈的StactPushBank操作 (入栈)
void StactPushBank(ST* Stact, STDateType x) { //断言Stact,当进行Push时，栈结构必须存在(Stact!=NULL)， //如果不存也就是栈是空(Stact==NULL),那Push的操作就是非法的 assert(Stact); //每次对栈的底层是数组，所以每次都要检查是否需要扩容 if (Stact->capacity == Stact->top) { STDateType* tmp = (STDateType*)realloc(Stact->date, Stact->capacity * 2); if (tmp==NULL) { perror("realloc"); exit(-1); } Stact->date = tmp; Stact->capacity *= 2; } //将x入栈，数组的栈内数据的个数加一 Stact->date[Stact->top++] = x; }
4.栈的StactPopBank操作 (出栈)
void StactPopBank(ST* Stact) { assert(Stact); //当栈已经空了，还去出栈就是非法了 assert(!StactEmpty(Stact)); Stact->top--; }
5.栈的 StactTop (得到栈顶元素)
STDateType StactTop(ST* Stact) { assert(Stact); //当栈已经空了，无法获取栈顶元素 assert(!StactEmpty(Stact)); return Stact->date[Stact->top - 1]; }
6.栈的StactSize (元素个数)
int StactSize(ST* Stact) { assert(Stact); return Stact->top; }
7.栈的判空 (StactEmpty)
bool StactEmpty(ST* stact) { assert(stact); //当栈内数据个数为0时，栈为空 return stact->top == 0; }
测试：
void Print(ST* Stact) { assert(Stact); for (int i = 0; i < Stact->top; i++) { printf("%d ", Stact->date[i]); } printf("\n"); } int main() { ST* Stact= StactInit(); StactPushBank(Stact, 100); StactPushBank(Stact, 200); StactPushBank(Stact, 300); StactPushBank(Stact, 400); Print(Stact); printf("StactSize:%d\n",StactSize(Stact)); //Pop一次 StactPopBank(Stact); Print(Stact); printf("StactSize:%d\n", StactSize(Stact)); StactDestory(Stact); return 0; }
🌱（3）.栈的应用
（1）例题
若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）
A 1,4,3,2
B 2,3,4,1
C 3,1,4,2
D 3,4,2,1
答案：C
分析：选项A，1进1出，2进3进4进，4出3出2出，所以出栈顺序1，4，3，2，选项A正确。
选项B，1进2进，2出，3进3出，4进，4出1出，所以出栈顺序2，3，4，1，选项B正确。
选项C，1进2进3进，3出，此时想要出2，就必须先出栈1，所以选项C错误。
选项D，1进2进3进，3出，4进，4出2出1出，所以出栈顺序3，4，2，1，选项D正确。
（2）例题
LeetCode ———— 20. 有效的括号
题目描述：
思路分析：
遇到左括号就进栈，遇到右括号就出栈，将出栈的左括号与右括号进行匹配，如果匹配成功就继续，如果匹配失败就返回false。
//栈结构 typedef char STDateType; typedef struct Stact { STDateType* date; int capacity; int top; }ST; ST* StactInit(); void StactPushBank(ST* Stact, STDateType x); int StactSize(ST* Stact); void StactDestory(ST* Stact); void StactPopBank(ST* Stact); STDateType StactTop(ST* Stact); bool StactEmpty(ST* stact); ST* StactInit() { ST* Stact = (ST*)malloc(sizeof(ST)); Stact->capacity = 4; Stact->top = 0; Stact->date = (STDateType*)malloc(sizeof(STDateType) * Stact->capacity); return Stact; } void StactPushBank(ST* Stact, STDateType x) { assert(Stact); if (Stact->capacity == Stact->top) { STDateType* tmp = (STDateType*)realloc(Stact->date, Stact->capacity * 2); if (tmp == NULL) { perror("realloc"); exit(-1); } Stact->date = tmp; Stact->capacity *= 2; } Stact->date[Stact->top++] = x; } bool StactEmpty(ST* stact) { assert(stact); return stact->top == 0; } STDateType StactTop(ST* Stact) { assert(Stact); assert(!StactEmpty(Stact)); return Stact->date[Stact->top - 1]; } void StactPopBank(ST* Stact) { assert(Stact); assert(!StactEmpty(Stact)); Stact->top--; } void StactDestory(ST* Stact) { assert(Stact); free(Stact->date); Stact->date = NULL; Stact->capacity = 0; Stact->top = 0; free(Stact); } int StactSize(ST* Stact) { assert(Stact); return Stact->top; } bool isValid(char* s) { //创建栈 ST* stact = StactInit(); while (*s) { //遇到左括号进栈 if (*s == '(' || *s == '{' || *s == '[') { StactPushBank(stact, *s); s++; } else { //遇到右括号出栈，如果出栈的括号时， //栈中已经空，此时括号匹配已经失败 if (StactEmpty(stact)) { StactDestory(stact); return false; } //如果栈不为空，出栈的左括号，与遇到的右括号匹配 //如果匹配成功就，继续向后走，匹配失败就返回false char ch = StactTop(stact); StactPopBank(stact); if ((ch == '(' && *s == ')') || (ch == '[' && *s == ']') || ch == '{' && *s == '}') { s++; } else { StactDestory(stact); return false; } } } //当括号匹配匹配完时，如果栈中还有括号， //也就意味着匹配失败。 if (!StactEmpty(stact)) { StactDestory(stact); return false; } StactDestory(stact); return true; }
🌾二.队列
🌲（1）什么是队列
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头。
🌵 (2)队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
1.队列的定义——QueueInit
由于队列是，队尾入数据，队头出数据，为了方便数据的入队，我们除了队头指针，还会设计一个队尾指针。
typedef int QUDateType; typedef struct QueueNode { QUDateType date; struct QueueNode* next; }QueueNode; typedef struct Queue { QueueNode* head; QueueNode* tail; int size; }Queue; void QueueInit(Queue* pque) { assert(pque); pque->head = NULL; pque->tail = NULL; pque->size = 0; } int main() { Queue Q; QueueInit(&Q); return 0; }
2.入队操作——QueuePush
void QueuePush(Queue* pque,QUDateType x) { //断言队列结构，当进行入队操作时，队列结构一定不能为空 assert(pque); //申请空间 QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); if (newnode == NULL) { perror("malloc"); exit(-1); } //赋值 newnode->date = x; newnode->next = NULL; //如果队列为空，此时入队的就是第一个数据，也将是队列的头尾数据 if (pque->head == NULL) { pque->head = pque->tail = newnode; } //如果队列不为空，就将数据连接到队尾巴后面 else { pque->tail->next = newnode; pque->tail = newnode; } //队列中数据个数加一 pque->size++; }
3.队列销毁——QueueDestroy
void QueueDestroy(Queue* pque) { assert(pque); QueueNode* cur = pque->head; while (cur) { QueueNode* nextnode = cur->next; free(cur); cur = nextnode; } pque->head = pque->tail = NULL; }
4.得到对头数据——QueueFront
QUDateType QueueFront(Queue*pque) { assert(pque); assert(!QueueEmpty(pque)); return pque->head->date; }
5.队列判空——QueueEmpty
bool QueueEmpty(Queue* pque) { assert(pque); return pque->head == NULL && pque->tail == NULL; }
6.删除对头数据——QueuePop
void QueuePop(Queue* pque) { assert(pque); //队列结构不能为空 assert(!QueueEmpty(pque)); //删除数据时队列不能为空 //队列中只有一个数据的时候 if (pque->head->next == NULL) { free(pque->head); pque->tail = pque->head = NULL; } //队列中数据个数大于1 else { QueueNode* popnode = pque->head; pque->head = pque->head->next; free(popnode); } //数据个数减一 pque->size--; }
7.得到队尾数据——QueueBack
QUDateType QueueBack(Queue* pque) { assert(pque); assert(!QueueEmpty(pque)); return pque->tail->date; }
8.得到队列中数据个数——QueueSize
int QueueSize(Queue* pque) { assert(pque); return pque->size; }
测试：
int main() { Queue Q; QueueInit(&Q); //插如100 .200 300 ，400 ， QueuePush(&Q, 100); QueuePush(&Q, 200); QueuePush(&Q, 300); QueuePush(&Q, 400); //输出队头数据 printf("%d ", QueueFront(&Q)); //输出队尾数据 printf("%d ", QueueBack(&Q)); //输出队列数据个数 printf("%d \n", QueueSize(&Q)); //输出队列中的数据 while (!QueueEmpty(&Q)) { printf("%d ", Q.head->date); QueuePop(&Q); } //队列销毁 QueueDestroy(&Q); return 0; }
