【栈和队列】纯C实现栈和队列以及其基本操作-宝藏级别数据结构教程【保姆级别详细教学】

【栈和队列】栈和队列的C语言实现-宝藏级别数据结构教程-超详细的注释和解释

先赞后看好习惯 打字不容易，这都是很用心做的，希望得到支持你 大家的点赞和支持对于我来说是一种非常重要的动力 看完之后别忘记关注我哦！️️️

本篇博客干货满满，建议收藏后食用~

文章目录

前言

还没有学习链表的伙伴，可以通过传送门先学习
单链表教学：【链表】单链表的介绍和基本操作（C语言实现）【保姆级别详细教学】
双向链表教学：【链表】双向链表的介绍和基本操作(C语言实现)【保姆级别详细教学】

当我们学习完链表之后，我们接下来要学习的基础数据结构，就是栈和队列了。 栈和队列，是我们后续学习，解题中非常重要的一种基础数据结构。虽然有些学习过C++或其它编程语言的伙伴会认为，只要会用即可，不需要知道底层的实现。
但是博主在这里要说的是，虽然其它面向对象的编程语言里面会有包装好的栈或队列可以使用，但是对于底层的实现原理的思想，对于我们的学习是非常重要的。因此接下来，请跟着博主的节奏，学习这两个重要的数据结构。

栈（stack）

什么是栈

栈
栈是一种特殊的线性表，只允许在固定的一段进行插入和删除的操作
进行数据插入和删除操作的一端称为栈顶，另一端称为栈底
栈中的数据遵循后进先出LIFO的原则
Last in First Out
压栈：栈的插入操作，在栈顶
出栈：栈的删除，出数据也在栈顶。

这个结构其实就像一个弹夹，只能在一端进行数据的插入和删除。

**

这里强调一下：栈的特点就是，后进先出！

**
这非常关键！

有关实现的思考

在实现之前，我们要思考：
首先，这是一个线性表实现的，所以我们有两个选择：顺序表，也就是数组实现；或者链表实现。
栈的实现
数组好还是链表好？
其实我们栈的插入和删除相当于尾插尾删
用数组的唯一缺陷就是不够的时候要增容
用单链表就不太好了：

1. 尾插尾删要找尾
2. 如果不找尾，用尾指针记录尾结点 但是即便这样，我们也要找到前一个

所以要不就使用双链表实现

如果一定想使用单链表
把把栈顶栈底反一下，用头插，不要用尾插即可
所以用单链表也是ok的

1. 如果用尾作栈顶，那么用双链表好
2. 如果要用单链表实现，那么就用让头作栈顶

总和各方面的要素，使用数组（顺序表）实现是最合适的。

• 在这里博主要给大家传递一个观念，我们说用数组实现栈最好。但是，数组并不是实现栈的唯一方法。基础数据结构的实现，是很灵活的，拿链表，拿顺序表实现都是正确的，能抓到老鼠的都是好猫。因此我们在学习的时候，不能过于死板，不能说老师说什么对就是对的，我们要灵活地学习！

代码实现

只要我们学习过链表和顺序表，这个栈的实现，简直就是信手拈来，非常简单的。
我们要实现的几个接口有:

节点结构

typedefint STDataType;typedefstruct Stack {
    STDataType* a;int top;//栈顶int capacity;//容量}ST;

初始化接口：
我们初始化的数组容量是4
容量不够后我们使用两倍扩容法

//初始化voidStackInit(ST* ps){assert(ps);//判断ps的真假
    ps->a =(STDataType*)malloc(sizeof(STDataType)*4);
    ps->capacity =4;
    ps->top =0;}

销毁栈接口：

注意： 释放后记得将指针置空，养成良好习惯，防止野指针的生成！

voidStackDestory(ST* ps){assert(ps);free(ps->a);
    ps->a =NULL;
    ps->top = ps->capacity =0;}

数据压栈接口：
采用两倍扩容法

//压栈voidStackPush(ST* ps, STDataType x){assert(ps);//扩容if(ps->top==ps->capacity){
        STDataType* tmp =realloc(ps->a, ps->capacity *2*sizeof(STDataType));if(tmp ==NULL){printf("realloc fail\n");exit(-1);}
        ps->a = tmp;
        ps->capacity *=2;//容量不够的时候，容量乘2}
    ps->a[ps->top]= x;//赋值
    ps->top++;//栈顶记得移动}

数据出栈接口：

**注意：当栈为空的时候，调用此接口肯定是不行的，因此出栈之前，我们还需要判断，栈是否为空。所以需要

assert(ps->top);

**

//出栈voidStackPop(ST* ps){assert(ps);assert(ps->top >0);//如果栈空了，调用Pop直接终止程序//不需要改数据，反正不重要//直接--top就可以了
    ps->top--;}

取栈顶元素接口：

对于我们来说，这些接口的实现都非常的简单，这里就不赘述了。
当然：要注意的点：top记得减一

