主页：HABUO🍁主页：HABUO。

🍁如果再也见不到你󿀌早上好，祝你早上好，#xff00c;午安，晚安🍁

1.栈。

1.1 栈的定义和结构。

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

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

出栈：栈的删除操作叫做出栈。数据也在栈顶。。 如下图所示，#xff1a;

总结：其实栈是一个后进先出的容器，注意。可边进边出。，什么意思࿱？f;例如，上图�a1进入栈后，a2可以再次进入栈，因此，一个入栈序列可以对应多个出栈序列。。 。

1.2 栈的实现。

分析：我们之前学过顺序表，也就是可以动态增容的数组，也学过链表，无论是带头不带头，循环不循环，双向不双向，我们都做到了吗？然后我们思考一个问题，哪种结构更适合实现栈？无论顺序表󿀌我们是否都实现了链表的增删查改，因此，它们都可以实现，但是使用顺序表更方便，因为你想，我们只需要在一端操作#xff0c;这里有一个现成的数组形式，为何要选择更复杂的结构😅？;，因此，我们选择顺序表来实现栈。。

一般思想见下图：

事实上，顺序表已经在我们面前实现了c;其实现栈只不过是注意一些细节，不再详细赘述。

typedef int StackDataType;typedef struct Stack{ 	StackDataType* _Array;	int _top;	int _capacity;}Stack;///栈初始化void StackInit(Stack* s);///销毁栈void StackDestory(Stack* s);//进栈void StackPush(Stack* s, StackDataType x);//出栈void StackPop(Stack* s);///获得栈顶元素StackDatatatypepe StackTop(Stack* s);///Int获得栈有效元素数量 StackSize(Stack* s);///判断栈是否空，空返回1󿀌非空返回0int StackEmpty(Stack* s);

这是整个工程文件的第一份文件，各种结构和接口的放置栈声明，我们主要是出栈入栈操作，因此，与顺序表相比，，添加、删除和修改的界面相对较少，下面逐一实现。

///栈初始化void StackInit(Stack* s){ 	assert(s);	s->_Array = (Stack*)malloc(sizeof(Stack) * ARRAYINITSIZE);	s->_top = 0;	s->_capacity = ARRAYINITSIZE;}///销毁栈void StackDestory(Stack* s){ 	assert(s);	free(s->_Array);	s->_Array = NULL;	s->_top = s->_capacity = 0;}。

这里需要注意的是堆栈初始化的地方，我们可以把指针放在NULL，但是，当我们进入栈时，我们会遇到麻烦，需要判断情况，因此，我们在初始化时直接开辟了一个空间，以后再判断，当我们进入栈时，我们只需要判断栈是否满足，满了就增容，不满直接插入数据。

//进栈void StackPush(Stack* s, StackDataType x){ 	assert(s);	if (s->_top == s->_capacity)	{ 		s->_capacity *= 2;		Stack* temp = (Stack*)realloc(s->_Array, sizeof(Stack) * s->_capacity);		if (temp == NULL)		{ 			printf("内存不足\n");			exit(-1);		}		else		{ 			s->_Array = temp;		}	}	s->_Array[s->_top] = x;	s->_top++;}//出栈void StackPop(Stack* s){ 	assert(s);	assert(s->_top != 0);	s->_top--;}。= 0);	s->_top--;}。

与之前的顺序表相比，入栈操作的增删查改操作，这里太简单了，不要重复，看看前面博客顺序表的实现就可以了解了。这里需要注意。assert(s->top != 0)，我们在这里加一个断言，防止栈里没有元素，我们还进行出栈操作。。

其他接口只需返回相应的变量，这里会有问题吗？#xff1f;由于直接返回相应的变量󿀌那我们为什么要建立一个接口，事实上，这是为了保持我们接口的一致性，可以直接调用。 。

2.队列。

2.1 队列的定义和结构。

队列：只允许在一端插入数据操作，在另一端删除数据操作的特殊线性表。，先进先出的队列 FIFO(First In First Out)，如下图所示，结构如下图所示a;

入队列༚插入操作的一端称为队尾。

队列：删除操作的一端称为队长 。

总结：排队的情况和我们每天排队的情况差不多，谁先进谁先出，绝对没有后进先出的情况，所以，也就是说，一个入队序列只能对应一个出队序列。

2.2 实现队列。

