当前位置： 首页 > article >正文

C 语言数据结构（三）：栈和队列

article 2025/3/13 4:52:07

目录

1. 栈

1.1 栈的概念及结构

1.2 栈的实现

2. 队列

2.1 队列的概念及结构

2.2 队列的实现

💬 ：如果你在阅读过程中有任何疑问或想要进一步探讨的内容，欢迎在评论区畅所欲言！我们一起学习、共同成长~！

👍 ：如果你觉得这篇文章还不错，不妨顺手点个赞、加入收藏，并分享给更多的朋友噢~！

1. 栈

1.1 栈的概念及结构

栈是一种特殊的线性表，它只允许在固定的一端进行插入和删除元素操作。

允许进行插入和删除操作的一端称为栈顶；另一端不允许进行插入和删除操作，称为栈底。

栈中的数据元素遵守后进先出（LIFO，Last In First Out）的原则——最后进栈的数据元素会最先被取出。就像往一个桶里放东西，最后放进去的东西会在最上面，取的时候最先被取出。

  • 压栈：栈的插入操作叫做进栈 / 压栈 / 入栈。
  • 出栈：栈的删除操作叫做出栈。

1.2 栈的实现

栈的实现一般可使用数组或链表，相对而言数组的结构实现更优。

  • 若使用数组，一般来说数组末端作栈顶。在栈顶插入数据，只需简单地移动索引，且数组元素在内存中连续存储，访问速度快。
  • 若使用链表，每次插入数据要创建新节点并修改指针，涉及内存的动态分配和指针操作。
// 定长的静态栈的结构在实际中一般不实用，下面实现支持动态增长的栈

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// 定义栈中存储的数据类型
typedef int STDataType;

// 定义栈的结构体
typedef struct Stack
{
    STDataType* a;  // 指向动态分配的数组，用于存储栈中的元素
    int top;        // 栈顶指针，指示栈顶元素的位置
    int capacity;   // 栈的当前容量
} Stack;

// 初始化栈
void StackInit(Stack* ps)
{
    // 确保传入的栈指针不为空
    assert(ps);
    // 初始分配一定的容量，这里假设初始容量为 4
    ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
    if (ps->a == NULL)
    {
        perror("malloc fail");
        return;
    }
    // 初始化栈顶指针为 0，表示栈为空
    ps->top = 0;
    
    ps->capacity = 4;
}

// 入栈操作
void StackPush(Stack* ps, STDataType data)
{
    assert(ps);

    // 检查栈是否已满，如果已满则扩容
    if (ps->top == ps->capacity)
    {
        STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
        if (tmp == NULL)
        {
            perror("realloc fail");
            return;
        }
        // 更新栈的数组指针
        ps->a = tmp;
        
        ps->capacity *= 2;
    }
    // 将数据放入栈顶位置
    ps->a[ps->top] = data;
    
    ps->top++;   // 表示添加栈顶元素
}

// 出栈操作
void StackPop(Stack* ps)
{
    assert(ps);
    // 确保栈不为空才能进行出栈操作
    assert(ps->top > 0);
    
    ps->top--;   // 表示移除栈顶元素
}

// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
    assert(ps);
    // 确保栈不为空才能获取栈顶元素
    assert(ps->top > 0);
    // 返回栈顶元素
    return ps->a[ps->top - 1];
}

// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
    assert(ps);
    // 栈顶指针的值即为栈中有效元素的个数
    return ps->top;
}

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回 0
int StackEmpty(Stack* ps)
{
    assert(ps);

    // 当栈顶指针为 0 时，栈为空
    return ps->top == 0;
}

// 销毁栈
void StackDestroy(Stack* ps)
{
    assert(ps);

    // 释放动态分配的数组内存
    free(ps->a);
    // 将数组指针置为 NULL，避免野指针
    ps->a = NULL;
    
    ps->top = 0;
    
    ps->capacity = 0;
}

