栈
栈是一种后进先出的数据结构，可以用数组来模拟实现，掌握必要的数据结构是非常的有必要的
一样是先打出头文件
#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;
}
