数据结构【栈和队列】

目录

栈

概念与结构

栈的实现

栈的数据

栈的初始化

入栈

出栈

取栈顶元素

获取有效个数

栈的销毁

队列

概念与结构

队列的实现

队列的数据

初始化队列

入队列

出队列

取队头数据

取队尾数据

获取有效个数

队列销毁

栈的代码

stack.h

stack.c

test.c

队列的代码

Queue.h

Queue.c

test.c

---

栈

概念与结构

栈：⼀种特殊的线性表，其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作 的⼀端称为栈顶，另⼀端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插⼊操作叫做进栈/压栈/⼊栈，⼊数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

栈底层结构选型。

栈的实现⼀般可以使⽤数组或者链表实现，相对⽽⾔数组的结构实现更优⼀些。因为数组在尾上插⼊ 数据的代价⽐较⼩。

栈的实现

栈我们用顺序表来实现

栈的数据

arr就是数组，给arr申请空间后就是数组了。

空间就是有多少个空间。

栈顶是用来进栈和出栈的。

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int data;
typedef struct stack
{
	data* arr;//存放数值
	int koj;  //空间
	int top;  //栈顶
}stack;

---

栈的初始化

//初始化
void stack_csh(stack* r);

---

把arr置为空。

把koj和栈顶置为0。 

//初始化
void stack_csh(stack* r)
{
	assert(r);
	r->arr = NULL;
	r->koj = r->top = 0;
}

---

入栈

//入栈
void stack_push(stack* r, data x);

---

思路：先判断空间够不够，不够就2倍增容。

够的话，在栈顶的位置插入数据x。

//入栈
void stack_push(stack* r, data x)
{
	assert(r);
	//空间大小等于栈顶，就说明空间不够
	if (r->koj == r->top)
	{
		int koj1 = r->koj == 0 ? 4 : 2 * r->koj;
		stack* tab = (stack*)realloc(r->arr, sizeof(stack));
		if (tab == NULL)
		{
			perror("realloc");
			exit(1);
		}
		//把新申请的空间给r
		r->arr = tab;
		r->koj = koj1;
	}
	//空间够直接入栈
	r->arr[r->top] = x;
	r->top++;
}

---

void p()
{
	stack add;
	//初始化栈
	stack_csh(&add);
	//入栈
	stack_push(&add,1);
	stack_push(&add,2);
	stack_push(&add,3);
	stack_push(&add,4);
}
 
int main()
{
	p();
	return 0;
}

---

出栈

//布尔类型
bool buer(stack* r);
 
//出栈
void stack_pop(stack* r);

---

布尔类型，栈顶为0返回真，不为0返回假

//布尔类型
bool buer(stack* r)
{
	assert(r);
	return r->top == 0;
}

---

这里布尔类型接收真，假，这个逻辑非！把真变假，把假变真。

栈的删除操作叫做出栈。

我们只需要让，栈顶减减就行了

//出栈
void stack_pop(stack* r)
{
	assert(r);
	//布尔类型
	assert(!buer(r));
	r->top--;
}

---

出栈我们可以用循环来出栈，也可以用4条来出栈。

---

取栈顶元素

//取栈顶
data stack_top(stack* r);

---

---

arr数组的栈顶减1这个位置就可以拿到4。

//取出栈顶
data stack_top(stack* r)
{
	assert(r);
	assert(!buer(r));
	return r->arr[r->top - 1];
}

---

取出栈顶的数据赋值给tab，然后打印出来。然后出栈

	while (!buer(&add))
	{
		//取出栈顶数据
		data tab = stack_top(&add);
		printf("%d ", tab);
 
		//出栈
		stack_pop(&add);
 
	}

---

获取有效个数

//获取有效个数
data stack_size(stack* r);

---

我们直接返回top就行了。

//有效个数
data stack_size(stack* r)
{
	assert(r);
	return r->top;
}

---

当前有效个数是4，循环出栈后，有效个数是0

---

栈的销毁

//销毁
void xiaoh(stack* r);

---

判断arr这个空间是不是空，不是空释放arr空间，

koj和top赋值为0。

