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

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

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

一、栈

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语言
数据结构栈队列
数据结构栈
数据结构队列
ephemerals__
目录
相关文章
hahaha无
|
1月前
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因，涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问，修改了变量`i`的值，导致`for`循环条件始终为真，形成死循环。原因是VS2022栈区从低地址到高地址分配内存，`arr`数组与`i`相邻，`arr[15]`恰好覆盖`i`的地址。而在VS2019中，栈区先分配高地址再分配低地址，因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致，需避免数组越界以确保代码健壮性。
hahaha无
21 0
栈区的非法访问导致的死循环(x64)
游客beejssedmb2sq
|
1月前
232.用栈实现队列，225. 用队列实现栈
在232题中，通过两个栈（`stIn`和`stOut`）模拟队列的先入先出（FIFO）行为。`push`操作将元素压入`stIn`，`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列（`que`）模拟栈的后入先出（LIFO）特性。通过多次调整队列头部元素的位置，确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素，`empty`判断队列是否为空。 两题均仅使用基础数据结构操作，展示了栈与队列之间的转换逻辑。
游客beejssedmb2sq
33 0
蓝易云
|
5月前
|
算法 调度 C++
STL——栈和队列和优先队列
通过以上对栈、队列和优先队列的详细解释和示例，希望能帮助读者更好地理解和应用这些重要的数据结构。
蓝易云
77 11
羑悻的小杀马特
|
5月前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法：用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下： 1. **用两个队列实现栈**： - 插入元素时，选择非空队列进行插入。 - 移除栈顶元素时，将非空队列中的元素依次转移到另一个队列，直到只剩下一个元素，然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**： - 插入元素时，选择非空栈进行插入。 - 移除队首元素时，将非空栈中的元素依次转移到另一个栈，再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
羑悻的小杀马特
80 14
羑悻的小杀马特
|
5月前
|
定位技术 C语言
c语言及数据结构实现简单贪吃蛇小游戏
c语言及数据结构实现简单贪吃蛇小游戏
羑悻的小杀马特
130 13
羑悻的小杀马特
|
6月前
|
搜索推荐 C语言
数据结构（C语言）之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法，通过递归将数组不断分割为子数组，直到每个子数组仅剩一个元素，再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中，每次分割区间为[left, mid]和[mid+1, right]，确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值（初始为1），先对单个元素排序，再逐步扩大到更大的区间进行合并，直至整个数组有序。归并排序的时间复杂度为O(n*logn)，空间复杂度为O(n)，且具有稳定性，适用于普通排序及大文件排序场景。
羑悻的小杀马特
96 13
pqo7bvdsfj67q
|
C语言
纯c语言迷宫源码
纯c语言迷宫源码
pqo7bvdsfj67q
173 0
RossyYan
|
6月前
|
存储 算法 C语言
【C语言程序设计——函数】素数判定（头歌实践教学平台习题）【合集】
本内容介绍了编写一个判断素数的子函数的任务，涵盖循环控制与跳转语句、算术运算符（%）、以及素数的概念。任务要求在主函数中输入整数并输出是否为素数的信息。相关知识包括 `for` 和 `while` 循环、`break` 和 `continue` 语句、取余运算符 `%` 的使用及素数定义、分布规律和应用场景。编程要求根据提示补充代码，测试说明提供了输入输出示例，最后给出通关代码和测试结果。 任务核心：编写判断素数的子函数并在主函数中调用，涉及循环结构和条件判断。
RossyYan
305 23
程序员Feri
|
5月前
|
人工智能 Java 程序员
一文彻底搞清楚C语言的函数
本文介绍C语言函数：函数是程序模块化的工具，由函数头和函数体组成，涵盖定义、调用、参数传递及声明等内容。值传递确保实参不受影响，函数声明增强代码可读性。君志所向，一往无前！
程序员Feri
97 1
一文彻底搞清楚C语言的函数
RossyYan
|
6月前
|
算法 C语言
【C语言程序设计——函数】利用函数求解最大公约数和最小公倍数（头歌实践教学平台习题）【合集】
本文档介绍了如何编写两个子函数，分别求任意两个整数的最大公约数和最小公倍数。内容涵盖循环控制与跳转语句的使用、最大公约数的求法（包括辗转相除法和更相减损术），以及基于最大公约数求最小公倍数的方法。通过示例代码和测试说明，帮助读者理解和实现相关算法。最终提供了完整的通关代码及测试结果，确保编程任务的成功完成。
RossyYan
263 15
【C语言程序设计——函数】利用函数求解最大公约数和最小公倍数（头歌实践教学平台习题）【合集】