栈

栈的介绍

        栈的概念

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

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

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

        栈的结构

栈的实现

        初始化栈 StackInit

        需要用结构体创建一个栈，这个结构体需要包括栈的基本内容（栈，栈顶，栈的容量）。

typedef int STDataType;//栈中存储的元素类型（这里用整型举例）

typedef struct Stack
{
	STDataType* a;//栈
	int top;//栈顶
	int capacity;//容量，方便增容
}Stack;

        然后需要一个初始化函数，对刚创建的栈进行初始化。 

//初始化栈
void StackInit(Stack* pst)
{
	// 使用断言检查输入指针是否有效，确保不为空
    assert(pst);

    // 动态分配内存，为栈分配空间，初始可存储4个STDataType类型的元素
    pst->a = (STDataType*)malloc(sizeof(STDataType)* 4);

    // 初始化栈顶指针为0，表示栈当前为空，没有元素
    pst->top = 0;

    // 设置栈的初始容量为4，即栈目前最多可以容纳4个元素
    pst->capacity = 4;
}

        销毁栈 StackDestroy

        因为栈的内存空间是动态开辟出来的，当我们使用完后必须释放其内存空间，避免内存泄漏。

void StackDestroy(Stack* pst) 
{
    // 断言检查传入的栈结构体指针是否有效，确保它是指向一个已初始化的栈
    assert(pst != NULL);

    // 使用 free 函数释放栈中存储元素的数组所占用的内存防止内存泄漏
    free(pst->a);

    // 将栈的元素数组指针置为 NULL，这是一种安全措施，避免栈被释放后仍被当作有效指针使用
    pst->a = NULL;

    // 将栈顶指针 top 置为 0，这表示栈内已无任何元素，栈处于空状态
    pst->top = 0;

    // 将栈的容量 capacity 置为 0，代表栈当前没有存储能力，明确表示栈已经被销毁
    pst->capacity = 0;
}

        入栈 StackPush

        进行入栈操作前，我们需要检测栈的当前状态，若已满，则需要先对其进行增容，然后才能进行入栈操作。

void StackPush(Stack* pst, STDataType x) 
{

    // 断言检查栈结构体指针是否有效
    assert(pst);

    // 判断栈是否已满（栈顶索引等于栈的当前容量）
    if (pst->top == pst->capacity) 
    {
        // 如果栈满，则尝试重新分配内存，使栈容量翻倍
        STDataType* tmp =(STDataType*)realloc(pst->a,sizeof(STDataType)*pst->capacity * 2);

        // 检查重新分配内存是否成功
        if (tmp == NULL) 
        {
            // 若失败，输出错误信息，并调用 exit 函数结束程序运行
            printf("realloc fail\n");
            exit(-1);
        }

        // 若重新分配内存成功，更新栈的元素数组指针和容量
        pst->a = tmp;
        pst->capacity *= 2;
    }

    // 将新元素存入栈顶位置
    pst->a[pst->top] = x;

    // 更新栈顶索引，表示栈顶已移动至新的元素处
    pst->top++;
}

        出栈 StackPop

        出栈操作比较简单，即让栈顶的位置向下移动一位即可。但需检测栈是否为空，若为空，则不能进行出栈操作。

void StackPop(Stack* pst) 
{
    // 断言检查栈结构体指针是否有效
    assert(pst);

    // 断言检查栈是否为空，若为空则无法弹出元素
    assert(!StackEmpty(pst));

    // 栈顶指针向下移一位，相当于删除栈顶元素
    // 注意：这里假设移除元素后不需要返回其值，且不涉及内存释放
    pst->top--;

    // 注：在实际应用中，若栈顶元素包含动态分配的内存，此处还需要额外处理释放该内存
}

        获取栈顶元素 StackTop

        获取栈顶元素，即获取栈的最上方的元素。若栈为空，则不能获取。

STDataType StackTop(Stack* pst) 
{
    // 断言检查栈结构体指针是否有效
    assert(pst);

    // 断言检查栈是否为空，若为空则无法获取栈顶元素
    assert(!StackEmpty(pst));

    // 返回栈顶元素的值，栈顶元素的位置是栈顶指针减1
    // 注意：此处只读取栈顶元素而不改变栈的状态
    return pst->a[pst->top - 1];
}

        检查栈是否为空 StackEmpty

        检测栈是否为空，即判断栈顶的位置是否是0即可。若栈顶是0，则栈为空。