//销毁
void xiaoh(stack* r)
{
	assert(r);
	if (r->arr != NULL)
	{
		free(r->arr);
	}
	r->arr = NULL;
	r->koj = r->top = 0;
}

---

队列

概念与结构

概念：只允许在⼀端进⾏插⼊数据操作，在另⼀端进⾏删除数据操作的特殊线性表，队列具有先进先 出FIFO(First In First Out)

⼊队列：进⾏插⼊操作的⼀端称为队尾

出队列：进⾏删除操作的⼀端称为队头

队列底层结构选型

队列也可以数组和链表的结构实现，使⽤链表的结构实现更优⼀些，因为如果使⽤数组的结构，出队 列在数组头上出数据，效率会⽐较低。

---

队列的实现

创建3个文件，test.c测试文件，Queue.h头文件，Queue.c函数文件

---

队列的数据

typedef int data;
typedef struct queuedata//单链表
{
	data arr;//存放的数据
	struct queuedata* p;//指向下一个节点
}queuedata;
 
typedef struct Queue
{
	queuedata* to; //队头——单链表的 头节点
	queuedata* wei;//队尾——单链表的 尾节点
	int size; //有效个数
}Queue;

---

初始化队列

//初始化
void csh(Queue* r);

---

我们只需要把队头和队尾置为NULL，有效个数给0。

//初始化
void csh(Queue* r)
{
	assert(r);
	r->to = r->wei = NULL;
	r->size = 0;
}

---

---

入队列

入队列要从队尾进入

//入队，队尾
void dui_wei(Queue* r,data x);

---

思路:

1.申请一个单链表的空间，把x给新申请的空间，

2.判断队尾是不是空，是空当前链表里没有数据，所以让队头和队尾指向新申请的空间，

3.不是空，这个和单链表的尾插差不多，队尾的p指向新申请的空间，

有效个数加1

//入队尾
void dui_wei(Queue* r,data x)
{
	assert(r);
	//申请单链表空间
	queuedata* tab = (queuedata*)malloc(sizeof(queuedata));
	if (tab == NULL)
	{
		perror("malloc");
		exit(1);
	}
	//把x赋值给新申请空间的arr
	tab->arr = x;
	tab->p = NULL;
 
	//入队
	//判断队尾是不是空
	if (r->wei == NULL)
	{
		//是空，队头队尾指向新申请的空间
		r->to = r->wei = tab;
	}
	else//不是空
	{
		//队尾p指向新申请的空间
		r->wei->p = tab;
		//队尾走到新申请的空间
		r->wei = r->wei->p;
	}
	//有效个数加1
	r->size++;
}

---

我们可以看到插入了4个数据1,2,3,4，有效个数是4

void p()
{
	Queue add;
	//初始化
	csh(&add);
	//入队，尾
	dui_wei(&add, 1);
	dui_wei(&add, 2);
	dui_wei(&add, 3);
	dui_wei(&add, 4);
 
}
 
int main()
{
	p();
	return 0;
}

---

出队列

出队列：进⾏删除操作的⼀端称为队头

出队列要从队头出，

---

出队列，我们要用布尔类型，判断链表是不是空，是空不能出队列，报错。

//布尔类型
bool buer(Queue* r);
//出队列
void dui_to(Queue* r);

---

布尔判断队头是不是等于空，是返回真，不是返回假。

//布尔类型
bool buer(Queue* r)
{
	assert(r);
	return r->to == NULL;
}

---

思路：判断队头等于队尾，说明只有一个节点。直接释放就行了，

不等于说明有链表里有空间，把头节点的下一个节点给tab，释放头节点，再把tab给头节点。

有效个数减1

 
//出队,头
void dui_to(Queue* r)
{
	assert(r);
	//布尔类型，！把真变假，把假变真
	assert(!buer(r));
	//判断队头等于队尾，就说明只有一个节点
	if (r->to == r->wei)
	{
		//直接释放空间
		free(r->to);
		//把队头和队尾置为空
		r->to = r->wei = NULL;
	}
	else
	{
		//把队头的下一个节点给tab
		queuedata* tab = r->to->p;
		//释放当前队头节点
		free(r->to);
		//把tab节点给队头
		r->to = tab;
	}
	//有效个数减1
	--r->size;
}

