数据结构——栈和队列

HZzzzzLu

发布于 2024-11-26 08:18:23

4230

文章被收录于专栏：codingcoding

栈

栈的基本知识

栈的定义

栈（Stack）是一种遵循后进先出（Last In First Out，LIFO）原则的数据结构。它的操作主要限制在数据结构的一端，称为栈顶（Top）。

压栈：栈的插入操作叫进栈\压栈\入栈，入数据在栈顶出栈：栈的删除操作叫做出栈，出数据也在栈顶

基本特点

后进先出：最后添加到栈中的元素将是第一个被移除的元素。
限制性访问：只能在栈顶进行添加和删除操作。
动态大小：虽然传统的栈有固定大小，但现代编程语言通常提供动态栈，其大小可以随着元素的添加和移除而变化。

基本操作

Push：向栈顶添加一个新元素，使其成为新的栈顶。
Pop：移除栈顶元素，并返回它的值。
Peek/Top：查看栈顶元素的值，但不从栈中移除它。
IsEmpty：检查栈是否为空，即没有任何元素。
Size：获取栈中元素的数量。

适用场景

栈常用于管理函数调用的上下文，如递归调用和返回地址。
用于表达式求值，如算术表达式和逆波兰表达式。
用于回溯算法，如迷宫求解、图搜索等。
用于撤销操作（Undo操作）和恢复操作（Redo操作）。
用于括号匹配和语法分析。

栈的实现

数组实现：使用数组来存储栈的元素，并通过一个索引来追踪栈顶的位置。
链表实现：使用链表实现栈，允许在不需要移动其他元素的情况下动态地添加和删除元素。

相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小，而链表尾插每次都需要申请空间创建新的节点。

下面我们就用数组实现个动态栈。

定义

typedef int STDataType;

typedef struct Stack
{
	STDataType* arr;
	int top;         //堆顶
	int capacity;    //容量（能容纳数据个数的最大数量）
}ST;

各个接口的实现

初始化

//初始化
void STInit(ST* pst)
{
	assert(pst);

	pst->arr = NULL;

	//指向栈顶数据的下一个位置
	pst->capacity = pst->top = 0;

	//指向栈顶数据
	//pst->top = -1
}

注意这里的top的指向，是指向堆顶数据的下一个位置，所以top也可以代表栈的数据个数。

入栈

//入栈
void STPush(ST* pst, STDataType x)
{
	assert(pst);

	//扩容
	if (pst->capacity == pst->top)
	{
		int newcapacity = (pst->capacity == 0) ? 4  : 2 * pst->capacity;
		STDataType* tep = (STDataType*)realloc(pst->arr, newcapacity * sizeof(STDataType));
		if (tep == NULL)
		{
			perror("realloc");
			return;
		}
		pst->arr = tep;
		pst->capacity = newcapacity;
	}

	pst->arr[pst->top] = x;
	pst->top++;

}

这里的扩容需要注意，当pst->capacity == pst->top时，说明栈空间已经满了，需要扩容，一般是扩容2倍。

详细解释可以看数据结构——顺序表-CSDN博客中CheckCapacity函数的解释。

解决完扩容问题后，直接再top位置插入数据，并更新top就可以了。

出栈

移除栈顶元素，只需让top减减就行了。

注意判断栈不为空（top > 0）就可以了。

// 出栈
void STPop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);

	pst->top--;
}

取栈顶数据

top指向栈顶数据的下一位置，返回top-1的数据就行了。

还是要注意栈不为空。

//取栈顶数据
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);

	return pst->arr[pst->top - 1];
}

判空

看的是数据个数为不为0（top == 0），不是看容量（capacity）

//判空 看的是数据个数为不为0，不是看容量
bool STEmpty(ST* pst)
{
	assert(pst);

	return (pst->top == 0);
}

获取栈的数据个数

top就是栈的数据个数，返回就好了。

//获取数据个数
int STSize(ST* pst)
{
	assert(pst);

	return (pst->top);
}

销毁栈

用free释放掉申请的空间，然后把top和capacity置0就行了。

//销毁
void STDestroy(ST* pst)
{
	assert(pst);

	free(pst->arr);
	pst->arr = NULL;

	pst->capacity = pst->top = 0;
}

队列

队列的基本知识

队列的定义

队列（Queue）是一种遵循先进先出（First In First Out，FIFO）原则的线性数据结构。它在一端添加元素，在另一端移除元素。

基本特点

先进先出：最先添加到队列中的元素将是第一个被移除的元素。
两端操作：队列允许在一端（队尾）添加元素，在另一端（队首）移除元素。
有序性：元素保持它们被添加的顺序。

基本操作

Enqueue：在队尾添加一个新元素。
Dequeue：移除队首的元素，并返回它的值。
Peek/Front：查看队首元素的值，但不从队列中移除它。
IsEmpty：检查队列是否为空。
Size：获取队列中元素的数量。

适用场景

任务调度，如打印机任务队列。
缓冲区管理，如视频播放器的缓冲。
广度优先搜索（BFS）算法中管理待访问的节点。
模拟现实世界中的排队行为，如超市结账队伍。

队列的实现

数组实现：使用数组来存储队列的元素，需要两个指针或索引来分别追踪队首和队尾。
链表实现：使用链表来实现队列，允许在队尾添加和在队首删除元素，而不需要移动其他元素。
循环数组：使用固定大小的数组并通过模运算来实现队列的循环，避免在数组末尾重新分配空间。

队列的实现使用链表结构比较好，因为涉及到头插头删，使用数组有数据挪动，效率较为低下。

下面我们就用链表去实现队列。

定义

队列的节点和队列结构

typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType val;
}QNode;

typedef struct Queue
{
	QNode* phead;    //队列的头节点
	QNode* ptail;    //队列的尾节点
	int size;        //队列的数据个数
}Queue;

各个接口的实现

初始化

把phead和ptail置空，size置0即可。

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

插入数据到队尾（入队列）

创建一个新节点，然后尾插就行。

注意判断队列为空的情况就可以了。

// 队尾插入
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	//创建一个新节点，赋值x
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->next = NULL;
	newnode->val = x;

	//判断链表为空的情况
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}

	//更新size
	pq->size++;
}

删除队头的元素（出队列）

删除队列头节点，跟链表的删除基本一模一样。

注意判断队列元素不为0，以及元素个数为1的情况。

// 队头删除
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->size != 0);

	//判断是不是一个节点，特殊处理
	if (pq->size == 1)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}

	//更新size
	pq->size--;
}

取队头队尾的数据

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead);

	return pq->phead->val;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->ptail);

	return pq->ptail->val;
}

队列数据个数

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

	return pq->size;
}

队列的判空

判断队列的数据个数为不为0就行了，或者判断phead为不为空也可以。

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

	return pq->size == 0;
}

销毁队列

遍历队列，逐个销毁

void QueueDestroy(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;
		free(del);
	}

	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

拜拜，下期再见😏

摸鱼ing😴✨🎞