分析：与上述栈的实现相同，我们采用哪种结构来实现？因为这里需要一头进󿀌另一端出来󿀌只要是这种两端操作，我们的顺序表不是很好，因为你只需要头部操作，顺序表后面的数据是否需要移动，那么这里的效率就会下降。，所以顺序表不太好，那个链表用哪种形式？事实上，单链表在这里的功能还不够，为何࿱？f;由于我们只需要一个头部删除或尾部插入，这是单链表中最基本的功能，如果我们能使用单链表，我们应该尽量不要使用其他形式的链表，因为毕竟没必要󿀌为什么要多存地址？综上所述，，我们以单链表的形式实现队列。。

typedef int QueueDataType;typedef struct QueueListNode{ 	QueueDataType _data;	struct QueueListNode* _next;}QueueListNode;typedef struct Queue{ 	QueueListNode* _front;	QueueListNode* _rear;}Queue;// 初始化队列 void QueueInit(Queue* q);// 队尾入队列 void QueuePush(Queue* q, QueueDataType data);// 队头出队列 void QueuePop(Queue* q);// 获取队列头部元素 QueueDataType QueueFront(Queue* q);// 获取队列的尾部元素 QueueDataType QueueBack(Queue* q);// 获取队列中有效元素的数量 int QueueSize(Queue* q);// 检测队列是否空，如果空返回非零结果，若非空返回0 int QueueEmpty(Queue* q);// 销毁队列 void QueueDestroy(Queue* q);

这是整个工程文件的第一份文件，各种结构和接口放置队列的声明，事实上，与栈接口的实现基本相同，这里唯一需要注意的是。我们通过一个结构存储了连续的头尾指针，为什么要这样做？目的是使我们的界面保持一致性，如果不这样做，有些接口需要二级指针，在这里，我们传递结构体的地址是否可以操作结构体中的变量，换句话说，这些指针能改变࿰吗？c;而不仅仅是那些形参的变化。我们通过一个结构存储了连续的头尾指针，为什么要这样做？目的是使我们的界面保持一致性󿀌如果不这样做，有些接口需要二级指针，在这里，我们传递结构体的地址是否可以操作结构体中的变量，换句话说，这些指针能改变࿰吗？c;而不仅仅是形参的变化。

，我们主要进行入队列和出队列操作，因此，与单链表相比，，添加、删除和修改的界面相对较少，以下是对其的一一实现。 。

// 队尾入队列 void QueuePush(Queue* q, QueueDataType data){ assert(q); if (q->_front == NULL) { QueueDataType* temp = (QueueListNode*)malloc(sizeof(QueueListNode)); if (temp == NULL) { printf("内存不足\n"); exit(-1); } else { q->_front = q->_rear = temp; } } else { QueueListNode* temp = (QueueListNode*)malloc(sizeof(QueueListNode)); if (temp == NULL) { printf("内存不足\n"); exit(-1); } else { q->_rear->_next = temp; q->_rear = temp; } } q->_rear->_data = data; q->_rear->_next = NULL;}// 队头出队列 void QueuePop(Queue* q){ assert(q); assert(q->_front != NULL); QueueListNode* frontNext = q->_front->_next; free(q->_front); q->_front = frontNext;}。= NULL); QueueListNode* frontNext = q->_front->_next; free(q->_front); q->_front = frontNext;}。

看这里的入队列就分情况，因为这和顺序表不一样󿀌如果我们在初始化时没有直接开放空间，为什么࿱？f;因为你不知道该放什么数据，即使你建立了一个节点，进入队列时，还是要分情况，一是第一次进入队列，您只需将初始节点的val转换为所需的数据，如果要建立新的节点，你需要另一个malloc节点。所以无论如何都需要分为两种情况，顺序表不需要这样，我们可以通过下标来访问顺序表。

其他接口类似于返回各种变量的数据，不再赘述。

总结：我们知道两个新的数据结构，我们会有这样的问题吗？这些数据结构在哪里可以使用？栈，其实用处挺大的，例如，如果我们想设计一个迷宫游戏，#xff00c;当我们走到死路的时候，我们会后退吗，这涉及到一个后进先出的问题，利用我们的堆栈来实现这一目标。队列󿼌࿰在日常生活中仍然很常见c;我们都去过银行或者什么办公室󿀌是否有排队报号机，这是一个非常典型的队列问题，先排队，到了就出队列。因此，我们今天学到的两个数据结构，肯定会启发我们，希望大家都能有所收获。💯

🏋并非每一粒种子都能开花，但播种的种子比荒芜的荒野强百倍🏋