栈和队列-介绍与实现（超级！！！详解-C语言）

目录

栈

栈的介绍

        栈的概念

        栈的结构

栈的实现

        初始化栈 StackInit

        销毁栈 StackDestroy

        入栈 StackPush

        出栈 StackPop

        获取栈顶元素 StackTop

        检查栈是否为空 StackEmpty

        获取栈中有效元素个数 StackSize

队列

队列的介绍

        队列的概念

        队列的结构

        队列的应用

队列的实现

        初始化队列 QueueInit

        销毁队列 QueueDestroy

        队尾入队列 QueuePush

        队头出队列 QueuePop

        获取队列头部元素 QueueFront

        获取队尾尾部元素

        检查队列是否为空 QueueEmpty

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

栈

栈的介绍

        栈的概念

        栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出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;
}