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

【数据结构】栈和队列

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

​

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
关键词：
数据结构栈
数据结构队列
数据结构栈队列
数据结构栈和队列
是基德吖
目录
相关文章
ephemerals__
|
15天前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
90 9
那年春天
|
6天前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
15 1
德国都芳最好
|
9天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构，在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈，可以有效地解决许多与数据存储和操作相关的问题。
德国都芳最好
48 21
html的七十二变
|
12天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境，每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用，每当调用一个函数，就会在栈中添加一个新的执行上下文。
html的七十二变
25 2
dufadayang
|
13天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息？
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息，操作系统能够实现用户模式和内核模式之间的无缝切换，为用户程序提供稳定、可靠的系统服务。
dufadayang
41 4
肾透侧视攻城狮
|
18天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总（10）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
17 1
星霜旅人
|
1月前
数据结构（栈与列队）
数据结构（栈与列队）
星霜旅人
17 1
神明木佑
|
1月前
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中，而引用数据类型存放在堆中？
为什么基础数据类型存放在栈中，而引用数据类型存放在堆中？
神明木佑
68 1
白子寰
|
1月前
【数据结构】-- 栈和队列
【数据结构】-- 栈和队列
白子寰
16 0
java冯坚持
|
1月前
|
算法 程序员 索引
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈，并展示了如何利用栈和中缀表达式实现一个综合计算器。
java冯坚持
30 1
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器

热门文章

最新文章

  • 1
    我花了一夜用数据结构给女朋友写个H5走迷宫游戏
  • 2
    数据结构学习笔记【持续更新】
  • 3
    基于OHCI的USB主机 —— OHCI（自定义数据结构）
  • 4
    【数据结构与算法】一篇文章彻底搞懂二分查找（思路图解+代码优化）两种实现方式，递归与非递归
  • 5
    学数据结构，只需要基本的编程体验
  • 6
    数据结构（2）：栈的原理和实现
  • 7
    【数据结构7】查找
  • 8
    算法导论第十四章 数据结构的扩张
  • 9
    R语言学习笔记（一）数据结构
  • 10
    Smaller And Smarter Python数据结构：自己动手实现栈
  • 1
    `geopandas`是一个开源项目，它为Python提供了地理空间数据处理的能力。它基于`pandas`库，并扩展了其对地理空间数据（如点、线、多边形等）的支持。`GeoDataFrame`是`geopandas`中的核心数据结构，它类似于`pandas`的`DataFrame`，但包含了一个额外的地理列（通常是`geometry`列），用于存储地理空间数据。
    69
  • 2
    “解锁Python高级数据结构新姿势：图的表示与遍历，让你的算法思维跃升新高度
    40
  • 3
    Redis数据结构—跳跃表 skiplist 实现源码分析
    62
  • 4
    逆袭之路！用 Python 玩转图的 DFS 与 BFS，让数据结构难题无处遁形
    65
  • 5
    Python中的列表（List）和元组（Tuple）是两种重要的数据结构
    53
  • 6
    【数据结构OJ题】链表分割
    32
  • 7
    【数据结构常见七大排序（三）上】—交换排序篇【冒泡排序】And【快速排序】
    45
  • 8
    【数据结构常见七大排序（二）】—选择排序篇【直接选择排序】And【堆排序】
    33
  • 9
    【数据结构常见七大排序（一）】—插入排序篇【直接插入排序】And【希尔排序】
    45
  • 10
    【数据结构OJ题】链表的回文结构
    39

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    阿里云OSS设置跨域访问