AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【数据结构】栈和队列（c语言实现）（附源码）

2024-11-07 28
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。

一、栈

1.栈的概念与结构

栈的概念：栈是一种特殊的线性表，它不允许被遍历，并且只能够在固定的一端进行数据的插入或者删除操作。进行插入或删除操作的一端称之为栈顶，另一端称为栈底。由于数据的插入和删除在同一端，所以栈的数据元素遵从“先进后出”的原则。




2.栈的实现

       一般可以使用顺序表或者链表实现栈，在进行插入删除操作时满足先进后出原则即可。由于顺序表的尾插与尾删操作效率较高，接下来我们尝试用顺序表实现它。


2.1 栈的结构定义

栈的结构定义与顺序表完全相同，定义如下：

typedef int STDataType;
 
typedef struct Stack
{
    STDataType* arr;//起始指针
    int capacity;//栈的空间大小
    int top;//有效数据的个数
};

2.2 方法的声明

接下来是栈的一些常用方法：

//初始化
void STInit(ST* ps);
 
//销毁
void STDestroy(ST* ps);
 
//判空
bool STEmpty(ST* ps);
 
//压栈
void STPush(ST* ps, STDataType n);
 
//出栈
void STPop(ST* ps);
 
//取栈顶元素
STDataType STTop(ST* ps);

2.3 方法的实现

2.3.1  初始化

//初始化
void STInit(ST* ps)
{
    assert(ps);//防止传空指针
    ps->arr = NULL;
    ps->capacity = ps->top = 0;
}

2.3.2 销毁

//销毁
void STDestroy(ST* ps)
{
    assert(ps);//防止传空
    if (ps->arr != NULL)//防止多次free
    {
        free(ps->arr);
    }
    ps->arr = NULL;
    ps->capacity = ps->top = 0;
}

2.3.3 判空

       当栈中有效数据个数为0时，栈即为空。

//判空
bool STEmpty(ST* ps)
{
    assert(ps);
    return ps->top == 0;
}

2.3.4 压栈

       进行压栈操作时，我们将结构成员top作为栈顶，在尾部插入数据：

//压栈
void STPush(ST* ps, STDataType n)
{
    assert(ps);
    if (ps->capacity == ps->top)//若空间不够，则增容
    {
        int NewCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        STDataType* tmp = (STDataType*)realloc(ps->arr, NewCapacity * sizeof(STDataType));
        if (tmp == NULL)//内存申请失败，则直接退出程序
        {
            perror("realloc");
            exit(1);
        }
        ps->arr = tmp;//成功则让arr指向申请好的空间
        ps->capacity = NewCapacity;
    }
    ps->arr[ps->top++] = n;//在栈顶插入数据
}

2.3.5 出栈

       为遵循“先进后出”原则，既然在尾部插入数据，那么删除数据时也要在尾部进行：

//出栈
void STPop(ST* ps)
{
    assert(ps);
    assert(!STEmpty(ps));//确保栈不为空
    ps->top--;
}

2.3.6 取栈顶元素

       对于栈这样的数据结构，我们不能进行遍历，但是可以访问到栈顶元素。代码如下：

//取栈顶元素
STDataType STTop(ST* ps)
{
    assert(ps && !STEmpty(ps));
    return ps->arr[ps->top - 1];//栈顶top-1的位置即为栈顶元素
}

2.4 程序全部代码

       关于栈实现的全部代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
 
typedef int STDataType;
 
typedef struct Stack
{
    STDataType* arr;//起始指针
    int capacity;//栈的空间大小
    int top;//有效数据的个数
}ST;
 
//初始化
void STInit(ST* ps);
 
//销毁
void STDestroy(ST* ps);
 
//判空
bool STEmpty(ST* ps);
 
//压栈
void STPush(ST* ps, STDataType n);
 
//出栈
void STPop(ST* ps);
 
//取栈顶元素
STDataType STTop(ST* ps);
 