---

取队头数据

//取队头数据
data qto(Queue* r);

---

直接返回头节点的数据就行了

//取队头数据
data qto(Queue* r)
{
	assert(r);
	assert(!buer(r));
	return r->to->arr;
}

---

printf("头:%d\n", qto(&add));

---

取队尾数据

//取队尾数据
data qwei(Queue* r);

---

直接返回队尾的数据就行了。

//取尾
data qwei(Queue* r)
{
	assert(r);
	assert(!buer(r));
	return r->wei->arr;
}

---

printf("尾:%d\n", qwei(&add));

---

获取有效个数

//有效个数
data size(Queue* r);

---

//有效个数
data size(Queue* r)
{
	assert(r);
	return r->size;
}

---

printf("size:%d\n", size(&add));

---

队列销毁

 
//销毁
void xiaoh(Queue* r);

---

把队头给tab，让tab循环销毁单链表，add保存头节点的下一个节点，释放头节点，把add给tab，

把队头和队尾置为NULL，有效个数给0。

//销毁
void xiaoh(Queue* r)
{
	assert(r);
	assert(!buer(r));
	//把队头给tab
	queuedata* tab = r->to;
	//循环销毁单链表
	while (tab != NULL)
	{
		//add保存头节点的下一个节点
		queuedata* add = tab->p;
		//释放头节点
		free(tab);
		//把add给tab
		tab = add;
	}
	//把队头和队尾置为空
	r->to = r->wei = NULL;
	//有效个数赋值为0
	r->size = 0;
}

---

栈的代码

stack.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int data;
typedef struct stack
{
	data* arr;//存放数值
	int koj;  //空间
	int top;  //栈顶
}stack;
 
//初始化
void stack_csh(stack* r);
//入栈
void stack_push(stack* r, data x);
 
//布尔类型
bool buer(stack* r);
 
//出栈
void stack_pop(stack* r);
 
//取栈顶
data stack_top(stack* r);
 
//获取有效个数
data stack_size(stack* r);
 
//销毁
void xiaoh(stack* r);

stack.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"stack.h"
 
//初始化
void stack_csh(stack* r)
{
	assert(r);
	r->arr = NULL;
	r->koj = r->top = 0;
}
 
//入栈
void stack_push(stack* r, data x)
{
	assert(r);
	//空间大小等于栈顶，就说明空间不够
	if (r->koj == r->top)
	{
		int koj1 = r->koj == 0 ? 4 : 2 * r->koj;
		stack* tab = (stack*)realloc(r->arr, sizeof(stack));
		if (tab == NULL)
		{
			perror("realloc");
			exit(1);
		}
		//把新申请的空间给r
		r->arr = tab;
		r->koj = koj1;
	}
	//空间够直接入栈
	r->arr[r->top] = x;
	r->top++;
}
 
//布尔类型
bool buer(stack* r)
{
	assert(r);
	return r->top == 0;
}
 
//出栈
void stack_pop(stack* r)
{
	assert(r);
	//布尔类型
	assert(!buer(r));
	r->top--;
}
 
//取出栈顶
data stack_top(stack* r)
{
	assert(r);
	assert(!buer(r));
	return r->arr[r->top - 1];
}
 
//有效个数
data stack_size(stack* r)
{
	assert(r);
	return r->top;
}
 
