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

2024-11-07 530 发布于重庆

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。

一、栈

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语言实现）（附源码）

一、栈

1.栈的概念与结构

2.栈的实现

2.1 栈的结构定义

2.2 方法的声明

2.3 方法的实现

2.3.1 初始化

2.3.2 销毁

2.3.3 判空

2.3.4 压栈

2.3.5 出栈

2.3.6 取栈顶元素

2.4 程序全部代码

二、队列

1.队列的概念与结构

2.队列的实现

2.1 队列的结构定义

2.2 方法声明

2.3 方法实现

2.3.1 初始化

2.3.2 判空

2.3.3 入队列

2.3.4 出队列

2.3.5 取队头数据和队尾数据

2.3.6 销毁队列

2.4 程序全部代码

总结

热门文章

最新文章

相关课程

相关电子书

相关实验场景

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

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

一、栈

1.栈的概念与结构

2.栈的实现

2.1 栈的结构定义

2.2 方法的声明

2.3 方法的实现

2.3.1 初始化

2.3.2 销毁

2.3.3 判空

2.3.4 压栈

2.3.5 出栈

2.3.6 取栈顶元素

2.4 程序全部代码

二、队列

1.队列的概念与结构

2.队列的实现

2.1 队列的结构定义

2.2 方法声明

2.3 方法实现

2.3.1 初始化

2.3.2 判空

2.3.3 入队列

2.3.4 出队列

2.3.5 取队头数据和队尾数据

2.3.6 销毁队列

2.4 程序全部代码

总结

热门文章

最新文章

相关课程

相关电子书

相关实验场景