//初始化
void STInit(ST* ps)
{
    assert(ps);//防止传空指针
    ps->arr = NULL;
    ps->capacity = ps->top = 0;
}
 
//销毁
void STDestroy(ST* ps)
{
    assert(ps);//防止传空
    if (ps->arr != NULL)//防止多次free
    {
        free(ps->arr);
    }
    ps->arr = NULL;
    ps->capacity = ps->top = 0;
}
 
//判空
bool STEmpty(ST* ps)
{
    assert(ps);
    return ps->top == 0;
}
 
//压栈
void STPush(ST* ps, STDataType n)
{
    assert(ps);
    if (ps->capacity == ps->top)//若空间不够，则增容
    {
        int NewCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        STDataType* tmp = (STDataType*)realloc(ps->arr, NewCapacity * sizeof(STDataType));
        if (tmp == NULL)//内存申请失败，则直接退出程序
        {
            perror("realloc");
            exit(1);
        }
        ps->arr = tmp;//成功则让arr指向申请好的空间
        ps->capacity = NewCapacity;
    }
    ps->arr[ps->top++] = n;//在栈顶插入数据
}
 
//出栈
void STPop(ST* ps)
{
    assert(ps);
    assert(!STEmpty(ps));//确保栈不为空
    ps->top--;
}
 
//取栈顶元素
STDataType STTop(ST* ps)
{
    assert(ps && !STEmpty(ps));
    return ps->arr[ps->top - 1];//栈顶top-1的位置即为栈顶元素
}

二、队列

       学习了栈的特性和方法实现之后，我们再来了解一个新的数据结构：队列。


1.队列的概念与结构

队列也是一种特殊的线性表，与栈相反，它只能在一端插入数据，另一端删除数据。插入数据的端叫做队尾；删除数据的一端叫做队头。因此，队列的数据元素遵从“先进先出”的原则。



2.队列的实现

       与栈相同，队列的实现也可以用顺序表或链表。由于顺序表两端的插入和删除操作要涉及到数据的全体移动，效率较低，我们就尝试用链表来实现队列。


2.1 队列的结构定义

       队列的结构定义如下：

typedef int QDataType;
 
//定义队列的节点
typedef struct QueueNode
{
    QDataType data;//数据域
    struct QueueNode* next;//指针域
}QNode;
 
//定义队列
typedef struct Queue
{
    QNode* phead;//队头指针
    QNode* ptail;//队尾指针
    int size;//队列元素个数
}Queue;

2.2 方法声明

//初始化
void QInit(Queue* pq);
 
//判空
bool QEmpty(Queue* pq);
 
//入队列
void QPush(Queue* pq, QDataType n);
 
//出队列
void QPop(Queue* pq);
 
//取队头数据
QDataType QFront(Queue* pq);
 
//取队尾数据
QDataType QBack(Queue* pq);
 
//销毁
void QDestroy(Queue* pq);

2.3 方法实现

2.3.1 初始化

//初始化
void QInit(Queue* pq)
{
    assert(pq);
    pq->phead = pq->ptail = NULL;//将两指针都制为空
    pq->size = 0;//数据个数为0
}

2.3.2 判空

       当队头指针和队尾指针都指向空时，说明队列为空。

//判空
bool QEmpty(Queue* pq)
{
    assert(pq);
    return pq->phead == NULL && pq->ptail == NULL;
}

2.3.3 入队列

       入队列的操作与单链表尾插十分相似，由于有队尾指针，就无需遍历链表。注意其中的一些细节处理。

//入队列
void QPush(Queue* pq, QDataType n)
{
    assert(pq);
    QNode* newnode = (QNode*)malloc(sizeof(QNode));//创建新节点
    if (newnode == NULL)//创建失败退出程序
    {
        perror("malloc");
        exit(1);
    }
    newnode->data = n;
    newnode->next = NULL;
    if (QEmpty(pq))//队列为空的情况
    {
        pq->phead = pq->ptail = newnode;//队头与队尾都指向新节点
    }
    else//其他情况,尾插操作
    {
        pq->ptail->next = newnode;//将新节点连接在队尾之后
        pq->ptail = newnode;//队尾指向新节点
    }
    pq->size++;//空间大小+1
}

