【数据结构】– 栈和队列

🌈 个人主页：白子寰
🔥 分类专栏：python从入门到精通，魔法指针，进阶C++，C语言，C语言题集，C语言实现游戏👈 希望得到您的订阅和支持~
💡 坚持创作博文(平均质量分82+)，分享更多关于深度学习、C/C++，python领域的优质内容！（希望得到您的关注~）

目录

栈

引入

介绍

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

为什么栈用顺序表而不用数组？ 

由于栈只用在同一端进行插入和删除，因此我们优先选择使用顺序表，因为在顺序表的末尾插入和删除的时间复杂度都是O(1)，并且操作简单 

 栈的实现

stack.h：结构体，栈的声明与定义

typedef int STDatatype;
typedef struct stack
{
	STDatatype* a;
	int top;        //栈顶
	int capacity;   //容量
}ST;

//栈的初始化
void STInit(ST* ps);
//栈的销毁
void STDestroy(ST* ps);
//压入
void STPush(ST* ps, STDatatype x);
//弹出/出栈
void STPop(ST* ps);
//取栈顶元素
STDatatype STTPop(ST* ps);
//栈的大小
int STSize(ST* ps);
//判断栈是否为空
bool STEmpty(ST* ps);

stack.c：栈的具体实现代码

栈的初始化

void STInit(ST* ps)
{
	assert(ps);

	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

压入

void STPush(ST* ps, STDatatype x)
{
	assert(ps);

    //如果栈顶 = 容量，满了
	if (ps->top == ps->capacity)
	{
        //扩容
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDatatype* tmp = (STDatatype*)realloc(ps->a, newcapacity * sizeof(STDatatype));
		if (tmp == NULL)
		{
			perror("realloc");
			return;
		}
		//赋值
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	//新数据给值
	ps->a[ps->top] = x;
	ps->top++;
}

弹出 

void STPop(ST* ps)
{
	assert(ps);
	//判断栈是否为空
	assert(!STEmpty(ps));

	//栈顶元素删除
	ps->top--;
}

取栈顶元素

STDatatype STTPop(ST* ps)
{
	assert(ps);
	//判断栈是否为空
	assert(!STEmpty(ps));

	return ps->a[ps->top - 1];//栈顶元素下标
}

栈的大小 

int STSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

判断栈是否为空

bool STEmpty(ST* ps)
{
	assert(ps);

    //为空返回True,不为空返回False
	return ps->top == 0;
}

栈的销毁

void STDestroy(ST* ps)
{
    //判断穿的指针是否有效
	assert(ps);

    //先释放，后置空
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

Test.c：栈的测试

int main()
{
	ST st;
    //初始化
	STInit(&st);

    //压入
	STPush(&st, 1);//1
	STPush(&st, 2);//1 2 
	STPush(&st, 3);//1 2 3 
	STPush(&st, 4);//1 2 3 4
	
    //取栈顶元素
	int top = STTPop(&st);//4
	//printf("%d ", top);//4
	
    //弹出
	STPop(&st);//1 2 3

    //压入
	STPush(&st, 5);//1 2 3 5 
	STPush(&st, 6);//1 2 3 5 6

	while (!STEmpty(&st))//栈不为空
	{
		int top = STTPop(&st);//6 5 3 2 1
		printf("%d ", top);	  //6 5 3 2 1
		STPop(&st);
	}
	
    //摧毁
	STDestroy(&st);
	return 0;
}

队列

引入

介绍

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 
入队列：进行插入操作的一端称为队尾 
出队列：进行删除操作的一端称为队头

为什么队列选择链表而不用数组？ 

由于队列需要在队列两端进行插入或删除，因此我们优先选择链表来进行实现。当然使用数组实现也可以，只是数组在头部插入和删除元素需要O(n)的时间复杂度，因此选择链表更优。 

队列实现

Queue.h：结构体，队列的声明和定义

#pragma once

#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int QueDatatype;
typedef struct QueueNode
{
	int val;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Que;

//队列初始化
void QueueInit(Que* pq);
//队列销毁
void QueueDestroy(Que* pq);

// 队尾入队列
void QueuePush(Que* pq, QueDatatype x);
// 队头出队列
void QueuePop(Que* pq);
//获取队列头部元素
QueDatatype QueueFront(Que* pq);
//获取队列尾部元素
QueDatatype QueueBack(Que* pq);
//判断队列中有效元素
bool QueueEmpty(Que* pq);
//队列中有效元素个数
int QueueSize(Que* pq);

Queue.c：队列函数具体实现

队列初始化

void QueueInit(Que* pq)
{
	assert(pq);

    //一开始队列为空
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;     //队列大小
}

队尾入队列（数据）

void QueuePush(Que* pq, QueDatatype x)
{
	assert(pq);

    //扩容
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc");
		return;
	}
    //给值
	newnode->val = x;
	newnode->next = NULL;

	//队列不止一个元素
	if (pq->ptail)
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	//队列只有一个元素
	else
	{
		pq->phead = pq->ptail = newnode;
	}

	pq->size++;
}

队头出队列（数据）

void QueuePop(Que* pq)
{
	assert(pq);
	assert(pq->phead);

	//队列中不止一个元素
	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--;
}

获取队列头部元素

QueDatatype QueueFront(Que* pq)
{
	assert(pq);
    //判断队列是否为空
	assert(pq->phead);

	return pq->phead->val;
}

获取队列尾部元素

QueDatatype QueueBack(Que* pq)
{
	assert(pq);
    //判断队列是否为空
	assert(pq->ptail);

	return pq->ptail->val;
}

判断队列是否为空

bool QueueEmpty(Que* pq)
{
	assert(pq);

    //为空返回True，不为空返回False
	return pq->size == 0;
}

队列中有效元素个数

int QueueSize(Que* pq)
{
	assert(pq);

	return pq->size;//队列大小
}

队列销毁

void QueueDestroy(Que* 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;
}

Test.c：队列的测试

#include"Queue.h"

int main()
{
	Que q;
	//初始化
	QueueInit(&q);

	//队尾进入队列
	QueuePush(&q, 1);//1
	QueuePush(&q, 2);//1 2
	QueuePush(&q, 3);//1 2 3
	QueuePush(&q, 4);//1 2 3 4

	printf("%d ", QueueFront(&q));//1
	printf("%d ", QueueBack(&q));//4

	//对头出队列
	QueuePop(&q);//2 3 4

	printf("%d ", QueueFront(&q));//2
	printf("%d ", QueueBack(&q));//4

	printf("%d", QueueSize(&q));//3


	//while (!QueueEmpty(&q))
	//{
	//	printf("%d ", QueueFront(&q));
	//	QueuePop(&q);
	//}

    //销毁
	QueueDestroy(&q);
	return 0;
}

***********************************************************分割线*****************************************************************************
完结！！！
感谢浏览和阅读。
等等等等一下，分享最近喜欢的一句话:

“没有永恒的梅雨季，只有久违的艳阳天”。

我是白子寰，如果你喜欢我的作品，不妨你留个点赞+关注让我知道你曾来过。
你的点赞和关注是我持续写作的动力！！！ 
好了划走吧。