目录

一.栈和队列的概念

🍓1.栈的概念：🍓

🍋2.队列的基本概念🍋

二.栈和队列的基本操作

🍉1.栈的基本操作🍉

初始化

入栈 

出栈

获取栈顶元素

获取栈元素个数

判空

销毁

🥭2.队列的基本操作🥭

初始化

入队

出队

获取队头元素

获取队尾元素

获取元素个数

判空

销毁

---

🍒一.栈和队列的概念🍒

🥭1.栈的概念：🥭

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

压栈：栈的插入操作称为进栈/压栈/入栈。插入数据在栈顶插入

出栈：栈的删除操作称为出栈。删除数据也在栈顶删除

栈的实现：栈的实现有数组和链表两种方式，相对而言数组的结构实现更优一些，因为数组在尾部插入数据更加方便和高效

🍎2.队列的基本概念🍎

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

入队列：进行插入操作的一端称为 队尾

出队列：进行删除操作的一端称为 队头

 

 

队列的实现：队列的实现有数组和链表两种方式，使用链表的结构更优一些，因为其头出数据更加方便和高效，而数组头出数据效率较低

🍓二.栈和队列的基本操作🍓

🍍1.栈的基本操作🍍

        栈采用数组实现更优，栈的基本操作有初始化、入栈、出栈、返回栈顶元素、获取栈元素个数、判空、销毁等操作

数组实现：

typedef int STDataType;
 typedef struct Stack
{
	STDataType* a;
	int top;//栈顶元素的下一个位置
	int capacity;//栈的最大容量
}Stack;

初始化

        栈的初始化需要给栈开辟一定的空间，top指针为栈顶元素的下一个元素，一开始栈没有元素，故将top置为0，然后给capacity一个值，这里我们设定为4，后续空间不够时再动态扩容

void StackInit(Stack* ps)
{
	assert(ps);
	ps->a = (STDataType *)malloc(sizeof(STDataType)*4);//申请空间
	if (ps->a ==NULL)//申请失败则报错
	{
		perror("error:ps->a");
		return;
	}
	ps->top = 0;//栈顶指向当前元素的下一个位置
	ps->capacity = 4;//初始容量为4
}

入栈 

        栈的入栈步骤：首先判断栈是否已满，若栈满则需要扩容，这里我们将最大容量翻倍，即增容为原来容量的2倍，扩容后再将值赋给top位置，top加1，若栈未满则直接将值赋给top位置，top加1

void StackPush(Stack* ps, STDataType data )
{
	assert(ps);
	if (ps->top >= ps->capacity)//栈顶下标大于最大容量则扩容
	{
		ps->capacity = ps->capacity * 2;//容量翻倍
		ps->a = (STDataType*)realloc(ps->a, ps->capacity*sizeof(STDataType));
	}
	ps->a[ps->top++] = data;//元素入栈，栈顶指针+1
}

出栈

        栈的出栈步骤为：首先判断栈是否为空，为空则不能出栈，直接报错，若栈不为空则将top减1即可

void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->top != 0);//栈为空则直接报错
	ps->top--;//出栈，即将栈顶指针减1
}

获取栈顶元素

        获取栈顶元素首先需要判断栈是否为空，若栈为空则直接报错，若栈不为空，因为top为栈顶元素的下一个位置，故栈顶元素下标为top-1，返回top-1下标的值即可

STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->top != 0);//栈为空则直接报错
	return ps->a[ps->top - 1];//返回栈顶元素
}

获取栈元素个数

        由于top为栈顶元素的下一个位置，故其值就为栈元素的个数，将其返回即可

int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;//返回栈顶指针
}

判空

        栈的判空只需判断top是否为0，如果为0则说明栈没有元素即栈空，返回真，若不为0说明栈有元素即栈不为空，返回假

int StackEmpty(Stack* ps)
{
	assert(ps);
	if (ps->top == 0)//栈顶指针为0则说明栈空
		return 1;
	return 0;
}

销毁

        栈的销毁只需将在堆上申请的数组空间给释放，然后指向该空间的指针置空，栈的top和最大容量置为0

void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->a);//释放指针指向的空间
	ps->a = NULL;
	ps->top  = ps->capacity = 0;
}

🍑2.队列的基本操作🍑

        队列由单链表实现结构更优，由于队列有队头和队尾两个指针，故我们用一个结构体将两个指针封装起来，队列的基本操作有初始化、入队、出队、获取队头元素、获取队尾元素、获取队列元素个数、判空、销毁等操作

