【数据结构】— 探索栈和队列的奥秘

关注小庄 顿顿解馋૮(˶ᵔ ᵕ ᵔ˶)ა
💡个人主页：9ilk
💡专栏：数据结构之旅

上回我们学习了顺序表和链表，今天博主来讲解两个新的数据结构 — 栈和队列 ， 请放心食用

文章目录

• 🏠 栈
• • 📒 何为栈
  • • 👿 栈后进先出是相对的
  • 📒 栈的实现
• 🏠 队列
• • 📒 何为队列
  • 📒 队列的实现

🏠 栈

对于这么坨书，我们要拿到最下面的书是不是要最后才能拿到；而对于最上面的书它是最晚放上去的却能最先拿到，这样的一个场景就跟我们接下来要介绍的栈类似 — Last in First out(后进先出)

📒 何为栈

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

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

👿 栈后进先出是相对的

由图中我们可知，栈的后进先出是对于同时在栈里的数据而言的

📒 栈的实现

通过前面的分析我们知道，我们需要一个栈顶来表示数据，这跟我们链表的头结点有点相似，但是对于单链表来说实现栈，尾部插入数据并不方便，因此我们选择数组实现栈

• 动态栈

typedef int Datatype;
typedef struct Stack
{
	Datatype* arr;
	int top;
	int capacity;
}ST;

• 栈的初始化与销毁

//初始化
void StackInit(ST* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->capacity = ps->top = 0;
}

关于top的初始化：1.top表示栈顶元素的下一个位置时，让top初始化为0，插入数据时先top后++ ；2.top表示栈顶元素 时，top初始化为-1，此时先++后再用top

// 销毁栈 
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->arr);
	ps->arr = NULL;
	ps->capacity = ps->top = 0;
}

• 栈的插入数据和删除数据
  这里有了前面顺序表的基础就很简单了，不过要注意压栈和出栈都是在栈顶

//入栈
void StackPush(ST* ps, Datatype data)
{
	assert(ps);
	if (ps->capacity == ps->top)
	{//扩容
		int newcapacity = 0;
		newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		Datatype* temp = (Datatype*)malloc(newcapacity * sizeof(Datatype));
		if (temp == NULL)
		{
			perror("malloc failed");
			return;
		}
		ps->arr = temp;
		ps->capacity = newcapacity;
	}
	//入栈
	ps->arr[ps->top++] = data;

}
//出栈
void StackPop(ST* ps)
{
	assert(ps);
	//栈不能为空
	assert(ps->top != 0);
	ps->top--;
}

• 获取栈顶元素

// 获取栈顶元素 
Datatype StackTop(ST* ps)
{
	assert(ps);
	//栈不能为空
	assert(ps->top != 0);
	return ps->arr[ps->top - 1];
}

• 判断是否为空

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0 ? 1 : 0;

}

• 获取栈中有效数据个数

// 获取栈中有效元素个数 
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

🏠 队列

栈是后进先出，那有我们的先进先出（First in First out）吗 ? 当然有，跟现实中我们排队买票一样，这样数据结构叫做队列

📒 何为队列

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

📒 队列的实现

由于我们是先进先出，出在队头出，进在队尾进，所以我们需要两个“指针”front 和 rear 来标识位置有效率些。

那用数组来实现好还是链表呢？

用数组的话不好出数据，所以我们这里推荐用链表实现；同时我们可以将front和rear封装进一个结构体这样比较省事

• 队列结构

typedef int Datatype;
typedef struct QNode
{
	Datatype data;
	struct QNode* next;
}QNode;


typedef struct Quque
{
	QNode* head;
	QNode* tail;
	int size;
}Quque;

注：我们可以定义一个size表示数据个数，弥补链表需要循环遍历确定数据个数的缺陷

• 队列的初始化和销毁

//队列的初始化和摧毁
void QuqueInit(Quque* pq)
{
	assert(pq);
	pq->size = 0;
	pq->head = pq->tail = NULL;
}
void QuqueDestroy(Quque* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;

}

• 入队和出队

出队就是链表的头删 入队就是尾插

//队列的入队列和出队列
void QuquePop(Quque* pq)
{
	assert(pq);
	assert(pq->head != NULL);//对嘞不能为空
	//0个结点

	//1个结点
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	pq->size--;
}
void QuquePush(Quque* pq, Datatype x)
{
	assert(pq);
	//申请新结点
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc failed");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->head == NULL)
	{//0个结点
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}

• 获取头元素和尾元素

//队列的头元素和尾巴元素
Datatype QuqueFront(Quque* pq)
{
	assert(pq);
	assert(pq->head != NULL);
	return pq->head->data;//设置两个指针进结构体的好处
}
Datatype QuqueBack(Quque* pq)
{
	assert(pq);
	assert(pq->head != NULL);
	return pq->tail->data;//设置两个指针进结构体的好处
}

• 队列是否为空

//队列是否为空
bool QuqueEmpty(Quque* pq)
{
	assert(pq);
	if (pq->size == 0)
	{
		return true;
	}
	else
	{
		return false;
	}

}

• 队列有效数据个数

//队列数据个数
int QuqueSize(Quque* pq)
{
	assert(pq);
	return pq->size;

}

本次分享到这就结束咯，下次我们将讲解链表，栈和队列的OJ题，敬请期待 ~