Hello，everyone，今天小编讲解栈和队列的知识！！！
1.栈
1.1栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。 进行数据插入和删除操作的一端 称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈， 入数据在栈顶。
出栈：栈的删除操作叫做出栈。 出数据也在栈顶。
1.2栈的实现
栈的实现一般可以使用 数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
1.2.1 头文件的建立
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int datatype; //这里选用动态数组实现栈，单链表也可以 typedef struct stack { datatype* a; int top;//栈顶 int capacity; }ST; //栈的初始化和销毁 void STInit(ST* pst); void STDestory(ST* pst); //入栈和出栈 void STPush(ST* pst,datatype x); void STPop(ST* pst); //获取栈顶数据 datatype STTop(ST* pst); //判空 bool STEmpty(ST* pst); //栈的数据个数 int STSize(ST* pst);
1.2.2 函数的实现
#define _CRT_SECURE_NO_WARNINGS #include "Stack.h" //栈的初始化和销毁 void STInit(ST* pst){ assert(pst); pst->a = NULL; //top指向栈顶数据的下一个位置,可以理解为下标 pst->top = 0; //top指向指向栈顶数据，可以理解成栈的数据个数 //pst->top=-1; pst->capacity = 0; } void STDestory(ST* pst) { assert(pst); free(pst->a); pst->a = NULL; pst->top = pst->capacity = 0; } //容量检查 void Checkcapacity(ST* pst) { assert(pst); if (pst->top == pst->capacity) { int newcapacity = pst->capacity==0?4:pst->capacity * 2; datatype* temp = (datatype*)realloc(pst->a, newcapacity * sizeof(datatype)); if (temp == NULL) { perror("relloc fail"); return; } pst->a = temp; pst->capacity = newcapacity; } } //入栈和出栈 void STPush(ST* pst, datatype x) { assert(pst); Checkcapacity(pst); pst->a[pst->top] = x; pst->top++; } void STPop(ST* pst) { assert(pst); assert(pst->top>0); pst->top--; } //获取栈顶数据 datatype STTop(ST* pst) { assert(pst); assert(pst->top > 0); return pst->a[pst->top-1]; } //判空 bool STEmpty(ST* pst) { assert(pst); return pst->top == 0;//表达式判断 } //栈的数据个数 int STSize(ST* pst) { assert(pst); return pst->top; }
1.2.3 测试文件
#define _CRT_SECURE_NO_WARNINGS #include "Stack.h" int main() { ST s; STInit(&s); STPush(&s, 1); STPush(&s, 2); STPush(&s, 3); STPush(&s, 4); STPush(&s, 5); printf("%d\n", STTop(&s)); STPop(&s); //STPop(&s); printf("%d\n", STTop(&s)); while (!STEmpty(&s)) { printf("%d ", STTop(&s)); STPop(&s); } STDestory(&s); return 0; }
2.队列
2.1队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out)
入队列：进行插入操作的一端称为 队尾
出队列：进行删除操作的一端称为 队头
2.2队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
2.2.1 头文件的建立
#pragma once #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <assert.h> typedef int Qdatatype; //链式结构表示队列 typedef struct QueueNode { struct QueueNode* next; Qdatatype x; }Node; //定义结构体表示队头队尾,后续传参改变队列也很方便，不用传二级指针。 typedef struct Queue { Node* head; Node* tail; int size; }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 bool QueueEmpty(Queue* q); // 销毁队列 void QueueDestroy(Queue* q);
2.2.2 函数的实现
#define _CRT_SECURE_NO_WARNINGS #include "Queue.h" void QueueInit(Queue* q) { assert(q); q->head = NULL; q->tail = NULL; q->size = 0; } // 队尾入队列 void QueuePush(Queue* q, Qdatatype data) { assert(q); Node* newnode = (Node*)malloc(sizeof(Node)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->next = NULL; newnode->x = data; if (q->tail ==NULL) { q->head = q->tail = newnode; } else { q->tail->next = newnode; q->tail = newnode; } q->size++; } // 队头出队列 void QueuePop(Queue* q) { assert(q); assert(q->size != 0); //一个节点 if (q->head->next == NULL) { free(q->head); q->head = q->tail = NULL; } else { Node* next = q->head->next; free(q->head); q->head = next; } q->size--; } // 获取队列头部元素 Qdatatype QueueFront(Queue* q) { assert(q); assert(q->head); return q->head->x; } // 获取队列队尾元素 Qdatatype QueueBack(Queue* q) { assert(q); assert(q->tail); return q->tail->x; } // 获取队列中有效元素个数 int QueueSize(Queue* q) { assert(q); return q->size; } // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 bool QueueEmpty(Queue* q) { assert(q); return q->size == 0;//为0，返回1，不为0，返回0； } // 销毁队列 void QueueDestroy(Queue* q) { assert(q); Node* qcur = q->head; while (qcur) { Node* next = qcur->next; free(qcur); qcur = next; } q->head = q->tail = NULL; q->size = 0; }
2.2.3 测试文件
#define _CRT_SECURE_NO_WARNINGS #include "Queue.h" int main() { Queue p; QueueInit(&p); QueuePush(&p,1); QueuePush(&p,2); printf("%d\n", QueueFront(&p)); QueuePush(&p, 3); QueuePush(&p, 4); printf("%d\n",QueueBack(&p)); QueuePop(&p); printf("%d\n", QueueFront(&p)); while (!QueueEmpty(&p)) { printf("%d ", QueueFront(&p)); QueuePop(&p); } printf("\n"); return 0; }
另外扩展了解一下，实际中我们有时还会使用一种队列叫循环队列。如操作系统讲解生产者消费者模型时可以就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。
今天内容讲解结束，下次小编将讲解栈和队列的相关习题。
希望各位友友留下三连和评论！！！
