纯c实现栈和队列 数据结构大全

栈

栈是一种后进先出的数据结构，可以用数组来模拟实现，掌握必要的数据结构是非常的有必要的

一样是先打出头文件

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <assert.h>typedef int type;
typedef struct stack
{type* a;int top;//栈顶int capa;
}st;void stinit(st* pst);// 初始化
void stdestroy(st* pst);
void stpush(st* pst, type x);// 入
void stpop(st* pst);// 出
type sttop(st* pst);// 获取栈顶数据
bool stempty(st* pst);
int stsize(st* pst);

因为栈的特性，栈对比链表简单了不少

接下来我们来实现它的功能接口

初始化

使用typedef int是因为我们可能要存其他类型的数据，这样我们可以很容易的改变存进来的数据类型，避免麻烦的替换操作 

栈也分数组栈和链式栈，但我们很容易发现既然是后进先出，那么数组栈会更简单，更合理

typedef int type;
typedef struct stack
{type* a;int top;//栈顶int capa;
}st;

//数组栈 和 链式栈
//后进先出
#include "stack.h"void stinit(st* pst)// 初始化
{assert(pst);//经典判空pst->a = NULL;pst->top = 0;//指向栈顶数据pst->capa = 0;
}

销毁空间

void stdestroy(st* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capa = 0;
}

必要的接口，避免内存泄漏 

因为是数组实现，所以直接对a这块空间释放就可以了

入栈

void stpush(st* pst, type x)// 入栈
{if (pst->top == pst->capa){type newcapa = pst->capa == 0 ? 4 : pst->capa * 2;type* tmp = (type*)realloc(pst->a, newcapa * sizeof(type));if (tmp == NULL){perror("realloc fail\n");return;}pst->a = tmp;pst->capa = newcapa;}pst->a[pst->top++] = x;
}

第一个if是检查栈是否为0需要开辟空间，或者是栈是不是已经满了要开辟空间

要是if条件里面判断为真，我们就需要用两倍开辟新的空间

开辟完后再把数据入栈，同时记得更新a的地址以及容量capa的大小

出栈

void stpop(st* pst)// 出栈
{assert(pst);assert(!stempty(pst));//不为空才可以删pst->top--;
}

出栈很简单，判空之后直接top--，跟顺序表的尾删一样

获取栈顶数据

type sttop(st* pst)// 获取栈顶数据
{assert(pst);assert(!stempty(pst));//不为空才可以访问return pst->a[pst->top - 1];//避免越界访问
}

一样判空之后直接return top的值就可以提取出来了

判空

bool stempty(st* pst)
{assert(pst);return pst->top == 0;
}

检查top的值即可

检查数量

int stsize(st* pst)
{assert(pst);return pst->top;
}

一样检查top的值即可

测试

下面是测试代码，大家可以自己修改测试栈的功能

void stacktest1()//测试栈功能
{st s;//使用栈结构初始化stinit(&s);stpush(&s, 1);stpush(&s, 3);stpush(&s, 4);stpush(&s, 2);stpush(&s, 1);sttop(&s);stpop(&s);sttop(&s);while (!stempty(&s))//遍历 但是遍历一遍栈的数据就没了{printf("%d ", sttop(&s));stpop(&s);}stdestroy(&s);
}
int main()
{stacktest1();return 0;
}

队列 

队列是一种先进先出的数据结构，可以用链表来模拟实现，掌握必要的数据结构是非常的有必要的

因为是先进先出的特性，数组来模拟头删会特别慢

还是照例给出头文件

/一个是结点，好去malloc，一个是整体，整体是为了方便，提高效率
typedef struct quenenode
{struct quenenode* next;type data;
}qnode;typedef struct quene
{qnode* phead;qnode* ptail;int size;
}queue;
//void queueinit(queue* pq);
void queuedestroy(queue* pq);
void queuepush(queue* pq,type x);
void queuepop(queue* pq);
type queuefront(queue* pq);//取头
type queueback(queue* pq);//取尾
int  queuesize(queue* pq);
bool queueempty(queue* pq);

 和前面的数据结构不同的是，队列创建了两个结构体来提高接口的效率

初始化

接口调用的都是queue结构体，另一个结构体仅存数据和操作来指向next

//队列
//链式队列
//先进先出
//尾进头出#include "quene.h"void queueinit(queue* pq)//总体的初始化
{assert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}

销毁空间

void queuedestroy(queue* 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;
}

因为队列是链表为基础的，所以我们要创建一个结点来专门遍历销毁

最后再将phead和ptail置为空指针，size置为0

入队列

void queuepush(queue* pq, type x)
{assert(pq);qnode* newnode = (qnode*)malloc(sizeof(qnode));if (newnode == NULL){perror("malloc fail\n");return;}newnode->data = x;newnode->next = NULL;if (pq->ptail == NULL){assert(pq->phead == NULL);pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;//存数据进结点pq->ptail = newnode;//更新尾指针}pq->size++;
}

最开始还是经典判空，然后建立一个结点来接受新开辟的空间，然后将数据存入新建立的节点中，然后更新原本最后的结点的next的值，最后再将ptail指向新建立的结点，然后将描述数量的size++

出队列

void queuepop(queue* pq)//对头出数据
{assert(pq);assert(!queueempty(pq));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--;
}

首先判空，因为空的话会出现未定义行为

然后判断只有一个结点的情况，因为只有一个结点的时候next指向NULL

然后出队列其实就是头删，先建立一个结点保存头数据的next，然后将phead释放，再将phead指向新建立的next处

 取头取尾

type queuefront(queue* pq)//取头
{assert(pq);assert(!queueempty(pq));return pq->phead->data;
}
type queueback(queue* pq)//取尾
{assert(pq);assert(!queueempty(pq));return pq->ptail->data;
}

很简单直接取出phead 和 ptail 但是标准官方版的队列有这个接口，所以我们也实现一下

检查数量

int queuesize(queue* pq)//数量
{assert(pq);return pq->size;
}

跟上面的取头取尾一样，官方版的队列有这个接口，我们直接返回size即可

判空

bool queueempty(queue* pq)//判断空
{assert(pq);return pq->phead == NULL;//判断ptail跟size都可以
}

判空有很多种写法，自习挑选一种即可

测试

下面是测试代码，大家可以自己修改测试队列的功能

void testqueue()
{queue q;queueinit(&q);queuepush(&q, 1);queuepush(&q, 3);queuepush(&q, 2);queuepush(&q, 4);queuefront(&q);queueback(&q);while (!queueempty(&q)){printf("%d ", queuefront(&q));queuepop(&q);}printf("\n");queuedestroy(&q);
}int main()
{testqueue();return 0;
}