栈
什么是栈？
栈也是顺序表的一种，栈的逻辑实现是先进后出（后进先出）就跟子弹夹一样。
具体逻辑就是它只允许在固定的一端进行数据的插入与删除，在数据插入与删除的一端称为
栈顶，另一端称为栈低
压栈：插入数据的名称，在栈顶插入数据
出栈：删除数据的名称, 在栈顶删除数据
如图：
栈的具体实现
我们可以用双链表，单链表，数组来实现栈，
本文采用数组来实现栈，因为双链表的指针太多，浪费，单链表每次创建节点都需要去用操作系统
也是比较浪费资源。
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdlib.h> //用于引用动态内存函数
#include<stdbool.h>//用于使用布尔类型
#include<assert.h>
typedef int Datatype;
typedef struct Stack {
Datatype* arr; //定义数组来实现栈。那么进栈与出栈的操作用尾插与尾删实现
int capacity; //已经申请的空间
int top; //用top的数值代表栈顶指针,指向第几个元素
}ST;
//栈的初始化
void StackInitialize(ST* p);
//判断空间是否足够，不够则扩容
void Deter(ST* p);
//进栈
void StackInsert(ST* p, Datatype x);
//出栈
void StackDelete(ST* p);
//返回栈顶的元素
Datatype StackTop(ST* p);
//求栈中元素的个数
int StackSize(ST* p);
//判断栈是否为空
bool StackEmpty(ST* p);
//栈的销毁
void StackDestory(ST* p);
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
//栈的初始化
void StackInitialize(ST*p) {
//将栈的空间初始置为4个元素的大小
p->arr = (Datatype *)malloc(4 * sizeof(Datatype));
//栈的初始元素个数为0
p->top = 0; //top的初始值为0代表，表示栈顶指针指向栈顶元素的下一个元素
//这个栈顶指针的理解可以从p->size元素个数的角度理解
//p-size-1就相当于栈顶指针指向的元素位置，p->size即元素的总个数
//因为top代表栈顶指针指向栈顶的下一个元素，所以可以使用top-1来表示栈顶元素
// 但是top为0时，则代表栈中没有元素，top-1也不能使用！
p->capacity = 4;//初始化的空间为4个数据类型大小的空间
}
//判断空间是否足够，不够则扩容
void Deter(ST* p) {
//判断空间是否足够，要看元素个数与空间个数是否相同
//如果相同，则空间不足
assert(p);
if (p->top == p->capacity) {
Datatype* p1 = realloc(p->arr, 2 * p->capacity * sizeof(Datatype));
//如果扩展空间失败
if (p1 == NULL) {
printf("扩展空间失败\n");
}
//如果扩展空间成功，
else {
p->arr = p1;
p->capacity = 2 * p->capacity;//记录增长二倍
}
}
}
//进栈
void StackInsert(ST*p,Datatype x) {
assert(p);
//先判断空间是否足够,如果不足，则扩容
Deter(p);
//从数组的尾部插入数据实现进栈
p->arr[p->top++] = x;
}
//出栈
void StackDelete(ST*p) {
assert(p);
//如果栈已经为空，还删除栈中内容则报错！
assert(p->top > 0);
p->top--;
}
//返回栈顶的元素
Datatype StackTop(ST *p) {
assert(p);
assert(p->top > 0);//栈不能为空，否则报错
return p->arr[p->top - 1];
}
//求栈中元素的个数
int StackSize(ST*p) {
assert(p);
return p->top;
}
//判断栈是否为空
bool StackEmpty(ST*p) {
assert(p);
//查询栈中元素的个数即可
if (p->top == 0) {
//false表示为空
return false;
}
else {
return true;
}
}
//栈的销毁
void StackDestory(ST *p) {
assert(p);
//栈的销毁需要先释放掉申请的空间
free(p->arr);
p->arr = NULL;
p->top = p->capacity = 0;
}
队列
什么是队列？
队列也是线性表的一种，它的规则是只能在队列的一端插入数据，在另一端删除数 据，简称为：先进先出
出队列：进入数据删除的一端称为队头
入队列：进行数据插入的一端称为队尾
队列的实现
队列可以由数组，单链表，与双链表实现，
数组实现时，如果删除数据后，还需再挪动整个队列中的数据移动
双链表的指针太多，
所以我采用单链表:
进行尾插与头删
#pragma once //用于避免头文件被重复引用
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//定义存储的数据类型
typedef int Datatype;
//用单链表来实现队列
typedef struct QueueNode {
Datatype data;
struct QueueNode* Next;
}QN;
//初始化队列：
//因为要改变头指针，所以需要用二级指针
void QueueInitialize(QN** pphead);
//队尾入
//采用尾插法来实现
void QueueInsert(QN* phead, Datatype x);
//队头出
//出队列的实现用头删法
//因为头指针需要改变，所以用二级指针作为形参
void QueueDelete(QN** pphead);
//获取队头的数据
Datatype QueueFront(QN* phead);
//获取队尾的数据
Datatype QueueTail(QN* phead);
//获取队列中元素的个数
int QueueSize(QN* phead);
//判断队列是否为空
bool QueueEmpty(QN* phead);
//销毁队列
void QueueDestory(QN** phead);
#include"Queue.h"
//初始化队列：
//因为要改变头指针，所以需要用二级指针
void QueueInitialize(QN**pphead) {
*pphead = NULL;
}
//队尾入
//采用尾插法来实现
void QueueInsert(QN*phead,Datatype x) {
//先找到队尾
QN* temp = phead;
while (temp!= NULL) {
temp = temp->Next;
}
temp = (QN*) malloc (sizeof(QN)); //创建一个新节点
temp->data = x; //赋值
temp->Next = NULL;
}
//队头出
//出队列的实现用头删法
//因为头指针需要改变，所以用二级指针作为形参
void QueueDelete(QN**pphead) {
//头删时，首节点不能为空
assert(*pphead&&pphead);
QN* tem = *pphead;
*pphead = (*pphead)->Next;//将头指针指向第二个节点
free(tem); //释放掉tem中指针指向的空间
}
//获取队头的数据
Datatype QueueFront(QN *phead) {
assert(phead); //phead不能为空。
return phead->data;
}
//获取队尾的数据
Datatype QueueTail(QN* phead) {
assert(phead);
QN* tem = phead;
while (tem->Next!=NULL) {
tem = tem->Next;
}
//找到尾节点后
return tem->data;
}
//获取队列中元素的个数
int QueueSize(QN*phead) {
int size = 0;
QN* tem = phead;
while (tem != NULL) {
tem = tem->Next;
size++;
}
return size;
}
//判断队列是否为空
bool QueueEmpty(QN*phead) {
//如果队列为空，返回true
if (phead == NULL)
return true;
//如果队列不为空,返回false
else
return false;
}
//销毁队列
void QueueDestory(QN **phead) {
assert(*phead&&phead);
//销毁队列从头节点开始释放
QN* tem = *phead;
//当前节点不为空，就一直执行
while (tem != NULL) {
//先将现在节点的下一个节点地址放在cur变量中
QN* cur = tem->Next;
free(tem);
tem = cur;
}
*phead = NULL;
}