int main()
{
    Stack st;

    // 初始化栈
    StackInit(&st);

    // 入栈操作
    StackPush(&st, 1);
    StackPush(&st, 2);
    StackPush(&st, 3);
    StackPush(&st, 4);
    
    printf("Top element: %d\n", StackTop(&st));
    // 打印栈中元素个数
    printf("Stack size: %d\n", StackSize(&st));

    // 出栈操作
    StackPop(&st);
    
    printf("Top element after pop: %d\n", StackTop(&st));
    
    printf("Stack size after pop: %d\n", StackSize(&st));

    // 检测栈是否为空
    printf("Is stack empty? %s\n", StackEmpty(&st) ? "Yes" : "No");

    // 销毁栈
    StackDestroy(&st);

    return 0;
}

  • 时间复杂度：（1）初始化、出栈、获取栈顶元素、获取栈中元素个数和检测栈是否为空的操作时间复杂度均为 O(1)。（2）入栈操作在不需扩容时时间复杂度为 O(1)，扩容时平均时间复杂度也接近 O(1)。（3）销毁栈操作的时间复杂度为 O(1)。
  • 空间复杂度：主要取决于栈中元素的个数，空间复杂度为 O(n)，n 是栈中元素的个数。

2. 队列

2.1 队列的概念及结构

队列是只允许在一端插入数据，在另一端删除数据的特殊线性表。

队列有先进先出（FIFO，First In First Out）的特性——先进入队列的元素先出队列。好比排队收银，排在队伍前面的顾客先结账离开队伍，而后到的顾客要在后面依次等待。

  • 入队列：插入数据操作。进行插入操作的一端称为队尾。
  • 出队列：删除数据操作。进行删除操作的一端称为队头。

2.2 队列的实现

队列的实现可使用数组或链表，相对而言使用链表的结构实现更优。

  • 若使用数组，出队列即在数组头部删除元素，而由于数组元素在内存中连续存储，删除头部元素后，要将后面所有元素依次向前移动一位来填补空缺，此过程涉及大量的数据移动操作，效率较低；
  • 若使用链表，出队列删除头部节点时，只需修改头指针指向原头节点的下一个节点，然后释放原头节点的内存即可，效率更高。
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// 定义队列存储的数据类型
typedef int QDataType;

// 定义队列节点的结构体，每个节点包含两部分
// 1. pNext：指向下一个节点的指针，用于连接队列中的各个节点
// 2. data：存储队列中的数据
typedef struct QListNode
{
    struct QListNode* pNext;
    QDataType data;
} QNode;

// 定义队列的结构体，包含两个指针
// 1. front：指向队列的头部节点
// 2. rear：指向队列的尾部节点 
typedef struct Queue
{
    QNode* front;
    QNode* rear;
} Queue;

// 初始化队列 
void QueueInit(Queue* q) 
{
    // 断言队列指针不为空，避免传入空指针导致程序崩溃
    assert(q);

    // 初始化队头和队尾指针为 NULL，表示队列为空
    q->front = NULL;
    q->rear = NULL;
}

// 队尾入队列 
void QueuePush(Queue* q, QDataType data) 
{
    assert(q);
    // 为新节点分配内存
    QNode* newNode = (QNode*)malloc(sizeof(QNode));
    if (newNode == NULL) 
    {
        perror("malloc fail");
        return;
    }
    // 给新节点的“数据域”赋值
    newNode->data = data;
    
    // 新节点的下一个节点指针置为 NULL，因为新节点将成为尾节点，其后无其他节点
    newNode->pNext = NULL;

    if (q->rear == NULL) 
    {
        // 如果队列为空，新节点既是队头也是队尾
        q->front = newNode;
        q->rear = newNode;
    }
    else 
    {
        // 新节点连接到队尾
        q->rear->pNext = newNode;
        // 更新队尾指针指向新节点
        q->rear = newNode;
    }
}

