数据结构--栈与队列【您的关注是我创作的动力！】

文章目录

栈
- 什么是栈？
- 栈的具体实现
队列
- 什么是队列？
- 队列的实现

栈

什么是栈？

栈也是顺序表的一种，栈的逻辑实现是先进后出（后进先出）就跟子弹夹一样。
具体逻辑就是它只允许在固定的一端进行数据的插入与删除，在数据插入与删除的一端称为
栈顶，另一端称为栈低
压栈：插入数据的名称，在栈顶插入数据
出栈：删除数据的名称,   在栈顶删除数据

如图：
在这里插入图片描述

栈的具体实现

我们可以用双链表，单链表，数组来实现栈，
本文采用数组来实现栈，因为双链表的指针太多，浪费，单链表每次创建节点都需要去用操作系统
也是比较浪费资源。

在这里插入图片描述

#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;
}