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

【数据结构】栈和队列

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

​

1. 栈

1.1 栈的概念及结构

栈（stack），又名堆栈。一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守先进后出的原则。

入栈：栈的插入操作叫做入栈/进栈/压栈，入数据在栈顶。（把新元素放在栈顶元素的上面，使之成为新的栈顶元素）。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。（把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素）。
image.png
image.png
​​image.png

1.2 栈的定义

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。因为静态顺序表不实用，所以我们使用动态顺序表实现栈。

//支持动态增长的栈
typedef int STDataType;
#define INIT_CAPACITY 4
typedef struct Stack
{
   
    STDataType* a;  //指向动态开辟的数组
    int top;  //栈顶
    int capacity;  //容量
}ST;

使用结构体创建一个支持动态增长的栈（用动态顺序表实现）。

用STDataType替换int，方便对不同类型的数据进行修改。

用ST替换struct Stack，方便简洁。

用宏定义INIT_CAPACITY将栈的初始容量设置为4。

1.3 栈的接口实现

栈的所有接口函数一览：

//初始化栈
void STInit(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//获取栈顶元素
STDataType STTop(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);
//检测栈是否为空
bool STEmpty(ST* ps);
//销毁栈
void STDestroy(ST* ps);

这些接口函数主要实现了支持动态动态增长的栈的基本功能，接下来我们一一实现这些函数！

1.3.1 初始化栈

我们一开始将指针a置空，让栈顶top为0，栈的容量capacity也为0。这里要注意assert()断言，保证ps的合理性。

//初始化栈
void STInit(ST* ps)
{
   
    assert(ps);
    ps->a = NULL;
    ps->top = 0;
    ps->capacity = 0;
}

1.3.2 入栈

和动态顺序表的操作类似，入栈的时候，我们也需要考虑是否需要扩容。

这里当栈满了（ps->top==ps->capacity）的时候，就需要扩容。

我们定义了一个变量newCapacity来存储扩容后栈的新容量。我们将新容量扩充为原来的2倍，但是因为有可能原容量为0，所以我们这里使用了三目运算符。如果原容量为0，我们就将newCapacity设置为INIT_CAPACITY。否则，我们就让newCapacity是原容量的2倍。

之后使用realloc（）函数进行扩容，我们用结构体指针tmp存取栈扩容后的地址。

这里我们扩展一个知识点：
image.png

我们可以知道，如果一开始如果传的指针a为空，realloc()函数的作用和malloc()函数作用相同。

扩容完后就是让指针a指向tmp（ps->a=tmp），

让容量变为newCapacity（ps->capacity=newCapacity）。

入栈就是添加新元素在栈顶（ps->a[ps->top]=x）,同时让栈顶top++。

//入栈
void STPush(ST* ps, STDataType x)
{
   
    assert(ps);
    if (ps->top == ps->capacity)
    {
   
        int newCapacity = ps->capacity == 0 ? INIT_CAPACITY : ps->capacity * 2;
        STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
        if (tmp == NULL)
        {
   
            perror("realloc failed");
            exit(-1);
        }
        ps->a = tmp;
        ps->capacity = newCapacity;
    }
    ps->a[ps->top] = x;
    ps->top++;
}

1.3.3 出栈

栈中必须有元素我们才能进行出栈的操作。所以我们要使用assert(ps->a>0)断言，同时也要用assert()保证指针ps的合理性。

出栈我们直接让栈顶top--即可。

//出栈
void STPop(ST* ps)
{
   
    assert(ps);
    //空
    assert(ps->a > 0);
    --ps->top;
}

1.3.4 获取栈顶元素

栈中必须有元素我们才能获取栈顶元素。所以我们要使用assert(ps->a>0)断言，同时也要用assert()保证指针ps的合理性。

栈顶元素就是下标为top-1位置的元素。

//获取栈顶元素
STDataType STTop(ST* ps)
{
   
    assert(ps);
    //空
    assert(ps->a > 0);
    return ps->a[ps->top - 1];
}

1.3.5 获取栈中有效元素个数

assert()断言保证指针ps的合理性，直接返回top即可。

//获取栈中有效元素个数
int STSize(ST* ps)
{
   
    assert(ps);
    return ps->top;
}

1.3.6 检测栈是否为空

assert()断言保证指针ps的合理性，判断top是否为0，并返回。

//检测栈是否为空
bool STEmpty(ST* ps)
{
   
    assert(ps);
    return ps->top == 0;
}

1.3.7 销毁栈

assert()断言保证指针ps的合理性。将指针a置空，将栈顶top和容量capacity都为0。

//销毁栈
void STDestroy(ST* ps)
{
   
    assert(ps);
    ps->a = NULL;
    ps->top = ps->capacity = 0;
}

1.4 栈的完整代码

1.4.1 Stack.h

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

//支持动态增长的栈
typedef int STDataType;
#define INIT_CAPACITY 4
typedef struct Stack
{
   
    STDataType* a;  //指向动态开辟的数组
    int top;  //栈顶
    int capacity;  //容量
}ST;

//初始化栈
void STInit(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//获取栈顶元素
STDataType STTop(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);
//检测栈是否为空
bool STEmpty(ST* ps);
//销毁栈
void STDestroy(ST* ps);

1.4.2 Stack.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"

//初始化栈
void STInit(ST* ps)
{
   
    assert(ps);
    ps->a = NULL;
    ps->top = 0;
    ps->capacity = 0;
}

//入栈
void STPush(ST* ps, STDataType x)
{
   
    assert(ps);
    if (ps->top == ps->capacity)
    {
   
        int newCapacity = ps->capacity == 0 ? INIT_CAPACITY : ps->capacity * 2;
        STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
        if (tmp == NULL)
        {
   
            perror("realloc failed");
            exit(-1);
        }
        ps->a = tmp;
        ps->capacity = newCapacity;
    }
    ps->a[ps->top] = x;
    ps->top++;
}

//出栈
void STPop(ST* ps)
{
   
    assert(ps);
    //空
    assert(ps->a > 0);
    --ps->top;
}

//获取栈顶元素
STDataType STTop(ST* ps)
{
   
    assert(ps);
    //空
    assert(ps->a > 0);
    return ps->a[ps->top - 1];
}

//获取栈中有效元素个数
int STSize(ST* ps)
{
   
    assert(ps);
    return ps->top;
}

//检测栈是否为空
bool STEmpty(ST* ps)
{
   
    assert(ps);
    return ps->top == 0;
}

//销毁栈
void STDestroy(ST* ps)
{
   
    assert(ps);
    ps->a = NULL;
    ps->top = ps->capacity = 0;
}

1.4.3 Test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"

void TestStack()
{
   
    ST st;
    STInit(&st);
    STPush(&st, 1);
    STPush(&st, 2);
    STPush(&st, 3);
    STPush(&st, 4);
    STPush(&st, 5);

    while (!STEmpty(&st))
    {
   
        printf("%d ", STTop(&st));
        STPop(&st);
    }
    printf("\n");
    STDestroy(&st);
}

int main()
{
   
    TestStack();
    return 0;
}

image.png

2. 队列

2.1 队列的概念及结构

队列（queue）是一种特殊的线性表，只允许在表的后端（rear）进行插入数据操作，只允许在表的前端（front）进行删除数据操作。进行插入操作的一端称为队尾，进行删除操作的一端称为队头 。队列中的数据元素遵循先进先出的原则。

入队：在队尾插入一个队列元素称为入队。

出队：从队头删除一个队列元素称为出队。
image.png
​​​​image.png
​​image.png

2.2 队列的定义

队列也可以用数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

typedef int QDataType;
typedef struct QueueNode
{
   
    QDataType data;
    struct QueueNode* next;
}QNode;
使用结构体创建一个队列（用单链表实现）。

用**QDataType**替换**int**，方便对不同类型的数据进行修改。

用**QNode**替换**struct QueueNode**，方便简洁。

typedef struct Queue
{
   
    QNode* head;
    QNode* tail;
    int size;
}Que;

我们这里再用一个结构体存储头指针head，尾指针tail和队列的长度size。

2.3 队列的接口实现

队列的所有接口函数一览：

#pragma once

#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* head;
    QNode* tail;
    int size;
}Que;

//初始化队列
void QueueInit(Que* pq);
//队尾入队列
void QueuePush(Que* pq,QDataType x);
//队头出队列
void QueuePop(Que* pq);
//获取队列头部元素
QDataType QueueFront(Que* pq);
//获取队列队尾元素
QDataType QueueBack(Que* pq);
//获取队列中有效元素个数
QDataType QueueSize(Que* pq);
//检测队列是否为空
bool QueueEmpty(Que* pq);
//销毁队列
void QueueDestroy(Que* pq);

这些接口函数主要实现了队列的基本功能，接下来我们一一实现这些函数！

2.3.1 初始化队列

将头指针head和尾指针tail均置空，将size置为0。这里要注意assert()断言，保证pq指针的合理性。

//初始化队列
void QueueInit(Que* pq)
{
   
    assert(pq);
    pq->head = pq->tail = NULL;
    pq->size = 0;
}

2.3.2 入队

首先使用assert()断言，保证pq指针的合理性。

接着我们使用malloc()函数创建一个新结点。如果malloc()函数的返回值为空（即这里的newnode==NULL），我们就用perror()函数打印提示相应错误，并用exit(-1)退出整个程序。

我们将这个新结点的值赋为x（newnode->data=x），

将新结点的next指针置空(newnode->next=NULL)。

入队其实就是进行单链表的尾插操作，但是也需要考虑不同情况：

（1）如果是尾插第一个结点，我们就让头指针head和尾指针tail都指向新结点newnode。

（2）其他情况就正常尾插，让tail的next指向新结点newnode，同时tail往后走一步。

最后我们让size++即可。

//入队
void QueuePush(Que* pq, QDataType x)
{
   
    assert(pq);
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (newnode == NULL)
    {
   
        perror("malloc failed");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;
    if (pq->tail == NULL)
    {
   
        pq->head = pq->tail = newnode;
    }
    else
    {
   
        pq->tail->next = newnode;
        pq->tail = newnode;
    }
    pq->size++;
}

2.3.3 出队

首先使用assert()断言，保证pq指针的合理性。因为我们要让队头元素出队，所以队列不能为空，当队列为空时，我们也使用assert()断言。

出队其实就是进行单链表的头删操作，出队时我们也要分情况讨论：

（1）当队列只有一个结点时，我们直接释放掉这个结点（free(pq->head)）,再让头指针head和尾指针tail置空。

（2）当队列不止一个结点时，我们定义一个结构体指针next保存头结点的下一个结点，用free()释放掉头结点，再让头指针head指向next指针。

最后我们让size--即可。

//出队
void QueuePop(Que* pq)
{
   
    assert(pq);
    //队列为空
    assert(!QueueEmpty(pq));
    //只有一个结点
    if (pq->head->next == NULL)
    {
   
        free(pq->head);
        pq->head = pq->tail = NULL;
    }
    else
    {
   
        QNode* next = pq->head->next;
        free(pq->head);
        pq->head = next;
    }
    pq->size--;
}

2.3.4 获取队头元素

首先使用assert()断言，保证pq指针的合理性。因为我们要获取队头元素，所以队列不能为空，当队列为空时，我们也使用assert()断言。

返回头结点的值(head->data)即可。

//获取队头元素
QDataType QueueFront(Que* pq)
{
   
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->head->data;
}

2.3.5 获取队尾元素

首先使用assert()断言，保证pq指针的合理性。因为我们要获取队尾元素，所以队列不能为空，当队列为空时，我们也使用assert()断言。

返回尾结点的值（tail->data）即可。

//获取队尾元素
QDataType QueueBack(Que* pq)
{
   
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->tail->data;
}

2.3.6 获取队列中有效元素个数

assert()断言保证指针pq的合理性，直接返回size即可。

//获取队列中有效元素个数
QDataType QueueSize(Que* pq)
{
   
    assert(pq);
    return pq->size;
}

2.3.7 检测队列是否为空

先用assert()断言保证指针pq的合理性。判断head是否为空，并返回。

//检测队列是否为空
bool QueueEmpty(Que* pq)
{
   
    assert(pq);
    return pq->head == NULL;
}

2.3.8 销毁队列

assert()断言保证指针pq的合理性。定义一个结构体指针cur遍历整个链表，依次用free()释放掉每个结点。因为直接free释放当前的结点会导致找不到下一个结点，所以我们使用结构体指针next保存当前结点的下一个结点。通过while循环遍历，就能依次释放链表中的每个结点。

最后将头指针head和尾指针tail都置空。将队列长度size置为0。

//销毁队列
void QueueDestroy(Que* pq)
{
   
    assert(pq);
    QNode* cur = pq->head;
    while (cur)
    {
   
        QNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->head = pq->tail = NULL;
    pq->size = 0;
}

2.4 队列的完整代码

2.4.1 Queue.h

#pragma once

#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* head;
    QNode* tail;
    int size;
}Que;

//初始化队列
void QueueInit(Que* pq);
//入队
void QueuePush(Que* pq,QDataType x);
//出队
void QueuePop(Que* pq);
//获取队头元素
QDataType QueueFront(Que* pq);
//获取队尾元素
QDataType QueueBack(Que* pq);
//获取队列中有效元素个数
QDataType QueueSize(Que* pq);
//检测队列是否为空
bool QueueEmpty(Que* pq);
//销毁队列
void QueueDestroy(Que* pq);

2.4.2 Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"

//初始化队列
void QueueInit(Que* pq)
{
   
    assert(pq);
    pq->head = pq->tail = NULL;
    pq->size = 0;
}

//入队
void QueuePush(Que* pq, QDataType x)
{
   
    assert(pq);
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (newnode == NULL)
    {
   
        perror("malloc failed");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;
    if (pq->tail == NULL)
    {
   
        pq->head = pq->tail = newnode;
    }
    else
    {
   
        pq->tail->next = newnode;
        pq->tail = newnode;
    }
    pq->size++;
}

//出队
void QueuePop(Que* pq)
{
   
    assert(pq);
    //队列为空
    assert(!QueueEmpty(pq));
    //只有一个结点
    if (pq->head->next == NULL)
    {
   
        free(pq->head);
        pq->head = pq->tail = NULL;
    }
    else
    {
   
        QNode* next = pq->head->next;
        free(pq->head);
        pq->head = next;
    }
    pq->size--;
}

//获取队头元素
QDataType QueueFront(Que* pq)
{
   
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->head->data;
}

//获取队尾元素
QDataType QueueBack(Que* pq)
{
   
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->tail->data;
}

//获取队列中有效元素个数
QDataType QueueSize(Que* pq)
{
   
    assert(pq);
    return pq->size;
}

//检测队列是否为空
bool QueueEmpty(Que* pq)
{
   
    assert(pq);
    return pq->head == NULL;
}

//销毁队列
void QueueDestroy(Que* pq)
{
   
    assert(pq);
    QNode* cur = pq->head;
    while (cur)
    {
   
        QNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->head = pq->tail = NULL;
    pq->size = 0;
}

2.4.3 Test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"

void TestQueue()
{
   
    Que q;
    QueueInit(&q);
    QueuePush(&q, 1);
    QueuePush(&q, 2);
    QueuePush(&q, 3);
    QueuePush(&q, 4);
    QueuePush(&q, 5);

    while (!QueueEmpty(&q))
    {
   
        printf("%d ", QueueFront(&q));
        QueuePop(&q);
    }
    printf("\n");
    QueueDestroy(&q);
}
int main()
{
   
    TestQueue();
    return 0;
}

3. 总结

到这里，我们就用C语言实现了数据结构中的栈和队列。有什么问题欢迎在评论区讨论。如果觉得文章有什么不足之处，可以在评论区留言。如果喜欢我的文章，可以点赞收藏哦！

​

文章标签：
存储
C语言
前端开发
DataX
关键词：
数据结构队列
数据结构栈
数据结构栈队列
数据结构栈和队列
是基德吖
目录
相关文章
服务端技术栈
|
22天前
栈的几个经典应用，真的绝了
文章总结了栈的几个经典应用场景，包括使用两个栈来实现队列的功能以及利用栈进行对称匹配，并通过LeetCode上的题目示例展示了栈在实际问题中的应用。
服务端技术栈
35 1
栈的几个经典应用，真的绝了
可能只会写BUG
|
3天前
|
Linux C++ Windows
栈对象返回的问题 RVO / NRVO
具名返回值优化（(Name)Return Value Optimization，(N)RVO）是一种优化机制，在函数返回对象时，通过减少临时对象的构造、复制构造及析构调用次数来降低开销。在C++中，通过直接在返回位置构造对象并利用隐藏参数传递地址，可避免不必要的复制操作。然而，Windows和Linux上的RVO与NRVO实现有所不同，且接收栈对象的方式也会影响优化效果。
可能只会写BUG
12 2
小狮子安度因1
|
19天前
|
负载均衡 网络协议 安全
DKDP用户态协议栈-kni
DKDP用户态协议栈-kni
小狮子安度因1
22 5
小Lee
|
18天前
|
存储 安全 编译器
缓冲区溢出之栈溢出（Stack Overflow
【8月更文挑战第18天】
小Lee
39 3
小狮子安度因1
|
19天前
|
负载均衡 网络协议 安全
DPDK用户态协议栈-KNI
DPDK用户态协议栈-KNI
小狮子安度因1
56 4
aliyun6365824167
|
19天前
|
测试技术
【初阶数据结构篇】栈的实现（附源码）
在每一个方法的第一排都使用assert宏来判断ps是否为空（避免使用时传入空指针，后续解引用都会报错）。
aliyun6365824167
26 2
1387503158665997
|
5天前
crash —— 获取内核地址布局、页大小、以及栈布局
crash —— 获取内核地址布局、页大小、以及栈布局
1387503158665997
10 0
Star时光
|
6天前
|
存储 程序员 C语言
堆和栈之间有什么区别
【9月更文挑战第1天】堆和栈之间有什么区别
Star时光
48 0
cz游客
|
15天前
|
机器学习/深度学习 消息中间件 缓存
栈与队列的实现
栈与队列的实现
cz游客
35 0
aliyun6365824167
|
19天前
|
测试技术
【初阶数据结构篇】队列的实现（赋源码）
首先队列和栈一样，不能进行遍历和随机访问，必须将队头出数据才能访问下一个，这样遍历求个数是不规范的。
aliyun6365824167
22 0