后进先出—栈
什么是栈？
栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
什么是后进先出？
一图让你明白~
栈的实现？
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。但是由于数组是在定义完后对于空间是固定的，因此如果单纯用数组实现，如果申请空间过大会浪费空间，太小又会造成空间不够的问题，因此，本文采用支持动态增长的栈，也就是动态开辟空间的方法。
对此，我们先了解一下咱们栈的操作
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
栈实现需要设置的参数 ？
由于咱们要实现的是动态扩容因此定义如下：
// 支持动态增长的栈 typedef int STDataType; typedef struct Stack { STDataType* _a; int _top; // 栈顶 int _capacity; // 容量 }Stack;
此处对于相关栈所定义的元素进行解释：
1、 STDataType* _a 作为动态扩容的作用。
2、int _top 作为记录栈顶位置的作用。
3、int _capacity 作为记录栈容量的作用。
啥意思呢？
一图让你明白~
要实现的功能？
同我们之前所学的链表、线性表一样，需要实现基本的增、删、查、改！但是需要注意的是，我们的查与修只能在固定的一端进行！而不能进行改的操作！对此我们写出相应的接口函数。
// 初始化栈 void StackInit(Stack* ps); // 入栈 void StackPush(Stack* ps, STDataType data); // 出栈 void StackPop(Stack* ps); // 获取栈顶元素 STDataType StackTop(Stack* ps); // 获取栈中有效元素个数 int StackSize(Stack* ps); // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 int StackEmpty(Stack* ps); // 销毁栈 void StackDestroy(Stack* ps);
栈的C语言代码实现
初始化
void StackInit(Stack* ps) { assert(ps); ps->_a = NULL; ps->_capacity = 0; ps->_top = -1; }
注意：解释一下为什么这里top要设置成-1，主要是因为后续的操作中，比如：判空的操作的差异、在入栈时操作的差异，当然，top也可以设置成0，但后续的操作会有所差异。
入栈
void StackPush(Stack* ps, STDataType data) { assert(ps); if (ps->_capacity - 1 == ps->_top)//匹配上初始化top=-1 { int newcap = ps->_capacity == 0 ? MAX : ps->_capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->_a, newcap*sizeof(STDataType)); if (tmp == NULL) { perror("realloc fail"); return; } ps->_capacity = newcap; ps->_a = tmp; } ps->_a[++ps->_top] = data; }
入栈时首先判断空间是否足够，如果不够则扩容，够则直接入栈
判空
int StackEmpty(Stack* ps) { assert(ps); return ps->_top==-1; }
出栈
void StackPop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); ps->_top--; }
取栈顶元素
void StackPop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); ps->_top--; }
计算栈内数据个数
int StackSize(Stack* ps) { assert(ps); return ps->_top+1; }
销毁栈
void StackDestroy(Stack* ps) { assert(ps); free(ps->_a); ps->_a = NULL; }
栈的整体代码
头文件
#pragma once #define _CRT_SECURE_NO_WARNINGS 01 #define MAX 4 #include<stdio.h> #include<stdlib.h> #include<assert.h> // 支持动态增长的栈 typedef int STDataType; typedef struct Stack { STDataType* _a; int _top; // 栈顶 int _capacity; // 容量 }Stack; // 初始化栈 void StackInit(Stack* ps); // 入栈 void StackPush(Stack* ps, STDataType data); // 出栈 void StackPop(Stack* ps); // 获取栈顶元素 STDataType StackTop(Stack* ps); // 获取栈中有效元素个数 int StackSize(Stack* ps); // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 int StackEmpty(Stack* ps); // 销毁栈 void StackDestroy(Stack* ps);
函数实现
#include "stack.h" void StackInit(Stack* ps) { assert(ps); ps->_a = NULL; ps->_capacity = 0; ps->_top = -1; } void StackPush(Stack* ps, STDataType data) { assert(ps); if (ps->_capacity - 1 == ps->_top) { int newcap = ps->_capacity == 0 ? MAX : ps->_capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->_a, newcap*sizeof(STDataType)); if (tmp == NULL) { perror("realloc fail"); return; } ps->_capacity = newcap; ps->_a = tmp; } ps->_a[++ps->_top] = data; } void StackPop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); ps->_top--; } STDataType StackTop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->_a[ps->_top]; } int StackSize(Stack* ps) { assert(ps); return ps->_top+1; } int StackEmpty(Stack* ps) { assert(ps); return ps->_top==-1; } void StackDestroy(Stack* ps) { assert(ps); free(ps->_a); ps->_a = NULL; }
测试用例
#include"stack.h" void test() { Stack st; StackInit(&st); StackPush(&st, 1); StackPush(&st, 2); StackPush(&st, 3); StackPop(&st); StackPush(&st, 4); StackPush(&st, 5); printf("%d\n", StackSize(&st)); while (!StackEmpty(&st)) { printf("%d ", StackTop(&st)); StackPop(&st); } printf("\n%d\n", StackSize(&st)); StackDestroy(&st); } int main() { test(); return 0; }
测试结果：
先进先出—队列
什么是队列？
队列只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头。
什么是先进先出？
相信在前面了解过后进先出的你应该有一定的概念了，一图让你明白~
队列的实现？
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
队列的实现需要设置的参数？
根据链表的定义如下：
typedef int QDataType; // 链式结构：表示队列 typedef struct QListNode { struct QListNode* _next; QDataType _data; }QNode; // 队列的结构 typedef struct Queue { QNode* _front; QNode* _rear; }Queue;
注意：QNode是基本的链表结构，而在QNode的基础上建立的Queue是作为真正的队列的结构，其中 _front 是作为记录队头位置的一个指针，而相应的 _rear 是作为记录队尾位置的一个指针。
一图让你明了~
要实现的功能？
同我们之前所学的链表、线性表一样，需要实现基本的增、删、查、改！但是需要注意的是，增的操作在一端进行，而删的操作在另外一端进行，并且同栈一样不能进行改的操作！对此我们写出相应的接口函数。
// 初始化队列 void QueueInit(Queue* q); // 队尾入队列 void QueuePush(Queue* q, QDataType data); // 队头出队列 void QueuePop(Queue* q); // 获取队列头部元素 QDataType QueueFront(Queue* q); // 获取队列队尾元素 QDataType QueueBack(Queue* q); // 获取队列中有效元素个数 int QueueSize(Queue* q); // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 int QueueEmpty(Queue* q); // 销毁队列 void QueueDestroy(Queue* q);
队列的C语言实现
初始化
void QueueInit(Queue* q) { assert(q); q->_front = NULL; q->_rear = NULL; }
你可能有个问题？为什么需要将两个指针都置空呢？初始化指针是一方面，而最主要的是为了让两个指针在最开始都指向同一个位置，然后头指针（也就是front）是只有在出队时才会移动的！尾指针（也就是rear）是只有在出队时才会移动的！这也是后续判空等操作的关键。
入队列
void QueuePush(Queue* q, QDataType data) { assert(q); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->_next = NULL; newnode->_data = data; if (q->_rear == NULL) { assert(q->_front == NULL); q->_front = q->_rear = newnode; } else { q->_rear->_next = newnode; q->_rear = newnode; } }
入队列时需要判断头、尾指针是否为都为空，以此来确定是在头部插入还是在尾部插入。
判空
int QueueEmpty(Queue* q) { assert(q); return q->_front==NULL&&q->_rear==NULL; }
出队列
void QueuePop(Queue* q) { assert(q); assert(!QueueEmpty(&q)); if (q->_front == q->_rear)//一个节点 { free(q->_front); q->_front = NULL; q->_rear = NULL; } else { QNode* next = q->_front->_next; free(q->_front); q->_front = next; } }
取头节点元素
QDataType QueueFront(Queue* q) { assert(q); assert(!QueueEmpty(&q)); return q->_front->_data; }
计算队列内数据个数
int QueueSize(Queue* q) { QNode* cur = q->_front; int size = 0; if (cur != NULL) { size++; while (cur != q->_rear) { size++; cur = cur->_next; } } return size; }
销毁队列
void QueueDestroy(Queue* q) { assert(q); QNode* cur = q->_front; while (cur) { QNode* next = cur->_next; free(cur); cur = next; } q->_front = NULL; q->_rear = NULL; }
队列的整体代码
头文件
#pragma once #define _CRT_SECURE_NO_WARNINGS 01 #include <stdio.h> #include<stdlib.h> #include<assert.h> typedef int QDataType; // 链式结构：表示队列 typedef struct QListNode { struct QListNode* _next; QDataType _data; }QNode; // 队列的结构 typedef struct Queue { QNode* _front; QNode* _rear; }Queue; // 初始化队列 void QueueInit(Queue* q); // 队尾入队列 void QueuePush(Queue* q, QDataType data); // 队头出队列 void QueuePop(Queue* q); // 获取队列头部元素 QDataType QueueFront(Queue* q); // 获取队列队尾元素 QDataType QueueBack(Queue* q); // 获取队列中有效元素个数 int QueueSize(Queue* q); // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 int QueueEmpty(Queue* q); // 销毁队列 void QueueDestroy(Queue* q);
函数实现
#include "queue.h" void QueueInit(Queue* q) { assert(q); q->_front = NULL; q->_rear = NULL; } void QueuePush(Queue* q, QDataType data) { assert(q); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->_next = NULL; newnode->_data = data; if (q->_rear == NULL) { assert(q->_front == NULL); q->_front = q->_rear = newnode; } else { q->_rear->_next = newnode; q->_rear = newnode; } } void QueuePop(Queue* q) { assert(q); assert(!QueueEmpty(&q)); if (q->_front == q->_rear)//一个节点 { free(q->_front); q->_front = NULL; q->_rear = NULL; } else { QNode* next = q->_front->_next; free(q->_front); q->_front = next; } } QDataType QueueFront(Queue* q) { assert(q); assert(!QueueEmpty(&q)); return q->_front->_data; } QDataType QueueBack(Queue* q) { assert(q); assert(!QueueEmpty(&q)); return q->_rear->_data; } int QueueSize(Queue* q) { QNode* cur = q->_front; int size = 0; if (cur != NULL) { size++; while (cur != q->_rear) { size++; cur = cur->_next; } } return size; } int QueueEmpty(Queue* q) { assert(q); return q->_front==NULL&&q->_rear==NULL; } void QueueDestroy(Queue* q) { assert(q); QNode* cur = q->_front; while (cur) { QNode* next = cur->_next; free(cur); cur = next; } q->_front = NULL; q->_rear = NULL; }1. #i
测试用例
#include"queue.h" void test() { Queue qu; QueueInit(&qu); QueuePush(&qu, 1); QueuePush(&qu, 2); printf("%d\n", QueueBack(&qu)); QueuePush(&qu, 3); QueuePush(&qu, 4); printf("%d\n", QueueSize(&qu)); while(!QueueEmpty(&qu)) { printf("%d ", QueueFront(&qu)); QueuePop(&qu); } printf("\n%d\n", QueueSize(&qu)); QueueDestroy(&qu); } int main() { test(); return 0; }
测试结果：
感谢你耐心的看到这里ღ( ´･ᴗ･` )比心，如有哪里有错误请踢一脚作者o(╥﹏╥)o！