单链表实现：

typedef int QDataType;
typedef struct QListNode
{
	struct QListNode* next;
	QDataType data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* front;
	QNode* rear;
}Queue;

初始化

        队列的初始化只需将两个指针都置为空即可

void QueueInit(Queue* q)
{
	assert(q);
	//队头和队尾指针置为空
	q->front = NULL;
	q->rear = NULL;
}

入队

        队列的入队步骤：首先新建一个节点，再判断是否是第一次入队，即如果队列为空，则让队头和队尾指针都指向该节点，如果队列不为空，则类似于链表的尾插，将队尾指针rear指向的节点的next指向新节点，再将队尾指针rear指向新节点，即实现入队

void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));//创建一个新的节点
	newnode->data = data;
	if (q->rear ==NULL)//如果队列为空队列，则让队头和队尾都指向该新节点
	{
		q->rear = q->front = newnode;
	}
	else
	{	//不为空则将新节点进行尾插操作
		q->rear->next = newnode;
		q->rear = newnode;
	}
}

出队

        队列的出队步骤：首先判断队列是否为空，为空则直接报错，再判断队列是否只有一个元素，只有一个元素则将该元素删除，队头和队尾指针置为空，如果队列不只有一个元素，则类似于单链表的头删，定义一个临时指针指向队头元素，然后让队头指针往后走一步，再删除临时指针指向的元素即可

void QueuePop(Queue* q)
{
	assert(q);
	assert(q->rear != NULL);//队列为空则报错
	if (q->rear == q->front)//如果队列只有一个元素，则将该元素出列，队头队尾指针置为空
	{
		free(q->front);
		q->rear = q->front = NULL;
	}
	else
	{	//如果队列不只有一个元素，则进行出列操作，即头删操作
		QNode* cur = q->front;
		q->front = q->front->next;
		free(cur);
	}
}

获取队头元素

        获取队头元素首先判断队头指针是否为空，为空则返回空，否则则直接返回队头指针指向的元素

QDataType QueueFront(Queue* q)
{
	assert(q);
	if (q->front == NULL)
		return NULL;
	return q->front->data;//返回队头指针指向的元素值
}

获取队尾元素

        获取队尾元素首先判断队尾指针是否为空，为空则返回空，不为空则直接返回队尾指针指向的元素

QDataType QueueBack(Queue* q)
{
	assert(q);
	if (q->rear == NULL)
		return NULL;
	return q->rear->data;//返回队尾指针指向的元素值
}

获取元素个数

        获取元素个数首先判断队列是否为空，为空则返回0，不为空则定义一个遍历指针，从队头遍历到队尾，遍历该队列统计元素个数即可

int QueueSize(Queue* q)
{
	assert(q);
	if (q->rear == NULL)//队列为空则返回空
		return 0;
	QNode* cur = q->front;//定义遍历指针
	int num = 1;//统计元素个数
	while (cur != q->rear)//遍历统计元素个数
	{
		num++;
		cur = cur->next;
	}
	return num;
}

判空

        队列的判空只需判断队头指针等于队尾指针且都为空即可，若是则队列为空，否则不为空

int QueueEmpty(Queue* q)
{
	assert(q);
	if((q->front == q->rear) && (q->front == NULL))//队头队尾指针相等且都为空则队列为空
		return 1;
	return 0;
}

销毁

        队列的销毁首先判断队列是否为空，为空则直接返回，不为空则定义遍历指针，从队头遍历到队尾依次删除节点即可，最后将队头和队尾指针置空即可

void QueueDestroy(Queue* q)
{
	assert(q);
	if (QueueEmpty(q))//队列为空则直接返回
		return;
	if (q->front == q->rear)//队列只有一个元素，删除这个元素，将两个指针置空
	{
		free(q->front);
		q->front = q->rear = NULL;
	}
	else
	{
		QNode* cur = q->front;//定义临时指针
		while (cur != q->rear)//遍历删除元素
		{
			q->front = q->front->next;
			free(cur);
			cur = q->front;
		}
		free(q->rear);//删除队尾
		q->front = q->rear = NULL;//两个指针置空
	}
}

好啦，栈和队列就先学习到这，如果对您有所帮助，欢迎一键三连~

种一棵树最好的时间是十年前，其次是现在