// 队头出队列 
void QueuePop(Queue* q) 
{
    assert(q);

    // 断言队列不为空
    assert(!QueueEmpty(q));

    // 保存队头节点的下一个节点的指针
    QNode* next = q->front->pNext;
    free(q->front);
    q->front = next;

    if (q->front == NULL) 
    {
        // 如果队头为空，说明队列已空，将队尾指针也置为 NULL
        q->rear = NULL;
    }
}

// 获取队列头部元素 
QDataType QueueFront(Queue* q) 
{
    assert(q);
    assert(!QueueEmpty(q));

    // 返回队头节点的数据
    return q->front->data;
}

// 获取队列队尾元素 
QDataType QueueBack(Queue* q) 
{
    assert(q);
    assert(!QueueEmpty(q));
    return q->rear->data;
}

// 获取队列中有效元素个数 
int QueueSize(Queue* q) 
{
    assert(q);
    int size = 0;
    QNode* cur = q->front;
    // 遍历队列，统计节点个数
    while (cur) 
    {
        size++;
        cur = cur->pNext;
    }
    return size;
}

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q) 
{
    assert(q);
    // 队头指针为空则队列为空
    return q->front == NULL;
}

// 销毁队列 
void QueueDestroy(Queue* q) 
{
    assert(q);
    QNode* cur = q->front;

    // 遍历队列，释放每个节点的内存
    while (cur) 
    {
        QNode* next = cur->pNext;
        free(cur);
        cur = next;
    }
    
    q->front = NULL;
    q->rear = NULL;
}

int main() 
{
    Queue q;   // 声明一个 Queue 类型的变量，为队列分配了内存空间
    QueueInit(&q);   // 初始化队列

    // 入队操作
    QueuePush(&q, 1);
    QueuePush(&q, 2);
    QueuePush(&q, 3);

    // 输出队头/尾元素
    printf("Queue front: %d\n", QueueFront(&q));
    printf("Queue back: %d\n", QueueBack(&q));

    // 输出队列元素个数
    printf("Queue size: %d\n", QueueSize(&q));

    // 出队操作
    QueuePop(&q);
    printf("Queue front after pop: %d\n", QueueFront(&q));

    // 销毁队列
    QueueDestroy(&q);

    return 0;
}

  • 时间复杂度：QueueSize 和 QueueDestroy 函数的时间复杂度为 O(n)，其余函数的时间复杂度均为 O(1)。
  • 空间复杂度：所有函数的空间复杂度均为 O(1)。整个队列的空间复杂度为 O(n)，其中 n 是队列中元素的数量。

在数据结构中，一个节点通常由多个部分组成，其中用于存储实际数据的部分称为数据域。而用于存储指向下一个节点地址的部分称为指针域。


http://www.kler.cn/a/582295.html

相关文章：

  • 【3D视觉学习笔记1】针孔相机模型与坐标系变换
  • Linux进程管理15 - CFS调度器2 - 数据结构关系
  • c#25/3/11 周二
  • WHAT - 前端性能监控和错误追踪（Sentry 篇）
  • 【A2DP】蓝牙A2DP协议剖析：从架构到规范
  • 2025-03-11 学习记录--C/C++-PTA 习题11-5 指定位置输出字符串
  • 详细介绍c++中的文件处理
  • nginx 代理 redis
  • git子仓库管理的两种方式
  • 从零开发Chrome广告拦截插件：开发、打包到发布全攻略
  • C++ 标准库：string 类、vector/List 容器与文件操作深度剖析
  • Android JNI二维码生成与优化方案
  • C语言_数据结构总结3:带头结点的单链表
  • deepseek R1提供的3d迷宫设计方案
  • 爬虫中一些有用的用法
  • PHP框架加载不上.env文件中的变量
  • Mysql 的 Query Cache为什么被废弃
  • Linux losetup循环设备
  • 阿里云ECS防勒索数据安全新选择：安当RDM防勒索组件——低成本、高可靠的主动防御方案
  • 网络防火墙是什么有什么用_网络防火墙：守护信息安全的重要屏障