栈

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

一样是先打出头文件

#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
");
            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
");
		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("
");
	queuedestroy(&q);
}

int main()
{
	testqueue();
	return 0;
}