【数据结构】详解栈和队列

目录一栈1栈的概念2栈的实现3栈的练习_1有效的括号二队列1队列的概念2队列的实现3队列的练习_1,设计循环队列三综合练习_1,用队列实现栈_2,用栈实现队列一栈1栈的概念栈一种特定的线性表只能在固定位置进行数据的插入和删除。进行插入的一端为栈顶另一端为栈底栈中的元素遵循先进后出后进先出的原则。压栈向栈中插入元素叫做压栈/入栈/进栈压栈的一端为栈顶。出栈向栈中删除元素叫做出栈。出数据也在栈顶。 6544453图示由于栈先进后出的特性若此时边进边出则一种入栈顺序可对应多种出栈顺序例如入栈顺序为1 2 3 4而出栈顺序共有14种可以是1 2 3 4 全进全出1 2 4 31 3 2 41 3 4 21 4 3 22 1 3 42 1 4 32 3 1 42 3 4 12 4 3 13 2 1 43 2 4 13 4 2 14 3 2 12栈的实现栈的实现可以借助数组亦可以借助链表进行实现。由于数组(顺序表)的缓存利用率高所以下面我们使用数组进行栈的实现。代码gitee链接https://gitee.com/codelsj-w/test.4.1.c.git头文件stack.h--函数的声明#pragma once #include stdio.h #include stdlib.h #include assert.h #include stdbool.h typedef int STDataType; typedef struct stack1 { STDataType* a; //数组的第一个元素的指针 int top; //栈顶元素的下一个的下标 int capacity; //数组中的元素个数 }ST; //初始化栈销毁栈 void STInit(ST* sep); void STDestroy(ST* sep); //入栈出栈 void STPush(ST* sep, STDataType x); void STPop(ST* sep); //求栈顶元素 STDataType STTop(ST* sep); //判空 bool STEmpty(ST* sep); //求栈中的元素个数 int STSize(ST* sep);源文件stack.c--实现函数功能#define _CRT_SECURE_NO_WARNINGS 1 #include stack.h //初始化栈销毁栈 void STInit(ST* sep) { assert(sep); sep-a NULL; //指向栈顶的下一个元素 sep-top 0; //指向栈顶元素 //sep-top -1; sep-capacity 0; } void STDestroy(ST* sep) { assert(sep); sep-a NULL; sep-top sep-capacity 0; } //入栈 void STPush(ST* sep, STDataType x) { assert(sep); //扩容 if (sep-top sep-capacity) { //三目操作符创建开辟元素的个数 int newcapacity sep-capacity 0 ? 4:sep-capacity * 2; STDataType* cmp (STDataType*)realloc(sep-a, sizeof(STDataType) * newcapacity); if (cmp NULL) { perror(realloc); return; } sep-a cmp; sep -capacity newcapacity; } sep-a[sep-top] x; sep-top; } //出栈 void STPop(ST* sep) { assert(sep); assert(sep-top 0); sep-top--; } //取栈顶元素 STDataType STTop(ST* sep) { assert(sep); assert(sep-top 0); return sep-a[sep-top - 1]; } //判空 bool STEmpty(ST* sep) { assert(sep); return sep-top 0; } //求栈中的元素个数 int STSize(ST* sep) { assert(sep); return sep-top; }源代码code.c--执行功能#define _CRT_SECURE_NO_WARNINGS 1 #include stdio.h #include stdlib.h #include stack.h int main() { ST s; STInit(s); STPush(s, 1); STPush(s, 2); STPush(s, 3); STPush(s, 4); STPop(s); int k STSize(s); printf(%d\n, k); while (!STEmpty(s)) { printf(%d , STTop(s)); STPop(s); } STDestroy(s); return 0; }3栈的练习_1有效的括号核心思路遍历字符串左括号进栈右括号和栈顶元素进行匹配代码实现#define _CRT_SECURE_NO_WARNINGS 1 //函数的声明 typedef char STDataType; typedef struct stack1 { STDataType* a; //数组的第一个元素的指针 int top; //栈顶元素的下一个的下标 int capacity; //数组中的元素个数 }ST; //初始化栈销毁栈 void STInit(ST* sep); void STDestroy(ST* sep); //入栈出栈 void STPush(ST* sep, STDataType x); void STPop(ST* sep); //求栈顶元素 STDataType STTop(ST* sep); //判空 bool STEmpty(ST* sep); //求栈中的元素个数 int STSize(ST* sep); //函数的实现 //初始化栈销毁栈 void STInit(ST* sep) { assert(sep); sep-a NULL; //指向栈顶的下一个元素 sep-top 0; //指向栈顶元素 //sep-top -1; sep-capacity 0; } void STDestroy(ST* sep) { assert(sep); sep-a NULL; sep-top sep-capacity 0; } //入栈 void STPush(ST* sep, STDataType x) { assert(sep); //扩容 if (sep-top sep-capacity) { //三目操作符创建开辟元素的个数 int newcapacity sep-capacity 0 ? 4:sep-capacity * 2; STDataType* cmp (STDataType*)realloc(sep-a, sizeof(STDataType) * newcapacity); if (cmp NULL) { perror(realloc); return; } sep-a cmp; sep -capacity newcapacity; } sep-a[sep-top] x; sep-top; } //出栈 void STPop(ST* sep) { assert(sep); assert(sep-top 0); sep-top--; } //取栈顶元素 STDataType STTop(ST* sep) { assert(sep); assert(sep-top 0); return sep-a[(sep-top) -1]; } //判空 bool STEmpty(ST* sep) { assert(sep); return sep-top 0; } //求栈中的元素个数 int STSize(ST* sep) { assert(sep); return sep-top; } //功能实现 bool isValid(char* s) { //创建栈 ST std; STInit(std); while(*s) { //左括号入栈 if(*s ( || *s [ || *s {) { STPush(std, *s); } //取栈顶元素和右括号进行匹配 else { //栈为空 if(STEmpty(std)) { STDestroy(std); return false; } char tap STTop(std); STPop(std); //不匹配 if((tap ( *s ! )) ||(tap [ *s ! ]) ||(tap { *s ! })) { STDestroy(std); return false; } } s; } //栈不为空说明左括号比右括号多 bool ret STEmpty(std); STDestroy(std); return ret; }二队列1队列的概念队列只允许在一端插入在另一端删除的特殊线性表。入队列进行插入操作的一端叫做队尾出队列进行删除操作的一端叫做队头。队列的元素遵循先进先出的原则。2队列的实现由于一种入栈顺序可以对应多种出栈顺序。而一种入队列顺序只能对应一种出队列顺序。例如入队列 1 2 3 4则出队列1 2 3 42队列的实现因为要满足在一端插入元素在另一端删除元素而在数组的头不管是进行插入元素还是删除元素都需要移动整个数组的元素比较麻烦所以考虑使用链表进行实现。单链表比双向链表少一组指针所以更容易实现所以我们使用单链表进行实现。队列实现全过程代码gitee链接https://gitee.com/codelsj-w/test.4.2.c.git头文件Queue.h--函数声明#pragma once #include stdio.h #include stdlib.h #include stdbool.h #include assert.h //重命名--方便节点类型的一键替换 typedef int QuNodeType; //单个节点 typedef struct QueueNode { QuNodeType* val; struct QueueNode* next; }QNode; //使用二级指针对指针进行更改比较麻烦 //所以将首尾指针放到结构体当中方便进行改变,同时表示队列 typedef struct Queueps { QNode* head;//单链表的头节点的地址 QNode* tail;//单链表的尾节点的地址 int size; //单链表中节点的个数 }Que; //队列的创建 void QuInit(Que* sep); //队列的销毁 void QuDestroy(Que* sep); //队尾插入 void QuPush(Que* sep, QuNodeType x); //队头删除 void QuPop(Que* sep); //取队头数据 QuNodeType QuFront(Que* sep); //取队尾数据 QuNodeType QuBack(Que* sep); //求队列中的元素个数 int Qusize(Que* sep); //判空 bool QuEmpty(Que* sep);源文件Queue.c--函数的实现#define _CRT_SECURE_NO_WARNINGS 1 #include Queue.h //队列的创建和销毁 void QuInit(Que* sep) { assert(sep); sep-head NULL; sep-tail NULL; sep-size 0; } //队列的销毁 void QuDestroy(Que* sep) { assert(sep); //定义一个变量进行接收 QNode* cur sep-head; //释放节点 while (cur) { QNode* next cur-next; free(cur); cur next; } sep-head sep-tail NULL; sep-size 0; } //队尾插入 void QuPush(Que* sep, QuNodeType x) { assert(sep); //创建一个节点 QNode* newnode (QNode*)malloc(sizeof(QNode)); if (newnode NULL) { perror(malloc); return; } newnode-val x; newnode-next NULL; //进行插入 if (sep-head NULL) //链表为空 { sep-head sep-tail newnode; } else //链表不为空 { sep-tail-next newnode; sep-tail newnode; } sep-size; } //队头删除 void QuPop(Que* sep) { assert(sep); //判断节点数不为空 assert(sep-size ! 0); //只有一个节点 if (sep-head-next NULL) { free(sep-head); sep-head sep-tail NULL; } //有多个节点 else { QNode* next sep-head-next;//先储存放丢失 free(sep-head); //再释放 sep-head next; } sep-size--; } //取队头数据 QuNodeType QuFront(Que* sep) { assert(sep); assert(sep-head); return sep-head-val; } //取队尾数据 QuNodeType QuBack(Que* sep) { assert(sep); assert(sep-tail); return sep-tail-val; } //求队列中的元素个数 int Qusize(Que* sep) { assert(sep); return sep-size; } //判空 bool QuEmpty(Que* sep) { assert(sep); return sep-size 0; }源文件code.c --功能的执行#define _CRT_SECURE_NO_WARNINGS 1 #include Queue.h int main() { Que qu; QuInit(qu); QuPush(qu, 1); QuPush(qu, 2); QuPush(qu, 3); QuPush(qu, 4); QuPop(qu); printf(%d\n, QuFront(qu));//2 printf(%d\n, QuBack(qu));//4 Qusize(qu);//3 while (!QuEmpty(qu)) { printf(%d , QuFront(qu)); QuPop(qu); } printf(\n); QuDestroy(qu); return 0; }3队列的练习_1,设计循环队列核心思路:代码实现//队列的创建 typedef struct { int* a; int head; //队列的首元素的下标 int tail; //队列的尾元素的下一个的下标 int k; //队列中实际空间的个数 } MyCircularQueue; //队列的初始化 MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); //多开辟一个空间解决溢出问题 obj-a (int*)malloc((k1) * sizeof(int)); obj-head 0; obj-tail 0; obj-k k; return obj; } //判空 bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return (obj-head) obj-tail; } //判满 bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj-tail1) %(obj-k1) obj-head; } //插入数据元素 bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if (myCircularQueueIsFull(obj)) { return false; } obj-a[obj-tail] value; obj-tail; //处理特殊回绕情况 obj-tail % (obj-k1); return true; } //删除元素 bool myCircularQueueDeQueue(MyCircularQueue* obj) { //先判空 if(myCircularQueueIsEmpty(obj)) { return false; } obj-head; //处理特殊回绕情况 obj-head % (obj-k1); return true; } //获取队头元素 int myCircularQueueFront(MyCircularQueue* obj) { //先判空 if(myCircularQueueIsEmpty(obj)) { return -1; } else return obj-a[obj-head]; } //获取队尾元素 int myCircularQueueRear(MyCircularQueue* obj) { //判空 if(myCircularQueueIsEmpty(obj)) { return -1; } //使用三目操作符处理一种特殊情况 else return obj-tail 0 ? obj-a[obj-k] : obj-a[obj-tail-1]; } //销毁队列 void myCircularQueueFree(MyCircularQueue* obj) { //malloc几个free几次 free(obj-a); free(obj); }三综合练习_1,选择题以下各链表均不带有头节点其中最不适合用作链栈的链表是___________ 。A.只有表尾指针没有表头指针的循环单链表B.只有表头指针没有表尾指针的循环单链表C,只有表头指针没有表尾指针的循环双链表D,只有表尾指针没有表头指针的循环双链表答案B分析分析是否适合用作链栈主要看链表是否方便实现数据的进栈和出栈。A.由于有tail尾指针所以可以直接将数据直接插入到tail的下一个相当于入栈而删除元素也直接访问tail的next数据相当于出栈。所以两种操作的时间复杂度为O(1).B,只有头节点的指针只能通过遍历找到尾节点tail-next first,在进行元素的插入也就是入栈同样进行元素的删除时删除栈顶元素也需要通过遍历找到栈底元素让栈底元素的next指针指向first的next节点。这两种操作都需要遍历链表找到尾节点所以这两种操作的时间复杂度均为O(n).C,D由于都是循环双链表所以可以直接找到栈顶元素和栈底元素进行元素的插入和删除。因此时间复杂度都为O(1)._2,用队列实现栈核心思路1初始时插入元素(进栈)向其中一个队列插入元素出栈时将有元素的队列中的前size-1个元素转移到另一个队列中去再取出原来队列中剩余的一个元素并删除。之后元素进栈就插入到有元素的队列中去。元素出栈就重复上述过程。代码实现//函数的声明 //重命名--方便节点类型的一键替换 typedef int QuNodeType; //单个节点 typedef struct QueueNode { QuNodeType val; struct QueueNode* next; }QNode; //使用二级指针对指针进行更改比较麻烦 //所以将首尾指针放到结构体当中方便进行改变,同时表示队列 typedef struct Queueps { QNode* head;//单链表的头节点的地址 QNode* tail;//单链表的尾节点的地址 int size; //单链表中节点的个数 }Que; //队列的创建 void QuInit(Que* sep); //队列的销毁 void QuDestroy(Que* sep); //队尾插入 void QuPush(Que* sep, QuNodeType x); //队头删除 void QuPop(Que* sep); //取队头数据 QuNodeType QuFront(Que* sep); //取队尾数据 QuNodeType QuBack(Que* sep); //求队列中的元素个数 int Qusize(Que* sep); //判空 bool QuEmpty(Que* sep); //函数功能的实现 //队列的创建和销毁 void QuInit(Que* sep) { assert(sep); sep-head NULL; sep-tail NULL; sep-size 0; } //队列的销毁 void QuDestroy(Que* sep) { assert(sep); //定义一个变量进行接收 QNode* cur sep-head; //释放节点 while (cur) { QNode* next cur-next; free(cur); cur next; } sep-head sep-tail NULL; sep-size 0; } //队尾插入 void QuPush(Que* sep, QuNodeType x) { assert(sep); //创建一个节点 QNode* newnode (QNode*)malloc(sizeof(QNode)); if (newnode NULL) { perror(malloc); return; } newnode-val x; newnode-next NULL; //进行插入 if (sep-head NULL) //链表为空 { sep-head sep-tail newnode; } else //链表不为空 { sep-tail-next newnode; sep-tail newnode; } sep-size; } //队头删除 void QuPop(Que* sep) { assert(sep); //判断节点数不为空 assert(sep-size ! 0); //只有一个节点 if (sep-head-next NULL) { free(sep-head); sep-head sep-tail NULL; } //有多个节点 else { QNode* next sep-head-next;//先储存放丢失 free(sep-head); //再释放 sep-head next; } sep-size--; } //取队头数据 QuNodeType QuFront(Que* sep) { assert(sep); assert(sep-head); return sep-head-val; } //取队尾数据 QuNodeType QuBack(Que* sep) { assert(sep); assert(sep-tail); return sep-tail-val; } //求队列中的元素个数 int Qusize(Que* sep) { assert(sep); return sep-size; } //判空 bool QuEmpty(Que* sep) { assert(sep); return sep-size 0; } //前面的部分是关于队列的基本功能的实现作为实现下面功能的基础 //下面才是问题真正的实现过程 typedef struct { Que q1; Que q2; } MyStack; //队列的初始化 MyStack* myStackCreate() { MyStack* obj (MyStack*)malloc(sizeof(MyStack)); QuInit((obj-q1)); QuInit((obj-q2)); return obj; } //插入元素--入栈 void myStackPush(MyStack* obj, int x) { if(!QuEmpty((obj-q1))) { QuPush((obj-q1), x); } else { QuPush((obj-q2), x); } } //删除元素--出栈 int myStackPop(MyStack* obj) { //假设法 Que* Empty (obj-q2); Que* Nonempty (obj-q1); if(!QuEmpty(Empty)) { Empty (obj-q1); Nonempty (obj-q2); } //将Nonempty中的前size-1个元素转移到Empty中 while(Qusize(Nonempty)1) { QuPush(Empty, QuFront(Nonempty)); QuPop(Nonempty); } int top QuFront(Nonempty); QuPop(Nonempty); return top; } //求栈顶元素 int myStackTop(MyStack* obj) { if(QuEmpty((obj-q1))) { return QuBack((obj-q2)); } else { return QuBack((obj-q1)); } } //判空 bool myStackEmpty(MyStack* obj) { return QuEmpty((obj-q1))QuEmpty((obj-q2)); } void myStackFree(MyStack* obj) { QuDestroy((obj-q1)); QuDestroy((obj-q2)); free(obj); }_3,用栈实现队列核心思路代码实现//函数的声明 typedef int STDataType; typedef struct stack1 { STDataType* a; //数组的第一个元素的指针 int top; //栈顶元素的下一个的下标 int capacity; //数组中的元素个数 }ST; //初始化栈销毁栈 void STInit(ST* sep); void STDestroy(ST* sep); //入栈出栈 void STPush(ST* sep, STDataType x); void STPop(ST* sep); //求栈顶元素 STDataType STTop(ST* sep); //判空 bool STEmpty(ST* sep); //求栈中的元素个数 int STSize(ST* sep); //函数的实现 //初始化栈销毁栈 void STInit(ST* sep) { assert(sep); sep-a NULL; //指向栈顶的下一个元素 sep-top 0; //指向栈顶元素 //sep-top -1; sep-capacity 0; } void STDestroy(ST* sep) { assert(sep); sep-a NULL; sep-top sep-capacity 0; } //入栈 void STPush(ST* sep, STDataType x) { assert(sep); //扩容 if (sep-top sep-capacity) { //三目操作符创建开辟元素的个数 int newcapacity sep-capacity 0 ? 4:sep-capacity * 2; STDataType* cmp (STDataType*)realloc(sep-a, sizeof(STDataType) * newcapacity); if (cmp NULL) { perror(realloc); return; } sep-a cmp; sep -capacity newcapacity; } sep-a[sep-top] x; sep-top; } //出栈 void STPop(ST* sep) { assert(sep); assert(sep-top 0); sep-top--; } //取栈顶元素 STDataType STTop(ST* sep) { assert(sep); assert(sep-top 0); return sep-a[sep-top - 1]; } //判空 bool STEmpty(ST* sep) { assert(sep); return sep-top 0; } //求栈中的元素个数 int STSize(ST* sep) { assert(sep); return sep-top; } //解决实际问题 //栈的创建 typedef struct { ST pushst; ST popst; } MyQueue; //栈的初始化 MyQueue* myQueueCreate() { MyQueue* obj (MyQueue*)malloc(sizeof(MyQueue)); STInit((obj-pushst)); STInit((obj-popst)); return obj; } //元素入队列 void myQueuePush(MyQueue* obj, int x) { STPush((obj-pushst), x); } //返回队列开头的元素 int myQueuePeek(MyQueue* obj) { //判空倒数据 if(STEmpty((obj-popst))) { while(!STEmpty((obj-pushst))) { int top STTop((obj-pushst)); STPush((obj-popst), top); STPop((obj-pushst)); } } return STTop((obj-popst)); } //元素出队列 int myQueuePop(MyQueue* obj) { int tep myQueuePeek(obj); STPop((obj-popst)); return tep; } //判断队列是否为空 bool myQueueEmpty(MyQueue* obj) { return STEmpty((obj-pushst)) STEmpty((obj-popst)); } void myQueueFree(MyQueue* obj) { STDestroy((obj-pushst)); STDestroy((obj-popst)); free(obj); }