2.3.4 出队列

       出队列时，注意是在队头删除数据。

//出队列
void QPop(Queue* pq)
{
    assert(pq && !QEmpty(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;//让队头指向下一个节点
    }
    pq->size--;//空间大小-1
}

2.3.5 取队头数据和队尾数据

//取队头数据
QDataType QFront(Queue* pq)
{
    assert(pq && !QEmpty(pq));
    return pq->phead->data;
}
 
//取队尾数据
QDataType QBack(Queue* pq)
{
    assert(pq && !QEmpty(pq));
    return pq->ptail->data;
}

2.3.6 销毁队列

//销毁
void QDestroy(Queue* pq)
{
    assert(pq);
    QNode* cur = pq->phead;
    while (cur != NULL)//遍历删除
    {
        QNode* next = cur->next;//记录后继节点
        free(cur);
        cur = next;//cur指针指向记录的节点
    }
    pq->phead = pq->ptail = NULL;
    pq->size = 0;
}

2.4 程序全部代码

       队列实现的全部代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
 
typedef int QDataType;
 
//定义队列的节点
typedef struct QueueNode
{
    QDataType data;//数据域
    struct QueueNode* next;//指针域
}QNode;
 
//定义队列
typedef struct Queue
{
    QNode* phead;//队头指针
    QNode* ptail;//队尾指针
    int size;//队列元素个数
}Queue;
 
//初始化
void QInit(Queue* pq);
 
//判空
bool QEmpty(Queue* pq);
 
//入队列
void QPush(Queue* pq, QDataType n);
 
//出队列
void QPop(Queue* pq);
 
//取队头数据
QDataType QFront(Queue* pq);
 
//取队尾数据
QDataType QBack(Queue* pq);
 
//销毁
void QDestroy(Queue* pq);
 
//初始化
void QInit(Queue* pq)
{
    assert(pq);
    pq->phead = pq->ptail = NULL;//将两指针都制为空
    pq->size = 0;//数据个数为0
}
 
//判空
bool QEmpty(Queue* pq)
{
    assert(pq);
    return pq->phead == NULL && pq->ptail == NULL;
}
 
//入队列
void QPush(Queue* pq, QDataType n)
{
    assert(pq);
    QNode* newnode = (QNode*)malloc(sizeof(QNode));//创建新节点
    if (newnode == NULL)//创建失败退出程序
    {
        perror("malloc");
        exit(1);
    }
    newnode->data = n;
    newnode->next = NULL;
    if (QEmpty(pq))//队列为空的情况
    {
        pq->phead = pq->ptail = newnode;//队头与队尾都指向新节点
    }
    else//其他情况,尾插操作
    {
        pq->ptail->next = newnode;//将新节点连接在队尾之后
        pq->ptail = newnode;//队尾指向新节点
    }
    pq->size++;//空间大小+1
}
 
//出队列
void QPop(Queue* pq)
{
    assert(pq && !QEmpty(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;//让队头指向下一个节点
    }
    pq->size--;//空间大小-1
}
 
//取队头数据
QDataType QFront(Queue* pq)
{
    assert(pq && !QEmpty(pq));
    return pq->phead->data;
}
 
//取队尾数据
QDataType QBack(Queue* pq)
{
    assert(pq && !QEmpty(pq));
    return pq->ptail->data;
}
 
//销毁
void QDestroy(Queue* pq)
{
    assert(pq);
    QNode* cur = pq->phead;
    while (cur != NULL)//遍历删除
    {
        QNode* next = cur->next;//记录后继节点
        free(cur);
        cur = next;//cur指针指向记录的节点
    }
    pq->phead = pq->ptail = NULL;
    pq->size = 0;
}

总结

       今天我们学习了栈和队列这两种数据结构：栈只能从同一端进行插入、删除操作，遵从“先进后出”原则；而队列只能从一端插入、另一端删除，遵从“先进先出”原则。栈和队列在一些场景的实用性很高，例如二叉树的层序遍历、快速排序的非递归实现等。如果你觉得博主讲的还不错，就请留下一个小小的赞在走哦，感谢大家的支持❤❤❤

文章标签：
C语言
关键词：
C语言源码
数据结构队列C语言
数据结构队列源码
数据结构源码
栈队列C语言
ephemerals__
目录
相关文章
ephemerals__
|
3天前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
23 4
肾透侧视攻城狮
|
4天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总（10）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
11 1
ephemerals__
|
3天前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
13 0
這～悸ベ雨落憂殇
|
存储 缓存 C语言
数据结构——双链表（C语言）
数据结构——双链表（C语言）
這～悸ベ雨落憂殇
45 0
7fa6b5ui5pmtk
|
5月前
|
存储
数据结构——双向链表（C语言版）
数据结构——双向链表（C语言版）
7fa6b5ui5pmtk
30 2
7fa6b5ui5pmtk
|
5月前
|
算法 C语言
数据结构——单向链表（C语言版）
数据结构——单向链表（C语言版）
7fa6b5ui5pmtk
45 2
Darknesscor
|
测试技术 C语言
数据结构单链表的实现（C语言）
数据结构单链表的实现（C语言）
Darknesscor
26 0
ForcibleBugMaker
|
6月前
|
存储 缓存 程序员
初阶数据结构之---顺序表和链表（C语言）
初阶数据结构之---顺序表和链表（C语言）
ForcibleBugMaker
85 1
GOTXX
|
6月前
|
存储 C语言
数据结构之单链表详解（C语言手撕）
数据结构之单链表详解（C语言手撕）
GOTXX
90 1
C-调战士
|
算法
【数据结构】带头双向循环链表---C语言版（单链表我们分手吧，不要再找我玩了！！！）（二）
【数据结构】带头双向循环链表---C语言版（单链表我们分手吧，不要再找我玩了！！！）（二）
C-调战士
72 0

热门文章

最新文章

  • 1
    数据结构~在页面上渲染树型结构
  • 2
    我花了一夜用数据结构给女朋友写个H5走迷宫游戏
  • 3
    基于OHCI的USB主机 —— OHCI（自定义数据结构）
  • 4
    数据结构学习笔记【持续更新】
  • 5
    学数据结构，只需要基本的编程体验
  • 6
    算法导论第十四章 数据结构的扩张
  • 7
    【数据结构】二叉树链式结构的实现（三）
  • 8
    数据结构之堆的应用
  • 9
    大数据开发基础的数据结构和算法的数据结构的图
  • 10
    【数据结构与算法】—— * 深度优先搜索入门 *
  • 1
    C语言之详细讲解文件操作（抓住文件操作的奥秘）
    44
  • 2
    C语言结构体—自定义类型—struct
    45
  • 3
    C语言—内存函数的实现和模拟实现（内存函数的丝绸之路）
    43
  • 4
    C语言—字符函数与字符串函数（字符问题变简单的关键之技）
    55
  • 5
    C语言之九九乘法表||素数||最小公倍数
    59
  • 6
    C语言详解指针（指针海洋的探索，将传值与传址刻在心里）
    39
  • 7
    C语言——函数递归
    34
  • 8
    C语言扫雷代码（蹦蹦炸弹）（下）
    35
  • 9
    关于我在C语言中玩扫雷（上）
    31
  • 10
    C语言—函数（大化小方式的心脏）
    34

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法
  • 你的第一门C语言课
  • C语言学习教程
  • Go语言核心编程 - 基础语法、数组、切片、Map
  • 5天玩转Java面向对象编程
  • Java面向对象编程

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    阿里云无影云电脑免费试用，最长可试用3个月