阅读量:0
目录
1.栈
1.1概念与结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素的操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守先进后出LIFO(Last In First Out)的原则。
压栈：栈的插入操作叫做入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
我们可以理解为给手枪弹匣装子弹，先装进去的子弹最后面才射出去，后装进的子弹先射出去。
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾插数据的时候代价比较小。
1.2栈的实现
#include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> //定义一个栈的结构 typedef int STDatatype; typedef struct stack { STDatatype* data; //数组 int capacity; //栈的空间的大小 int top; //有效数据个数 }ST; //初始化 void STInite(ST* ps); //销毁 void STDestroy(ST* ps); //入栈 void STPush(ST* ps, STDatatype x); //出栈 void STPop(ST* ps); //判断栈是否为空 bool STEmpty(ST* ps); //取栈顶个数 STDatatype STTop(ST* ps); //获取栈顶有效元素的个数 int STSize(ST* ps); 1.2.1定义一个栈的结构
栈的结构的定义和顺序表结构定义一样，在栈中定义一个指针data用于操作数据，然后定义整型变量capacity用于表示栈的空间大小，最后定义一个整型变量top用于表示有效数据个数也就是我们的栈顶。
//定义一个栈的结构 typedef int STDatatype; typedef struct stack { STDatatype* data; //数组 int capacity; //栈的空间的大小 int top; //有效数据个数 }ST; 1.2.2初始化栈
第二步，我们需要初始化栈将指针data置空，将capacity和top置成0，便于后面我们对于栈进行操作。
//初始化 void STInite(ST* ps) { assert(ps); ps->data = NULL; ps->capacity = ps->top = 0; } 1.2.3入栈
我们需要定义一个STPush函数，将栈的结构体的地址和我们要入栈的元素传过去，然后我们需要判断一下栈的空间是否充足，如果不够我们就需要扩容，当栈的空间和栈顶一样大时，我们就需要扩容了我们需要用realloc函数来调整我们栈的空间大小。方法和之前的顺序表一样，就不过多解释了。扩完容之后我们就需要入栈了，和顺序表的尾插是一样的，栈顶就是我们要插入的位置，插入完成后之后栈顶要往后走一个。
//入栈 void STPush(ST* ps, STDatatype x) { assert(ps); //判断一下空间是否充足 if (ps->capacity == ps->top) { //扩容 int newcapacity = ps->capacity == 0 ? 4 : 2 * (ps->capacity); STDatatype* tmp = (STDatatype*)realloc(ps->data, newcapacity * sizeof(STDatatype)); if (tmp == NULL) { perror("realloc fail!"); exit(1); } ps->data = tmp; ps->capacity = newcapacity; } //插入数据 ps->data[ps->top++] = x; }1.2.4出栈
出栈相当于顺序表的尾删，我们需要定义一个STPop函数将栈结点的地址传过去，然后我们需要判断一下栈是否为空创建一个STEmpty函数，函数返回值为bool类型，当栈顶为0时栈为空。判断完之后，我们就要进行出栈也就是顺序表的尾删，将栈顶--就好了。
//判断栈是否为空 bool STEmpty(ST* ps) { assert(ps); return ps->top == 0; } //出栈 void STPop(ST* ps) { assert(ps); //判断栈是否为空 assert(!STEmpty(ps)); --ps->top; }1.2.5取栈顶元素
我们需要定义一个函数STDatatype STTop（ST* ps）；然后，要判断栈是否为空，最后我们将栈的最后一个元素返回就完成了。
//取栈顶元素 STDatatype STTop(ST* ps) { assert(ps); //判断栈是否为空 assert(!STEmpty(ps)); return ps->data[ps->top - 1 ]; }1.2.6获取栈中有效元素个数
直接返回top的值就行了。
//获取栈顶有效元素的个数 int STSize(ST* ps) { assert(ps); return ps->top; } 1.2.7销毁栈
和销毁顺序表一样。
//销毁 void STDestroy(ST* ps) { assert(ps); if (ps->data) { free(ps->data); } ps->data = NULL; ps->capacity = ps->top = 0; }2.队列
2.1概念与结构
概念：只允许在一端进行插入数据操作，在另一端进行删除数据操作，的特殊线性表，队列具有先进先出FIFO（First In First Out）。
入队列：进行插入操作的一端叫做队尾
出队列：进行删除操作的一端称为队头
队列也可以数组和链表的结构实现，使用链表的结构会更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率比较低。
2.2队列的实现
#include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> //链式结构表示队列 typedef int QDatetype; typedef struct QueueNode { QDatetype data; struct QueueNode* next; }QNode; //队列结构 typedef struct Queue { struct QueueNode* phead; struct QueueNode* ptail; int size;//计数器 }Queue; // 初始化队列 void QueueInit(Queue* pq); //销毁 void QueueDestory(Queue* pq); //入队列，队尾 void QueuePush(Queue* pq, QDatetype x); //出队列,队头 void QueuePop(Queue* pq); //取队头数据 QDatetype QueueFront(Queue* pq); //取队尾数据 QDatetype QueueBack(Queue* pq); //队列有效数据个数 int Queue2.2.1 定义队列结构和队列结点结构
队列的结点结构就是单链表结点结构，队列结构phead指向头结点和ptail指向尾结点，还有一个size用同统计结点个数。
//链式结构表示队列 typedef int QDatetype; typedef struct QueueNode { QDatetype data; struct QueueNode* next; }QNode; //队列结构 typedef struct Queue { struct QueueNode* phead; struct QueueNode* ptail; int size;//计数器 }Queue;2.2.2初始化队列
我们需要将头结点和尾结点的指针置为空指针，然后将size置为0.
// 初始化队列 void QueueInit(Queue* pq) { assert(pq); pq->phead = pq->ptail = NULL; pq->size = 0; } 2.2.3入队列
由于队列的特性我们不能遍历队列，因此我们需要从尾部插入数据，和我们的单链表尾插一样。我们需要先创建一个新的结点，然后将原来的尾结点的next指向新插入的结点然后将ptail指向新的尾结点。结点个数加一个。
void QueuePush(Queue* pq, QDatetype x) { assert(pq); //申请新的结点 QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail!"); exit(1); } //申请成功，开始赋值 newnode->data = x; newnode->next = NULL; //队列为空 if (pq->phead==NULL) { pq->phead = pq->ptail = newnode; } else { //队列不为空 pq->ptail->next = newnode; pq->ptail = newnode; } //入队列成功 pq->size++; } 2.2.4出队列，队头
出队列我们需要从队头出，也就是删除头结点。我们需要先判断一下队列是否为空，当队列的头结点和尾结点都为NULL时队列为空，然后我们需要先记录下当前头结点的下一个结点的位置，然后将头结点的空间释放掉，最后将头结点指向我们记录的下一个结点的位置。结点个数减一个。
bool QueueEmpty(Queue* pq) { assert(pq); return pq->phead == NULL && pq->ptail == NULL; } //出队列,队头 void QueuePop(Queue* pq) { assert(pq); //判断队列是否为空 assert(!QueueEmpty(pq)); //只有一个结点，避免ptail成为野指针 if (pq->phead == pq->ptail) { free(pq->phead); pq->phead = pq->ptail = NULL; } else { //删除队头元素 QNode* Next = pq->phead->next; free(pq->phead); pq->phead = Next; } --pq->size; } 2.2.5取队头数据
这个很简单，我们需要先判断一下队列是否为空，然后把头结点的data返回就行了。
//取队头数据 QDatetype QueueFront(Queue* pq) { assert(pq); //判断一下队列是否为空 assert(!QueueEmpty(pq)); return pq->phead->data; }2.2.6取队尾数据
和上面的取队头数据差不多，先判断队列是否为空，然后将尾结点的data返回。
//取队尾数据 QDatetype QueueBack(Queue* pq) { assert(pq); //判断一下队列是否为空 assert(!QueueEmpty(pq)); return pq->ptail->data; }2.2.7队列有效数据个数
直接返回队列结构体的size就好了。这就是我们定义size最大的用途，相当于计数器。
//队列有效数据个数 int QueueSize(Queue* pq) { assert(pq); return pq->size; }2.2.8销毁队列
和销毁单链表一样。直接上代码。
//销毁 void QueueDestory(Queue* pq) { assert(pq); //判断一下队列是否为空 assert(!QueueEmpty(pq)); QNode* pcur = pq->phead; while (pcur) { QNode* Next = pcur->next; free(pcur); pcur = Next; } pq->size = 0; pq->phead = pq->ptail = NULL; }