1. 栈
1.1 栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈。入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
1.2 栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾插和头删的实际复杂度为O(1)，是非常合适的。
1.3 栈的功能
- 初始化栈
- 销毁栈
- 入栈
- 出栈
- 获取栈顶元素
- 获取栈内有效元素的个数
- 判断栈内是否为空，如果为空返回非0结果，不为空返回0
1.4 栈的功能的实现
（1）定义一个动态增长的栈
typedef int STDataType; typedef struct Stack { STDataType* a; STDataType top;//定义栈顶 size_t capacity;//栈的容量 }ST;
（2）初始化栈
void StackInit(ST* ps) { //初始化空间 ps->a = (STDataType*)malloc(sizeof(STDataType) * 4); if (ps->a == NULL) { printf("malloc fail!\n"); return; } ps->top = 0;//top指向的是栈顶元素的下一个 ps->capacity = 4;//初始化4个空间 }
（3）销毁栈
void StackDestory(ST* ps) { free(ps->a); ps->a = NULL; ps->capacity = 0; ps->top = 0; }
（4）入栈（相当于顺序表的尾插）
void StackPush(ST* ps, STDataType x) { //插入数据之前判断是否增容 if (ps->top == ps->capacity) { STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * sizeof(STDataType) * 2); if (tmp == NULL) { printf("realloc fail!\n"); return; } else { ps->a = tmp; ps->capacity *= 2; } } //注意由于我们定义top=0,这两条语句的顺序不能调换 ps->a[ps->top] = x; ps->top++; }
（5）出栈（相当于顺序表的头删）
void StackPop(ST* ps) { assert(ps);//断言 assert(ps->top>0);//栈空了，就要停止删除 ps->top--; }
（6）获取栈顶元素
STDataType StackTop(ST* ps) { assert(ps);//断言 assert(ps->top > 0);//栈为空时，防止越界 return ps->a[ps->top - 1]; }
（7）获取栈内有效元素的个数
int StackSize(ST* ps) { assert(ps); return ps->top; }
（8）判断栈内是否为空，如果为空返回非0结果，不为空返回0
bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; }
1.5 完整代码
Stack.h
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int STDataType; typedef struct Stack { STDataType* a; STDataType top;//定义栈顶 size_t capacity;//栈的容量 }ST; //初始化栈 void StackInit(ST* ps); //销毁栈 void StackDestory(ST* ps); //从栈顶插入数据 void StackPush(ST* ps, STDataType x); //从栈顶删除数据 void StackPop(ST* ps); //获取栈顶元素 STDataType StackTop(ST* ps); //获取栈内有效元素个数 int StackSize(ST* ps); //判断栈内是否为空，如果为空返回非0结果，不为空返回0 bool StackEmpty(ST* ps);
Stack.c
#define _CRT_SECURE_NO_WARNINGS #include "Stack.h" void StackInit(ST* ps) { //初始化空间 ps->a = (STDataType*)malloc(sizeof(STDataType) * 4); if (ps->a == NULL) { printf("malloc fail!\n"); return; } ps->top = 0;//top指向的是栈顶元素的下一个 ps->capacity = 4;//初始化4个空间 } void StackPush(ST* ps, STDataType x) { //插入数据之前判断是否增容 if (ps->top == ps->capacity) { STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * sizeof(STDataType) * 2); if (tmp == NULL) { printf("realloc fail!\n"); return; } else { ps->a = tmp; ps->capacity *= 2; } } //注意由于我们定义top=0,这两条语句的顺序不能调换 ps->a[ps->top] = x; ps->top++; } void StackPop(ST* ps) { assert(ps);//断言 assert(ps->top>0);//栈空了，就要停止删除 ps->top--; } STDataType StackTop(ST* ps) { assert(ps);//断言 assert(ps->top > 0);//栈为空时，防止越界 return ps->a[ps->top - 1]; } int StackSize(ST* ps) { assert(ps); return ps->top; } bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } void StackDestory(ST* ps) { free(ps->a); ps->a = NULL; ps->capacity = 0; ps->top = 0; }
Test.c
#define _CRT_SECURE_NO_WARNINGS #include "Stack.h" void StackTest() { ST st; StackInit(&st); StackPush(&st, 1); StackPush(&st, 2); StackPush(&st, 3); StackPush(&st, 4); //打印栈内的数据，由于不能破坏栈的后进先出特性， //所以不能直接从头开始遍历打印 while (!StackEmpty(&st)) { //输出栈顶元素，再删除 printf("%d ", StackTop(&st)); StackPop(&st); } StackDestory(&st); } int main() { StackTest(); return 0; }
2. 队列
2.1 队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出
FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
2.2 队列的实现
队列也可以数组和链表的结构实现，使用单链表的结构实现更优一些。
因为如果使用数组的结构，出队列在数组头上出数据，这时需要挪动数据，时间复杂度为O(n)，效率会比较低。
而单链表的尾插和头删的时间复杂度为O（1），十分合适。
2.3 队列的功能
- 初始化队列
- 销毁队列
- 入队列
- 出队列
- 获取队列头部元素
- 获取队列尾部元素
- 获取队列中有效元素的个数
- 判断队列是否为空，为空返回非0，不为空返回0
2.4 队列的功能的实现
（1）定义一个队列
typedef int QTDataType; typedef struct QNode { struct QNode* next; QTDataType data; }QNode; typedef struct Queue { struct QNode* tail; struct QNode* head; }Queue;
（2）初始化队列
void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; }
（3）销毁队列
void QueueDestory(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur-> next; free(cur); cur = next; } pq->head = pq->tail = NULL; }
（4）入队列(相当于单链表的尾插）
void QueuePush(Queue* pq, QTDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { printf("malloc fail!\n"); return; } newnode->data = x; newnode->next = NULL; //没有一个结点 if (pq->tail == NULL) { pq->head = pq->tail = newnode; } //多个节点 else { pq->tail->next = newnode; pq->tail = newnode; } }
（5）出队列（相当于单链表的头删）
void QueuePop(Queue* pq) { assert(pq); assert(pq->head);//防止队列为空 //只有一个节点时，防止tail成为野指针 if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { //保存下一个节点的地址 QNode* next = pq->head->next; free(pq->head); pq->head = next; } }
（6）获取队列头部元素
QTDataType QueueFront(Queue* pq) { assert(pq); assert(pq->head);//防止队列为空 return pq->head->data; }
（7）获取队列尾部元素
QTDataType QueueBack(Queue* pq) { assert(pq); assert(pq->head); return pq->tail->data; }
（8）获取队列中有效元素的个数
int QueueSize(Queue* pq) { assert(pq); int size = 0; QNode* cur = pq->head; while (cur) { size++; cur = cur->next; } return size; }
（9）判断队列是否为空，为空返回非0，不为空返回0
int QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; }
2.5 完整代码
Queue.h
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int QTDataType; typedef struct QNode { struct QNode* next; QTDataType data; }QNode; typedef struct Queue { struct QNode* tail; struct QNode* head; }Queue; //初始化队列 void QueueInit(Queue* pq); //销毁队列 void QueueDestory(Queue* pq); //队尾入队列 void QueuePush(Queue* pq, QTDataType x); //队头出队列 void QueuePop(Queue* pq); //获取队列头部元素 QTDataType QueueFront(Queue* pq); //获取队列尾部元素 QTDataType QueueBack(Queue* pq); //判断队列是否为空，为空返回非0，不为空返回0 int QueueEmpty(Queue* pq); //获取队列中有效元素的个数 int QueueSize(Queue* pq);
Queue.c
#define _CRT_SECURE_NO_WARNINGS #include "Queue.h" void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; } void QueuePush(Queue* pq, QTDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { printf("malloc fail!\n"); return; } newnode->data = x; newnode->next = NULL; //没有一个结点 if (pq->tail == NULL) { pq->head = pq->tail = newnode; } //多个节点 else { pq->tail->next = newnode; pq->tail = newnode; } } void QueuePop(Queue* pq) { assert(pq); assert(pq->head);//防止队列为空 //只有一个节点时，防止tail成为野指针 if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { //保存下一个节点的地址 QNode* next = pq->head->next; free(pq->head); pq->head = next; } } int QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; } QTDataType QueueFront(Queue* pq) { assert(pq); assert(pq->head);//防止队列为空 return pq->head->data; } QTDataType QueueBack(Queue* pq) { assert(pq); assert(pq->head); return pq->tail->data; } int QueueSize(Queue* pq) { assert(pq); int size = 0; QNode* cur = pq->head; while (cur) { size++; cur = cur->next; } return size; } void QueueDestory(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur-> next; free(cur); cur = next; } pq->head = pq->tail = NULL; }
Test.c
#define _CRT_SECURE_NO_WARNINGS #include "Queue.h" void QueueTest() { Queue q; QueueInit(&q); QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); QueuePush(&q, 4); //打印队列内的数据，由于不能破坏队列先进先出的特性， //所以不能直接遍历，需要出一个删一个 while (!QueueEmpty(&q)) { printf("%d ", QueueFront(&q)); QueuePop(&q); } QueueDestory(&q); } int main() { QueueTest(); return 0; }
