数据结构_栈和队列(Stack & Queue)

✨✨所属专栏：数据结构✨✨

✨✨作者主页：嶔某✨✨

栈：

代码：function/数据结构_栈/stack.c · 钦某/c-language-learning - 码云 - 开源中国 (gitee.com)https://gitee.com/wang-qin928/c-language-learning/blob/master/function/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84_%E6%A0%88/stack.c

栈的概念及结构

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

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

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

栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

其实单链表也可以很好的实现栈，我们将只需要进行头插和头删就行了（避免在尾部要进行找尾的循环操作）。

这里我们用顺序表实现，要实现的接口都是和顺序表大同小异：

typedef int STDataType;

typedef struct Stack
{
	STDataType* data;
	int capacity;
	int top;
}ST;

void STInit(ST* pst);

void STDestroy(ST* pst);

void STPush(ST* pst, STDataType x);

void STPop(ST* pst);

STDataType STTop(ST* pst);

bool STEmpty(ST* pst);

int STSize(ST* pst);

队列：

代码：

function/队列/Queue.c · 钦某/c-language-learning - 码云 - 开源中国 (gitee.com)https://gitee.com/wang-qin928/c-language-learning/blob/master/function/%E9%98%9F%E5%88%97/Queue.c

队列的概念及结构

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

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

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

队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低（需要整体往前挪动）

我们这里都尽量选择时间复杂度小的算法来实现

实现接口：

typedef int QDataType;

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

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

void QueueInit(Queue* pq);//队列初始化

void Destory(Queue* pq);//销毁队列

void QueuePush(Queue* pq, QDataType x);//入队

void QueuePop(Queue* pq);//出队

int QueueSize(Queue* pq);//获得队列元素个数

QDataType QueueFront(Queue* pq);//取出队头的元素

QDataType QueueBack(Queue* pq);//取出队尾的元素

栈和队列这两个数据结构在之前的顺序表和链表的基础上没有增加什么难度，学习栈和队列真正有难度的地方在LeetCode上的OJ题。大家可以期待一下后续我在数据结构专栏的题目！

本期博客到这里就结束了，如果有什么错误，欢迎指出，如果对你有帮助，请点个赞，谢谢！