数据结构与算法——栈和队列

栈

概念与结构

栈：⼀种特殊的线性表，其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作的⼀端称为栈顶，另⼀端称为栈底。栈中的数据元素遵守后进先出的原则。(先进的后出，后进的先出)

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

栈的底层结构选型：链表 or 数组？

• 使用链表来说，栈顶是经常操作的一端，为了降低时间复杂度，将链表的头看作栈顶，尾看作栈底，入栈的时间复杂度则为O(1),出栈时间复杂度O(1)。

• 使用数组来说，尾部看作栈顶，头部看作栈顶，入栈、出栈时间复杂度为O(1)。

他们的入栈、出栈操作时间复杂度都一样，但是我们选择数组更好，因为链表是独立的结点，每次操作都要申请一个新的结点，8个字节，空间的消耗更大，所以底层选择数组。所以物理、逻辑结构都是是线性的。

栈的实现

栈的初始化

首先定义栈的结构，然后定义一个初始化函数，因为对形参的改变需要影响实参，所以传址调用，且在函数中用一级指针接收。

头文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//定义栈的结构
typedef int StackDataType;
typedef struct Stack {StackDataType* arr;int top;     //指向栈顶的位置int capacity;//栈的容量
}Stack;//初始化
void StcakInit(Stack* ps);//形参的变化要影响实参，所以要传传址，用一级指针接受

实现文件

#include"Stack.h"//初始化
void StcakInit(Stack* ps) //ps是形参，形参的初始化要改变实参，所以传址
{ps->arr = NULL;ps->top = ps->capacity = 0;
}

测试文件

#include"Stack.h"void test01()
{Stack st;StackInit(&st);//传址，st是实参
}int main()
{test01();return 0;
}

栈的销毁

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

判断栈是否为空

bool 函数是一种返回 布尔值（true 或 false） 的函数，通常用于逻辑判断。在 C 语言中，bool 类型需要包含 <stdbool.h> 头文件才能使用。
检查栈是否为空：

• 如果 ps->top == 0（栈空），返回 true。

• 否则返回 false。

//判断栈是否为空
bool StackEmpty(Stack* ps)
{assert(ps);return ps->top == 0; //如果 top == 0，返回 true（栈空）；否则返回 false
}

入栈

定义一个入栈的函数，一个保存结构体地址的指针变量，一个需要插入的数据，因为进行了初始化，所以要进行增容，这里需要使用realloc(指向之前分配的内存块的指针，新的内存块大小（字节数）)，然后将新增容的空间和重新分配内存块的大小赋值给原来的capacity和arr。

