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

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

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

一、栈

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__
|
25天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
63 16
ephemerals__
|
21天前
|
搜索推荐 算法 C语言
【排序算法】八大排序（上）（c语言实现）（附源码）
本文介绍了四种常见的排序算法：冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据，详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序，选择排序通过选择最小元素进行交换，插入排序通过逐步插入元素到已排序部分，而希尔排序则是插入排序的改进版，通过预排序使数据更接近有序，从而提高效率。文章最后总结了这四种算法的空间和时间复杂度，以及它们的稳定性。
ephemerals__
65 8
ephemerals__
|
21天前
|
搜索推荐 算法 C语言
【排序算法】八大排序（下）（c语言实现）（附源码）
本文继续学习并实现了八大排序算法中的后四种：堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现，并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序，快速排序通过递归和多种划分方法实现高效排序，归并排序通过分治法将问题分解后再合并，计数排序则通过统计每个元素的出现次数实现非比较排序。最后，文章还对比了这些排序算法在处理一百万个整形数据时的运行时间，帮助读者了解不同算法的优劣。
ephemerals__
59 7
疯狂的猿
|
19天前
|
C语言 Windows
C语言课设项目之2048游戏源码
C语言课设项目之2048游戏源码，可作为课程设计项目参考，代码有详细的注释，另外编译可运行文件也已经打包，windows电脑双击即可运行效果
疯狂的猿
30 1
ephemerals__
|
25天前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
82 8
白子寰
|
2月前
|
C语言 C++
C语言 之 内存函数
C语言 之 内存函数
白子寰
36 3
华章计算机
|
机器学习/深度学习 算法
《数据结构与算法 C语言版》—— 3.2栈的应用举例
华章计算机
1905 0
Skyund
|
18天前
|
C语言
c语言调用的函数的声明
被调用的函数的声明： 一个函数调用另一个函数需具备的条件: 首先被调用的函数必须是已经存在的函数，即头文件中存在或已经定义过； 如果使用库函数，一般应该在本文件开头用#include命令将调用有关库函数时在所需要用到的信息“包含”到本文件中。.h文件是头文件所用的后缀。 如果使用用户自己定义的函数，而且该函数与使用它的函数在同一个文件中，一般还应该在主调函数中对被调用的函数做声明。 如果被调用的函数定义出现在主调函数之前可以不必声明。 如果已在所有函数定义之前，在函数的外部已做了函数声明，则在各个主调函数中不必多所调用的函数在做声明
Skyund
31 6
LuckiBit
|
1天前
|
存储 缓存 算法
【C语言】内存管理函数详细讲解
在C语言编程中，内存管理是至关重要的。动态内存分配函数允许程序在运行时请求和释放内存，这对于处理不确定大小的数据结构至关重要。以下是C语言内存管理函数的详细讲解，包括每个函数的功能、标准格式、示例代码、代码解释及其输出。
LuckiBit
19 6
ephemerals__
|
2月前
|
存储 缓存 C语言
【c语言】简单的算术操作符、输入输出函数
本文介绍了C语言中的算术操作符、赋值操作符、单目操作符以及输入输出函数 `printf` 和 `scanf` 的基本用法。算术操作符包括加、减、乘、除和求余，其中除法和求余运算有特殊规则。赋值操作符用于给变量赋值，并支持复合赋值。单目操作符包括自增自减、正负号和强制类型转换。输入输出函数 `printf` 和 `scanf` 用于格式化输入和输出，支持多种占位符和格式控制。通过示例代码详细解释了这些操作符和函数的使用方法。
ephemerals__
43 10

热门文章

最新文章

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

    • 相关课程

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

    • 相关电子书

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