栈
引入
介绍
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）
的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
为什么栈用顺序表而不用数组？
由于栈只用在同一端进行插入和删除，因此我们优先选择使用顺序表，因为在顺序表的末尾插入和删除的时间复杂度都是O(1)，并且操作简单
栈的实现
stack.h：结构体，栈的声明与定义
typedef int STDatatype; typedef struct stack { STDatatype* a; int top; //栈顶 int capacity; //容量 }ST; //栈的初始化 void STInit(ST* ps); //栈的销毁 void STDestroy(ST* ps); //压入 void STPush(ST* ps, STDatatype x); //弹出/出栈 void STPop(ST* ps); //取栈顶元素 STDatatype STTPop(ST* ps); //栈的大小 int STSize(ST* ps); //判断栈是否为空 bool STEmpty(ST* ps);
stack.c：栈的具体实现代码
栈的初始化
void STInit(ST* ps) { assert(ps); ps->a = NULL; ps->top = 0; ps->capacity = 0; }
压入
void STPush(ST* ps, STDatatype x) { assert(ps); //如果栈顶 = 容量，满了 if (ps->top == ps->capacity) { //扩容 int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; STDatatype* tmp = (STDatatype*)realloc(ps->a, newcapacity * sizeof(STDatatype)); if (tmp == NULL) { perror("realloc"); return; } //赋值 ps->a = tmp; ps->capacity = newcapacity; } //新数据给值 ps->a[ps->top] = x; ps->top++; }
弹出
void STPop(ST* ps) { assert(ps); //判断栈是否为空 assert(!STEmpty(ps)); //栈顶元素删除 ps->top--; }
取栈顶元素
STDatatype STTPop(ST* ps) { assert(ps); //判断栈是否为空 assert(!STEmpty(ps)); return ps->a[ps->top - 1];//栈顶元素下标 }
栈的大小
int STSize(ST* ps) { assert(ps); return ps->top; }
判断栈是否为空
bool STEmpty(ST* ps) { assert(ps); //为空返回True,不为空返回False return ps->top == 0; }
栈的销毁
void STDestroy(ST* ps) { //判断穿的指针是否有效 assert(ps); //先释放，后置空 free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; }
Test.c：栈的测试
int main() { ST st; //初始化 STInit(&st); //压入 STPush(&st, 1);//1 STPush(&st, 2);//1 2 STPush(&st, 3);//1 2 3 STPush(&st, 4);//1 2 3 4 //取栈顶元素 int top = STTPop(&st);//4 //printf("%d ", top);//4 //弹出 STPop(&st);//1 2 3 //压入 STPush(&st, 5);//1 2 3 5 STPush(&st, 6);//1 2 3 5 6 while (!STEmpty(&st))//栈不为空 { int top = STTPop(&st);//6 5 3 2 1 printf("%d ", top); //6 5 3 2 1 STPop(&st); } //摧毁 STDestroy(&st); return 0; }
队列
引入
介绍
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
为什么队列选择链表而不用数组？
由于队列需要在队列两端进行插入或删除，因此我们优先选择链表来进行实现。当然使用数组实现也可以，只是数组在头部插入和删除元素需要O(n)的时间复杂度，因此选择链表更优。
队列实现
Queue.h：结构体，队列的声明和定义
#pragma once #define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int QueDatatype; typedef struct QueueNode { int val; struct QueueNode* next; }QNode; typedef struct Queue { QNode* phead; QNode* ptail; int size; }Que; //队列初始化 void QueueInit(Que* pq); //队列销毁 void QueueDestroy(Que* pq); // 队尾入队列 void QueuePush(Que* pq, QueDatatype x); // 队头出队列 void QueuePop(Que* pq); //获取队列头部元素 QueDatatype QueueFront(Que* pq); //获取队列尾部元素 QueDatatype QueueBack(Que* pq); //判断队列中有效元素 bool QueueEmpty(Que* pq); //队列中有效元素个数 int QueueSize(Que* pq);
Queue.c：队列函数具体实现
队列初始化
void QueueInit(Que* pq) { assert(pq); //一开始队列为空 pq->phead = NULL; pq->ptail = NULL; pq->size = 0; //队列大小 }
队尾入队列（数据）
void QueuePush(Que* pq, QueDatatype x) { assert(pq); //扩容 QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc"); return; } //给值 newnode->val = x; newnode->next = NULL; //队列不止一个元素 if (pq->ptail) { pq->ptail->next = newnode; pq->ptail = newnode; } //队列只有一个元素 else { pq->phead = pq->ptail = newnode; } pq->size++; }
队头出队列（数据）
void QueuePop(Que* pq) { assert(pq); assert(pq->phead); //队列中不止一个元素 if (pq->phead->next == NULL) { free(pq->phead); pq->phead = pq->ptail = NULL; } //队列中只有一个元素 else { //先记录队头的下一个元素 QNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } pq->size--; }
获取队列头部元素
QueDatatype QueueFront(Que* pq) { assert(pq); //判断队列是否为空 assert(pq->phead); return pq->phead->val; }
获取队列尾部元素
QueDatatype QueueBack(Que* pq) { assert(pq); //判断队列是否为空 assert(pq->ptail); return pq->ptail->val; }
判断队列是否为空
bool QueueEmpty(Que* pq) { assert(pq); //为空返回True，不为空返回False return pq->size == 0; }
队列中有效元素个数
int QueueSize(Que* pq) { assert(pq); return pq->size;//队列大小 }
队列销毁
void QueueDestroy(Que* pq) { assert(pq); QNode* cur = pq->phead; //依次释放节点 while (cur) { QNode* next = cur->next; free(cur); cur = next; } //置为空 pq->phead = pq->ptail = NULL; pq->size = 0; }
Test.c：队列的测试
#include"Queue.h" int main() { Que q; //初始化 QueueInit(&q); //队尾进入队列 QueuePush(&q, 1);//1 QueuePush(&q, 2);//1 2 QueuePush(&q, 3);//1 2 3 QueuePush(&q, 4);//1 2 3 4 printf("%d ", QueueFront(&q));//1 printf("%d ", QueueBack(&q));//4 //对头出队列 QueuePop(&q);//2 3 4 printf("%d ", QueueFront(&q));//2 printf("%d ", QueueBack(&q));//4 printf("%d", QueueSize(&q));//3 //while (!QueueEmpty(&q)) //{ // printf("%d ", QueueFront(&q)); // QueuePop(&q); //} //销毁 QueueDestroy(&q); return 0; }