//插入数据-栈顶入数据
void StackPush(Stack* ps, StackDataType x)
{assert(ps);if (ps->top == ps->capacity){//增容int newCapacity = ps->capacity = 0 ? 4 : 2 * ps->capacity;StackDataType * tmp = (StackDataType*)realloc(ps->arr, newCapacity * sizeof(StackDataType));if (tmp == NULL){perror("relloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}ps->arr[ps->top++] = x;
}

出栈

因为栈为空返回的是true，所以这里要取反

//出栈-后进的先出，先进的后出
void StackPop(Stack* ps)
{assert(!StackEmpty(ps));--ps->top;
}

取栈顶元素

不同于出栈的是不会减少栈中的元素个数

//取栈顶元素
StackDataType* StcakTop(Stack* ps)
{assert(!StackEmpty(ps));return ps->arr[ps->top - 1];
}

栈中有效元素个数

int StackSize(ST* ps)
{return ps->top;
}

队列

概念与结构

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

⼊队列：进⾏插⼊操作的⼀端称为队尾
出队列：进⾏删除操作的⼀端称为队头

队列的底层结构如何选型？

数组：选择最后为队尾时->入队O(1),出队O(N)    选择第一个数据为队尾时->入队O(N),出队O(1)
链表：单链表时，第一个结点为队头，尾结点为队尾时，入队O(N)（因为需要找尾结点），出队O(1)双向链表时，这时入队，出队的时间复杂度都为O(1)，但是每个结点的空间消耗的太大。

优化单链表：在定义第一个结点的指针为phead的基础上，定义尾结点的指针为ptail，入队时候直接再ptail后面插入结点，这样也入队，出队时间复杂度都为O(1)。

队列的实现

队列结点结构

typedef int QNDataType;//队列结点的结构
typedef struct QueueNode {QNDataType data;struct QueueNode* next;
}QNode;

队列结构

//队列的结构
typedef struct Queue {QNode* phead;QNode* ptail;
}Q;

初始化队列

//队列的初始化
void QueueInit(Q* pq)
{assert(pq);pq->phead = pq->ptail = NULL;
}

队列判空

//判空
bool QueueEmpty(Q* pq)
{assert(pq);return pq->phead == NULL;
}

销毁队列

pcur从头开始遍历（条件：pcur不为空），然后将pcur的下一个结点存起来。释放pcur，将存起来的结点赋给pcur，最后手动将phead和ptail置空。

//销毁队列
void QueueDestroy(Q* pq)
{assert(pq);QNode* pcur = pq->phead;while(pcur){QNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;//pq->size = 0;
}

入队列，队尾

队列不为空：pq->ptail->next = newnode，然后将pq->ptail = pq->ptail->next

为空的时候：
phead = ptail = newnode

//队尾入数据
void QueuePush(Q* pq, QNDataType x)
{assert(pq);//申请结点空间QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;//队列为空if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else {pq->ptail->next = newnode;}pq->ptail = newnode;
}

出队列，队头

先将phead->next保存下来，然后释放phead，然后phead = phead->next ，只有一个结点（头，尾都指向同一个节点）phead和ptail都需要置空

//队头出数据
void QueuePop(Q* pq)
{//判空assert(!QueueEmpty(pq));//只有一个结点if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else {QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}
}

取队头数据

//取队头数据
QNDataType QueueFront(Q* pq)
{assert(!QueueEmpty(pq));return pq->phead->data;
}

取队尾数据

//取队尾数据
QNDataType QueueBack(Q* pq)
{assert(!QueueEmpty(pq));return pq->ptail->data;
}

队列有效数据个数

第一种方式：遍历链表——适用于不会频繁调用队列有效数据个数的场景

//队列有效元素个数
int QueueSize(Q* pq)
{assert(pq);//第一种方式：遍历链表——适用于不会频繁调用队列有效数据个数的场景QNode* pcur = pq->phead;int size = 0;while (pcur){size++;pcur = pcur->next;}return size;}

第二种方式：遍历链表——适用于频繁调用队列有效数据个数的场景（完整代码）
//return pq->size;

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int QNDataType;typedef struct QueueNode {QNDataType data;struct QueueNode* next;
} QNode;typedef struct Queue {QNode* phead;QNode* ptail;int size;  // 新增：记录队列元素个数
} Q;void QueueInit(Q* pq);
bool QueueEmpty(const Q* pq);
void QueuePush(Q* pq, QNDataType x);
void QueuePop(Q* pq);
QNDataType QueueFront(const Q* pq);
QNDataType QueueBack(const Q* pq);
int QueueSize(Q* pq);  // 新增：O(1) 方式
void QueueDestroy(Q* pq);

#include "Queue.h"void QueueInit(Q* pq) {assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}bool QueueEmpty(const Q* pq) {assert(pq);return pq->size == 0;  // 直接判断 size
}void QueuePush(Q* pq, QNDataType x) {assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL) {perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;if (pq->phead == NULL) {pq->phead = pq->ptail = newnode;} else {pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;  // 更新 size
}void QueuePop(Q* pq) {assert(!QueueEmpty(pq));QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;if (pq->phead == NULL) {pq->ptail = NULL;}pq->size--;  // 更新 size
}QNDataType QueueFront(const Q* pq) {assert(!QueueEmpty(pq));return pq->phead->data;
}QNDataType QueueBack(const Q* pq) {assert(!QueueEmpty(pq));return pq->ptail->data;
}int QueueSize(Q* pq) {assert(pq);return pq->size;  // O(1) 直接返回
}void QueueDestroy(Q* pq) {assert(pq);QNode* pcur = pq->phead;while (pcur) {QNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;  // 重置 size
}