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

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

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

一、栈

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__
目录
相关文章
那年春天
|
16天前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
22 1
龙大吉
|
3天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
22 5
德国都芳最好
|
18天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构，在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈，可以有效地解决许多与数据存储和操作相关的问题。
德国都芳最好
67 21
html的七十二变
|
21天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境，每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用，每当调用一个函数，就会在栈中添加一个新的执行上下文。
html的七十二变
30 2
dufadayang
|
23天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息？
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息，操作系统能够实现用户模式和内核模式之间的无缝切换，为用户程序提供稳定、可靠的系统服务。
dufadayang
47 4
java冯坚持
|
2月前
|
算法 程序员 索引
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈，并展示了如何利用栈和中缀表达式实现一个综合计算器。
java冯坚持
33 1
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
肾透侧视攻城狮
|
28天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总（10）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
21 1
禁默
|
2月前
初步认识栈和队列
初步认识栈和队列
禁默
61 10
星霜旅人
|
2月前
数据结构（栈与列队）
数据结构（栈与列队）
星霜旅人
20 1
java冯坚持
|
2月前
|
算法
数据结构与算法二：栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式
这篇文章讲解了栈的基本概念及其应用，并详细介绍了中缀表达式转换为后缀表达式的算法和实现步骤。
java冯坚持
51 3

热门文章

最新文章

  • 1
    《C语言及程序设计》实践参考——改造链表
  • 2
    C语言四舍五入计算方法（包含各种精度）
  • 3
    C语言中用于计算数组长度的函数 “strlen（） ”。
  • 4
    C语言标准库（常用函数）详解（含示例）数学公式：math.h
  • 5
    《C语言程序设计进阶教程》一第3章 预防、检测及消除bug
  • 6
    C语言预处理之二-----宏定义那点事儿
  • 7
    《C语言及程序设计》实践项目——数据的输入
  • 8
    C语言库函数大全及应用实例十
  • 9
    四则运算表达式求值程序(C语言版)
  • 10
    C语言及程序设计提高例程-26 实现线性表基本操作的函数
  • 1
    【Python进阶（七）】——Series数据结构
    167
  • 2
    Redis数据结构精讲：选择与应用实战指南
    1326
  • 3
    深入浅出数据结构之布隆过滤器
    65
  • 4
    数据结构/C++：位图 & 布隆过滤器
    44
  • 5
    数据结构/C++：哈希表
    75
  • 6
    数据结构/C++：红黑树
    42
  • 7
    数据结构/C++：AVL树
    40
  • 8
    栈的基本应用
    54
  • 9
    栈与队列理解
    40
  • 10
    数据结构/C++：二叉搜索树
    43

    • 相关课程

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

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 图解算法小抄
    • 下一篇
    使用阿里云接口（API）进行身份证实名认证