//取栈顶元素
STDataType StackTop(ST* ps){assert(ps);assert(ps->top);//同样return ps->a[ps->top -1];//记得减一}

返回栈大小和验空接口：
代码实现和思路都非常简单，这里不赘述

//返回大小intStackSize(ST* ps){assert(ps);return ps->top;}//验空
bool StackEmpty(ST*ps){assert(ps);return ps->top ==0;}

stack.h源代码展示

#pragma once#include<stdbool.h>#include<stdio.h>#include<malloc.h>#include<assert.h>typedefint STDataType;typedefstruct Stack {
    STDataType* a;int top;//栈顶int capacity;//容量}ST;//初始化voidStackInit(ST* ps);//销毁voidStackDestory(ST* ps);//压栈voidStackPush(ST* ps, STDataType x);//出栈voidStackPop(ST* ps);//取栈顶元素
STDataType StackTop(ST* ps);//大小intStackSize(ST* ps);//验空
bool StackEmpty(ST* ps);

test.c源代码展示

#include"Stack.h"intmain(){//从规定来说//不能随便遍历//按照规定后进先出//如果能随便遍历就保不住它的性质了
    ST st;StackInit(&st);StackPush(&st,1);StackPush(&st,2);StackPush(&st,3);StackPush(&st,4);StackPush(&st,5);//这个循环才是栈的取数据的方法，而不是什么Print接口while(!StackEmpty(&st)){printf("%d\n",StackTop(&st));StackPop(&st);}printf("\n");StackDestory(&st);return0;}

队列（queue）

什么是队列

队列
只允许在一段进行插入数据操作，另一端进行删除数据操作的特殊线性表。
队列具有先进先出FIFO(Fist in First Out)的规则
入队列：队尾
出队列：队头

这个结构就是队列
它所遵循的原则是：先进先出。这个非常重要！一定要牢记

有关实现的思考

数组还是链表？
当然这里，我们毫不犹豫是要选择单链表的，因为单链表的头删和尾插都是非常高效率的。

**在这里博主特别强调一下：相比于普通的单链表，我们再存一个尾指针

tail

，用来指向链表最后一个元素，这样我们尾插的效率就可以达到

O(1)

了。**

代码实现

节点结构：

typedefint QDataType;typedefstruct QueueNode {struct QueueNode* next;//指针域
    QDataType data;//数据域}QNode;typedefstruct Queue {
    QNode* head;//头指针
    QNode* tail;//尾指针}Queue;

要实现的接口有这些：

初始化接口：

voidQueueInit(Queue* pq){assert(pq);
    pq->head = pq->tail =NULL;//两个指针先置空}

销毁队列接口：

voidQueueDestroy(Queue* pq){assert(pq);
    QNode* cur = pq->head;while(cur){//记得保存一下下一个位置的位置//防止下一个节点丢失
        QNode* next = cur->next;free(cur);
        cur = next;}
    pq->head = pq->tail =NULL;//记得置空，防止野指针生生成}

增加数据接口(队尾入)：
注意：这里需要注意分情况，链表为空和不为空的情况。

//队尾入voidQueuePush(Queue* pq, QDataType x){assert(pq);
    QNode* newnode =(QNode*)malloc(sizeof(QNode));if(newnode ==NULL){printf("malloc fail\n");exit(-1);}
    newnode->data = x;
    newnode->next =NULL;//这里要分情况，如果链表一开始为空的时候，head和tail是一样的if(pq->tail ==NULL){
        pq->head = pq->tail = newnode;}//链表不为空：else{
        pq->tail->next = newnode;
        pq->tail = newnode;}}

删除数据接口(队头出)：

//队头出voidQueuePop(Queue* pq){assert(pq);assert(pq->head);//判断队列不为空//如果只剩一个节点时：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;//如果只剩一个之后，tail变成野指针了，所以处理一下tail,即上面的if//因此要分情况}}

取数据接口：
思路非常简单，这里不赘述。

//取数据
QDataType QueueFront(Queue* pq){assert(pq);assert(pq->head);return pq->head->data;}
QDataType QueueBack(Queue* pq){assert(pq);assert(pq->head);return pq->tail->data;}

返回大小和验空接口：

intQueueSize(Queue* pq){//遍历assert(pq);int size =0;
    QNode* cur = pq->head;//这里其实就是一个数组的遍历while(cur){
        size++;//计数器
        cur = cur->next;//迭代}return size;}
bool QueueEmpty(Queue* pq){assert(pq);return pq->head ==NULL;}

Queue.h源代码展示

#pragma once#include<stdio.h>#include<stdbool.h>#include<assert.h>#include<stdlib.h>typedefint QDataType;typedefstruct QueueNode {struct QueueNode* next;
    QDataType data;}QNode;typedefstruct Queue {
    QNode* head;
    QNode* tail;}Queue;//初始化voidQueueInit(Queue* pq);//销毁voidQueueDestroy(Queue* pq);//队尾入voidQueuePush(Queue* pq, QDataType x);//队头出voidQueuePop(Queue* pq);//取数据
QDataType QueueFront(Queue* pq);//头数据
QDataType QueueBack(Queue* pq);//尾数据//返回队列大小intQueueSize(Queue* pq);//验空
bool QueueEmpty(Queue* pq);

test.c源代码展示

#include"Queue.h"voidTestQueue(){
    Queue q;QueueInit(&q);//QueuePop(&q);QueuePush(&q,1);QueuePush(&q,2);QueuePush(&q,3);QueuePush(&q,4);QueuePush(&q,5);while(!QueueEmpty(&q)){printf("%d ",QueueFront(&q));QueuePop(&q);}printf("\n");QueueDestroy(&q);}intmain(){TestQueue();return0;}

尾声

看到这里，相信伙伴们已经对栈和队列已经有了比较深入的了解，掌握了基本的操作接口实现方法。这对我们以后数据结构的学习是非常有帮助的！
如果看到这里的你感觉这篇博客对你有帮助，不要忘了收藏，点赞，转发，关注哦！