bool StackEmpty(Stack* pst) 
{
    // 断言检查栈结构体指针是否有效
    assert(pst);

    // 根据栈顶指针 top 的值判断栈是否为空
    // 当栈顶指针为 0 时，表示栈中没有元素，即栈为空
    return pst->top == 0;
}

        获取栈中有效元素个数 StackSize

        因为top记录的是栈顶，使用top的值便代表栈中有效元素的个数。

int StackSize(Stack* pst) 
{
    // 断言检查栈结构体指针是否有效
    assert(pst);

    // 栈顶指针 top 的值直接表示栈中有效元素的个数
    // 因为每当有元素入栈时，top加1；元素出栈时，top减1
    // 所以，top的值就反映了当前栈内实际存储了多少个元素
    return pst->top;
}

队列

队列的介绍

        队列的概念

        队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表。队列遵守先进先出 FIFO（First In First Out）的原则。

        入队列：队列的插入操作叫做入队列，进行插入操作的一端称为队尾。

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

        队列的结构

​

        队列的应用

        队列在生活中的运用非常广泛。很大一部分医院、营业厅以及餐厅等场所都存在队列的应用。
        例如，医院的采血环节的流程就运用了队列。在医院，如果我们要去抽血，我们首先要在旁边的抽号机抽取自己的编号，当某一个抽血窗口叫到你时，你便可以去抽血了。
        在这个过程中，当你在抽号机抽取到某一个编号，那么这个编号这时就从队尾入队列，当某一窗口抽血结束后，会在该队列中拿走一个编号并叫该编号的人到这个窗口接受抽血，那么这时这个编号就从队头出队列。

​

队列的实现

        首先我们需要创建一个结点类型，类型包含了该结点的数据和指向下一结点的指针。

typedef int QDataType;

typedef struct QListNode
{
    // 指向下一个节点的指针
    struct QListNode* next;
    
    // 节点所存储的数据
    QDataType data;
} QListNode;

        队列与普通链表又有所不同，普通链表只需要知道链表的头指针，而队列的信息包括了队头和队尾，所以我们需要再创建一个结构体用于存放队列的队头和队尾。 

typedef struct Queue
{
    // 队列头指针
    // 指向队列的第一个节点，当队列为空时，head 和 tail 都指向 NULL
    QListNode* head;

    // 队列尾指针
    // 指向队列的最后一个节点，每次有新元素入队时，都会更新 tail 指针
    QListNode* tail;
} Queue;

        初始化队列 QueueInit

         然后需要一个初始化函数，对刚创建的队列进行初始化。

void QueueInit(Queue* pq) 
{
    // 断言检查传入的队列结构体指针是否有效
    assert(pq);

    // 将队列的头指针 head 初始化为 NULL，表示队列当前为空，无元素
    pq->head = NULL;

    // 将队列的尾指针 tail 也初始化为 NULL，与 head 一致，表示队列为空
    // 这样设计的原因是，在队列为空时，头尾指针均指向 NULL；而在有元素入队时，tail 指针将指向最后一个元素
    pq->tail = NULL;
}

        销毁队列 QueueDestroy

        队列中的每一个结点所占用的内存空间都是动态开辟的，当我们使用完队列后需要及时释放队列中的每一个结点。

void QueueDestroy(Queue* pq) 
{
    // 断言检查传入的队列结构体指针是否有效
    assert(pq);

    // 创建一个临时指针 cur，初始化为队列的头节点
    QListNode* cur = pq->head;

    // 循环遍历队列中的每一个节点
    while (cur) 
    {
        // 将 cur 的下一个节点赋值给临时指针 next，保存下一个节点的地址
        QListNode* next = cur->next;

        // 释放当前节点 cur 的内存
        free(cur);

        // 移动 cur 指针至下一个节点
        cur = next;
    }

    // 清空队列的头指针和尾指针，将它们都设置为 NULL
    pq->head = NULL;
    pq->tail = NULL;
}

        队尾入队列 QueuePush

        入队列，即申请一个新结点并将其链接到队尾，然后改变队尾的指针指向即可。需要注意的是：若队列中原本无数据，那么我们只需让队头和队尾均指向这个新申请的结点即可。