//销毁
void xiaoh(stack* r)
{
	assert(r);
	if (r->arr != NULL)
	{
		free(r->arr);
	}
	r->arr = NULL;
	r->koj = r->top = 0;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"stack.h"
 
 
void p()
{
	stack add;
	//初始化栈
	stack_csh(&add);
	//入栈
	stack_push(&add,1);
	stack_push(&add,2);
	stack_push(&add,3);
	stack_push(&add,4);
	//出栈
	/*stack_pop(&add);
	stack_pop(&add);
	stack_pop(&add);
	stack_pop(&add);*/
	printf("size:%d\n", stack_size(&add));
 
	while (!buer(&add))
	{
		//取出栈顶数据
		data tab = stack_top(&add);
		printf("%d ", tab);
 
		//出栈
		stack_pop(&add);
 
	}
	printf("size:%d\n", stack_size(&add));
 
	//销毁
	xiaoh(&add);
}
 
int main()
{
	p();
	return 0;
}

---

队列的代码

Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
 
typedef int data;
typedef struct queuedata//单链表
{
	data arr;//存放的数据
	struct queuedata* p;//指向下一个节点
}queuedata;
 
typedef struct Queue
{
	queuedata* to; //队头——单链表的 头节点
	queuedata* wei;//队尾——单链表的 尾节点
	int size; //有效个数
}Queue;
 
//初始化
void csh(Queue* r);
 
//入队，队尾
void dui_wei(Queue* r,data x);
 
//布尔类型
bool buer(Queue* r);
//出队列
void dui_to(Queue* r);
 
//取队头数据
data qto(Queue* r);
 
//取队尾数据
data qwei(Queue* r);
 
//有效个数
data size(Queue* r);
 
//销毁
void xiaoh(Queue* r);

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
 
//初始化
void csh(Queue* r)
{
	assert(r);
	r->to = r->wei = NULL;
	r->size = 0;
}
 
//入队尾
void dui_wei(Queue* r,data x)
{
	assert(r);
	//申请单链表空间
	queuedata* tab = (queuedata*)malloc(sizeof(queuedata));
	if (tab == NULL)
	{
		perror("malloc");
		exit(1);
	}
	//把x赋值给新申请空间的arr
	tab->arr = x;
	tab->p = NULL;
 
	//入队
	//判断队尾是不是空
	if (r->wei == NULL)
	{
		//是空，队头队尾指向新申请的空间
		r->to = r->wei = tab;
	}
	else//不是空
	{
		//队尾p指向新申请的空间
		r->wei->p = tab;
		//队尾走到新申请的空间
		r->wei = r->wei->p;
	}
	//有效个数加1
	r->size++;
}
//布尔类型
bool buer(Queue* r)
{
	assert(r);
	return r->to == NULL;
}
 
//出队,头
void dui_to(Queue* r)
{
	assert(r);
	//布尔类型，！把真变假，把假变真
	assert(!buer(r));
	//判断队头等于队尾，就说明只有一个节点
	if (r->to == r->wei)
	{
		//直接释放空间
		free(r->to);
		//把队头和队尾置为空
		r->to = r->wei = NULL;
	}
	else
	{
		//把队头的下一个节点给tab
		queuedata* tab = r->to->p;
		//释放当前队头节点
		free(r->to);
		//把tab节点给队头
		r->to = tab;
	}
	//有效个数减1
	--r->size;
}
 
//取队头数据
data qto(Queue* r)
{
	assert(r);
	assert(!buer(r));
	return r->to->arr;
}
 
//取尾
data qwei(Queue* r)
{
	assert(r);
	assert(!buer(r));
	return r->wei->arr;
}
 
 
//有效个数
data size(Queue* r)
{
	assert(r);
	return r->size;
}
 
//销毁
void xiaoh(Queue* r)
{
	assert(r);
	assert(!buer(r));
	//把队头给tab
	queuedata* tab = r->to;
	//循环销毁单链表
	while (tab != NULL)
	{
		//add保存头节点的下一个节点
		queuedata* add = tab->p;
		//释放头节点
		free(tab);
		//把add给tab
		tab = add;
	}
	//把队头和队尾置为空
	r->to = r->wei = NULL;
	//有效个数赋值为0
	r->size = 0;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
void p()
{
	Queue add;
	//初始化
	csh(&add);
	//入队，尾
	dui_wei(&add, 1);
	dui_wei(&add, 2);
	dui_wei(&add, 3);
	dui_wei(&add, 4);
 
	printf("头:%d\n", qto(&add));
 
 
	printf("尾:%d\n", qwei(&add));
	printf("size:%d\n", size(&add));
	//销毁
	xiaoh(&add);
}
 
int main()
{
	p();
	return 0;
}