void QueuePush(Queue* pq, QDataType x) 
{
    // 断言检查队列结构体指针是否有效
    assert(pq);

    // 分配内存创建一个新的节点
    QListNode* newnode = (QListNode*)malloc(sizeof(QListNode));
   
    // 检查内存分配是否成功
    if (newnode == NULL) 
    {
        // 若内存分配失败，输出错误信息并退出程序
        printf("malloc fail\n");
        exit(-1);
    }

    // 将新节点的数据域设置为要插入的元素值 x
    newnode->data = x;

    // 新节点的下一节点指针初始化为 NULL
    newnode->next = NULL;

    // 判断队列是否为空
    if (pq->head == NULL) 
    {
        // 若队列为空，则新节点既是头节点也是尾节点
        pq->head = pq->tail = newnode;
    } 
    else 
    {
        // 若队列非空，将现有尾节点的下一节点指向新节点
        pq->tail->next = newnode;
        
        // 更新队列尾指针，使之指向新插入的节点
        pq->tail = newnode;
    }
}

        队头出队列 QueuePop

        出队列，即释放队头指针指向的结点并改变队头指针的指向即可。若队列中只有一个结点，那么直接将该结点释放，然后将队头和队尾置空即可。

void QueuePop(Queue* pq) 
{
    // 断言检查队列结构体指针是否有效
    assert(pq);

    // 断言检查队列是否为空，若为空则不能进行出队操作
    assert(!QueueEmpty(pq));

    // 判断队列中剩余元素数量
    if (pq->head->next == NULL) 
    {
        // 如果队列只剩一个元素，则释放该元素，并将头尾指针都设为 NULL
        free(pq->head);
        pq->head = NULL;
        pq->tail = NULL;
    } 
    else 
    {
        // 如果队列中还有多个元素，则释放头节点，然后将头指针指向下一个节点
        QListNode* next = pq->head->next;
        free(pq->head);
        pq->head = next;
    }
}

        获取队列头部元素 QueueFront

        获取队列头部元素，即返回队头指针指向的数据即可。

QDataType QueueFront(Queue* pq) 
{
    // 断言检查队列结构体指针是否有效
    assert(pq);

    // 断言检查队列是否为空，若为空则无法获取队头元素
    assert(!QueueEmpty(pq));

    // 返回队列头部节点（即队首元素）的数据域值
    return pq->head->data;
}

        获取队尾尾部元素

        获取队列尾部元素，即返回队尾指针指向的数据即可。

QDataType QueueBack(Queue* pq) 
{
    // 断言检查队列结构体指针是否有效
    assert(pq);

    // 断言检查队列是否为空，若为空则无法获取队尾元素
    assert(!QueueEmpty(pq));

    // 返回队列尾部节点（即队尾元素）的数据域值
    return pq->tail->data;
}

        检查队列是否为空 QueueEmpty

        检测队列是否为空，即判断队头指针指向的内容是否为空。

bool QueueEmpty(Queue* pq) 
{
    // 断言检查队列结构体指针是否有效
    assert(pq);

    // 判断队列是否为空的条件是：头指针（pq->head）是否为 NULL
    // 如果头指针为 NULL，则队列为空，返回 true
    // 否则，队列非空，返回 false
    return pq->head == NULL;
}

        获取队列中有效元素个数 QueueSize

        队列中有效元素个数，即队列中的结点个数。我们只需遍历队列，统计队列中的结点数并返回即可。

int QueueSize(Queue* pq) 
{
    // 断言检查队列结构体指针是否有效
    assert(pq);

    // 初始化计数器 count 为 0
    int count = 0;

    // 创建一个临时指针 cur，初始化为队列的头节点
    QListNode* cur = pq->head;

    // 遍历队列，直到 cur 为空（即遍历完队列）
    while (cur) 
    {
        // 计数器加一，表示找到了一个有效节点
        count++;

        // 将 cur 指针移向下一个节点
        cur = cur->next;
    }

    // 返回计数器 count 的值，即队列中有效元素的个数
    return count;
}