备案控制台
开发者社区 人工智能 文章 正文

【C/数据结构和算法】：栈和队列

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

1. 栈

1.1 栈的概念及结构

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

压栈：栈的插入操作叫做进栈/压栈/入栈。入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

1.2 栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾插和头删的实际复杂度为O(1)，是非常合适的。

1.3 栈的功能

  • 初始化栈
  • 销毁栈
  • 入栈
  • 出栈
  • 获取栈顶元素
  • 获取栈内有效元素的个数
  • 判断栈内是否为空，如果为空返回非0结果，不为空返回0

1.4 栈的功能的实现

（1）定义一个动态增长的栈

typedef int STDataType;
typedef struct Stack
{
  STDataType* a;
  STDataType top;//定义栈顶
  size_t capacity;//栈的容量
}ST;

（2）初始化栈

void StackInit(ST* ps)
{
  //初始化空间
   ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
  if (ps->a == NULL)
  {
    printf("malloc fail!\n");
    return;
  }
  ps->top = 0;//top指向的是栈顶元素的下一个
  ps->capacity = 4;//初始化4个空间
}

（3）销毁栈

void StackDestory(ST* ps)
{
  free(ps->a);
  ps->a = NULL;
  ps->capacity = 0;
  ps->top = 0;
}

（4）入栈（相当于顺序表的尾插）

void StackPush(ST* ps, STDataType x)
{
  //插入数据之前判断是否增容
  if (ps->top == ps->capacity)
  {
    STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * sizeof(STDataType) * 2);
    if (tmp == NULL)
    {
      printf("realloc fail!\n");
      return;
    }
    else
    {
      ps->a = tmp;
      ps->capacity *= 2;
    }
  }
   
   //注意由于我们定义top=0,这两条语句的顺序不能调换
  ps->a[ps->top] = x;
  ps->top++;
}

（5）出栈（相当于顺序表的头删）

void StackPop(ST* ps)
{
  assert(ps);//断言
    assert(ps->top>0);//栈空了，就要停止删除
    
  ps->top--;
}

（6）获取栈顶元素

STDataType StackTop(ST* ps)
{
  assert(ps);//断言
  assert(ps->top > 0);//栈为空时，防止越界
  return ps->a[ps->top - 1];
}

（7）获取栈内有效元素的个数

int StackSize(ST* ps)
{
  assert(ps);
  return ps->top;
}

（8）判断栈内是否为空，如果为空返回非0结果，不为空返回0

bool StackEmpty(ST* ps)
{
  assert(ps);
  return ps->top == 0;
}

1.5 完整代码

Stack.h

#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int STDataType;
typedef struct Stack
{
  STDataType* a;
  STDataType top;//定义栈顶
  size_t capacity;//栈的容量
}ST;
//初始化栈
void StackInit(ST* ps);
//销毁栈
void StackDestory(ST* ps);
//从栈顶插入数据
void StackPush(ST* ps, STDataType x);
//从栈顶删除数据
void StackPop(ST* ps);
//获取栈顶元素
STDataType StackTop(ST* ps);
//获取栈内有效元素个数
int StackSize(ST* ps);
//判断栈内是否为空，如果为空返回非0结果，不为空返回0
bool StackEmpty(ST* ps);

Stack.c

#define _CRT_SECURE_NO_WARNINGS 
#include "Stack.h"
void StackInit(ST* ps)
{
  //初始化空间
   ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
  if (ps->a == NULL)
  {
    printf("malloc fail!\n");
    return;
  }
  ps->top = 0;//top指向的是栈顶元素的下一个
  ps->capacity = 4;//初始化4个空间
}
void StackPush(ST* ps, STDataType x)
{
  //插入数据之前判断是否增容
  if (ps->top == ps->capacity)
  {
    STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * sizeof(STDataType) * 2);
    if (tmp == NULL)
    {
      printf("realloc fail!\n");
      return;
    }
    else
    {
      ps->a = tmp;
      ps->capacity *= 2;
    }
  }
  
    //注意由于我们定义top=0,这两条语句的顺序不能调换
  ps->a[ps->top] = x;
  ps->top++;
}
void StackPop(ST* ps)
{
  assert(ps);//断言
    assert(ps->top>0);//栈空了，就要停止删除
  ps->top--;
}
STDataType StackTop(ST* ps)
{
  assert(ps);//断言
  assert(ps->top > 0);//栈为空时，防止越界
  return ps->a[ps->top - 1];
}
int StackSize(ST* ps)
{
  assert(ps);
  return ps->top;
}
bool StackEmpty(ST* ps)
{
  assert(ps);
  return ps->top == 0;
}
void StackDestory(ST* ps)
{
  free(ps->a);
  ps->a = NULL;
  ps->capacity = 0;
  ps->top = 0;
}

Test.c

#define _CRT_SECURE_NO_WARNINGS 
#include "Stack.h"
void StackTest()
{
  ST st;
  StackInit(&st);
  StackPush(&st, 1);
  StackPush(&st, 2);
  StackPush(&st, 3);
  StackPush(&st, 4);
  //打印栈内的数据，由于不能破坏栈的后进先出特性，
  //所以不能直接从头开始遍历打印
  
  while (!StackEmpty(&st))
  {
    //输出栈顶元素，再删除
    printf("%d ", StackTop(&st));
    StackPop(&st);
  }
  StackDestory(&st);
}
int main()
{
  StackTest();
  return 0;
}

2. 队列

2.1 队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出

FIFO(First In First Out)

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

2.2 队列的实现

队列也可以数组和链表的结构实现，使用单链表的结构实现更优一些。

因为如果使用数组的结构，出队列在数组头上出数据，这时需要挪动数据，时间复杂度为O(n)，效率会比较低。

而单链表的尾插和头删的时间复杂度为O（1），十分合适。

2.3 队列的功能

  • 初始化队列
  • 销毁队列
  • 入队列
  • 出队列
  • 获取队列头部元素
  • 获取队列尾部元素
  • 获取队列中有效元素的个数
  • 判断队列是否为空，为空返回非0，不为空返回0

2.4 队列的功能的实现

（1）定义一个队列

typedef int QTDataType;
typedef struct QNode
{
  struct QNode* next;
  QTDataType data;
}QNode;
typedef struct Queue
{
  struct QNode* tail;
  struct QNode* head;
}Queue;

（2）初始化队列

void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = pq->tail = NULL;
}

（3）销毁队列

void QueueDestory(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->head;
  while (cur)
  {
      QNode* next = cur-> next;
    free(cur);
    cur = next;
  }
  pq->head = pq->tail = NULL;
}

（4）入队列(相当于单链表的尾插）

void QueuePush(Queue* pq, QTDataType x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    printf("malloc fail!\n");
    return;
  }
  newnode->data = x;
  newnode->next = NULL;
  //没有一个结点
  if (pq->tail == NULL)
  {
    pq->head = pq->tail = newnode;
  }
  //多个节点
  else
  {
    pq->tail->next = newnode;
    pq->tail = newnode;
  }
}

（5）出队列（相当于单链表的头删）

void QueuePop(Queue* pq)
{
  assert(pq);
  assert(pq->head);//防止队列为空
  //只有一个节点时，防止tail成为野指针
  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;
  }
}

（6）获取队列头部元素

QTDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(pq->head);//防止队列为空
  return pq->head->data;
}

（7）获取队列尾部元素

QTDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(pq->head);
  return pq->tail->data;
}

（8）获取队列中有效元素的个数

int QueueSize(Queue* pq)
{
  assert(pq);
  int size = 0;
  QNode* cur = pq->head;
  while (cur)
  {
    size++;
    cur = cur->next;
  }
  return size;
}

（9）判断队列是否为空，为空返回非0，不为空返回0

int QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->head == NULL;
}

2.5 完整代码

Queue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int QTDataType;
typedef struct QNode
{
  struct QNode* next;
  QTDataType data;
}QNode;
typedef struct Queue
{
  struct QNode* tail;
  struct QNode* head;
}Queue;
//初始化队列
void QueueInit(Queue* pq);
//销毁队列
void QueueDestory(Queue* pq);
//队尾入队列
void QueuePush(Queue* pq, QTDataType x);
//队头出队列
void QueuePop(Queue* pq);
//获取队列头部元素
QTDataType QueueFront(Queue* pq);
//获取队列尾部元素
QTDataType QueueBack(Queue* pq);
//判断队列是否为空，为空返回非0，不为空返回0
int QueueEmpty(Queue* pq);
//获取队列中有效元素的个数
int QueueSize(Queue* pq);

Queue.c

#define _CRT_SECURE_NO_WARNINGS 
#include "Queue.h"
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QTDataType x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    printf("malloc fail!\n");
    return;
  }
  newnode->data = x;
  newnode->next = NULL;
  //没有一个结点
  if (pq->tail == NULL)
  {
    pq->head = pq->tail = newnode;
  }
  //多个节点
  else
  {
    pq->tail->next = newnode;
    pq->tail = newnode;
  }
}
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(pq->head);//防止队列为空
  //只有一个节点时，防止tail成为野指针
  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;
  }
}
int QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->head == NULL;
}
QTDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(pq->head);//防止队列为空
  return pq->head->data;
}
QTDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(pq->head);
  return pq->tail->data;
}
int QueueSize(Queue* pq)
{
  assert(pq);
  int size = 0;
  QNode* cur = pq->head;
  while (cur)
  {
    size++;
    cur = cur->next;
  }
  return size;
}
void QueueDestory(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->head;
  while (cur)
  {
      QNode* next = cur-> next;
    free(cur);
    cur = next;
  }
  pq->head = pq->tail = NULL;
}

Test.c

#define _CRT_SECURE_NO_WARNINGS 
#include "Queue.h"
void QueueTest()
{
  Queue q;
  QueueInit(&q);
  
  QueuePush(&q, 1);
  QueuePush(&q, 2);
  QueuePush(&q, 3);
  QueuePush(&q, 4);
  
    //打印队列内的数据，由于不能破坏队列先进先出的特性，
    //所以不能直接遍历，需要出一个删一个
  while (!QueueEmpty(&q))
  {
    printf("%d ", QueueFront(&q));
    QueuePop(&q);
  }
  QueueDestory(&q);
}
int main()
{
  QueueTest();
  return 0;
}
文章标签：
算法
关键词：
算法数据结构
数据结构算法
数据结构队列
算法栈队列
算法队列
24k纯甄
目录
相关文章
倔强的石头_
|
2天前
|
算法 C语言
【数据结构与算法 经典例题】使用栈实现队列（图文详解）
【数据结构与算法 经典例题】使用栈实现队列（图文详解）
倔强的石头_
10 0
倔强的石头_
|
2天前
|
算法 C语言
【数据结构与算法 经典例题】使用队列实现栈（图文详解）
【数据结构与算法 经典例题】使用队列实现栈（图文详解）
倔强的石头_
11 1
weixin_836869520
|
2天前
|
算法 Java
Java数据结构与算法：最短路径算法
Java数据结构与算法：最短路径算法
weixin_836869520
3 0
枫叶丹4
|
2天前
【海贼王的数据航海】栈和队列
【海贼王的数据航海】栈和队列
枫叶丹4
4 0
反季雪
|
2天前
|
存储 算法 搜索推荐
【数据结构和算法】--- 基于c语言排序算法的实现（2）
【数据结构和算法】--- 基于c语言排序算法的实现（2）
反季雪
4 0
我爱matlab
|
2天前
|
机器学习/深度学习 自然语言处理 算法
m基于深度学习的OFDM+QPSK链路信道估计和均衡算法误码率matlab仿真,对比LS,MMSE及LMMSE传统算法
**摘要：** 升级版MATLAB仿真对比了深度学习与LS、MMSE、LMMSE的OFDM信道估计算法，新增自动样本生成、复杂度分析及抗频偏性能评估。深度学习在无线通信中，尤其在OFDM的信道估计问题上展现潜力，解决了传统方法的局限。程序涉及信道估计器设计，深度学习模型通过学习导频信息估计信道响应，适应频域变化。核心代码展示了信号处理流程，包括编码、调制、信道模拟、降噪、信道估计和解调。
我爱matlab
23 8
可编程芯片开发
|
4天前
|
算法
基于GA遗传优化的混合发电系统优化配置算法matlab仿真
**摘要：** 该研究利用遗传算法（GA）对混合发电系统进行优化配置，旨在最小化风能、太阳能及电池储能的成本并提升系统性能。MATLAB 2022a用于实现这一算法。仿真结果展示了一系列图表，包括总成本随代数变化、最佳适应度随代数变化，以及不同数据的分布情况，如负荷、风速、太阳辐射、弃电、缺电和电池状态等。此外，代码示例展示了如何运用GA求解，并绘制了发电单元的功率输出和年变化。该系统原理基于GA的自然选择和遗传原理，通过染色体编码、初始种群生成、适应度函数、选择、交叉和变异操作来寻找最优容量配置，以平衡成本、效率和可靠性。
可编程芯片开发
36 11
软件算法开发
|
5天前
|
机器学习/深度学习 算法
基于鲸鱼优化的knn分类特征选择算法matlab仿真
**基于WOA的KNN特征选择算法摘要** 该研究提出了一种融合鲸鱼优化算法（WOA）与K近邻（KNN）分类器的特征选择方法，旨在提升KNN的分类精度。在MATLAB2022a中实现，WOA负责优化特征子集，通过模拟鲸鱼捕食行为的螺旋式和包围策略搜索最佳特征。KNN则用于评估特征子集的性能。算法流程包括WOA参数初始化、特征二进制编码、适应度函数定义（以分类准确率为基准）、WOA迭代搜索及最优解输出。该方法有效地结合了启发式搜索与机器学习，优化特征选择，提高分类性能。
软件算法开发
30 9
软件算法开发
|
22小时前
|
机器学习/深度学习 存储 算法
基于SFLA算法的神经网络优化matlab仿真
**摘要：** 使用MATLAB2022a，基于SFLA算法优化神经网络，降低训练误差。程序创建12个神经元的前馈网络，训练后计算性能。SFLA算法寻找最优权重和偏置，更新网络并展示训练与测试集的预测效果，以及误差对比。SFLA融合蛙跳与遗传算法，通过迭代和局部全局搜索改善网络性能。通过调整算法参数和与其他优化算法结合，可进一步提升模型预测精度。
软件算法开发
11 3
简简单单做算法
|
5天前
|
机器学习/深度学习 算法 数据可视化
基于BP神经网络的64QAM解调算法matlab性能仿真
**算法预览图省略** MATLAB 2022A版中，运用BP神经网络进行64QAM解调。64QAM通过6比特映射至64复数符号，提高数据速率。BP网络作为非线性解调器，学习失真信号到比特的映射，对抗信道噪声和多径效应。网络在处理非线性失真和复杂情况时展现高适应性和鲁棒性。核心代码部分未显示。
简简单单做算法
22 7

热门文章

最新文章

  • 1
    【视频】支持向量机算法原理和Python用户流失数据挖掘SVM实例（上）
  • 2
    【视频】支持向量机算法原理和Python用户流失数据挖掘SVM实例（下）
  • 3
    m基于LDPC编译码的matlab误码率仿真,对比SP,MS,NMS以及OMS四种译码算法
  • 4
    【Python机器学习专栏】关联规则学习：Apriori算法详解
  • 5
    【Python机器学习专栏】t-SNE算法在数据可视化中的应用
  • 6
    【Python机器学习专栏】层次聚类算法的原理与应用
  • 7
    【AI 初识】人工智能中使用了哪些不同的搜索算法？
  • 8
    论文介绍：进化算法优化模型融合策略
  • 9
    深度解析深度学习中的优化算法：从梯度下降到自适应方法
  • 10
    探索机器学习中的算法优化之路
  • 1
    Redis数据类型详解：选择合适的数据结构优化你的应用
    78
  • 2
    【算法与数据结构】二叉树（前中后）序遍历2
    24
  • 3
    【MongoDB】MongoDB 如何处理复杂的数据结构？
    39
  • 4
    【数据结构】排序算法
    35
  • 5
    【数据结构】C语言实现链队列(附完整运行代码)
    54
  • 6
    深入理解InnoDB索引数据结构和算法
    75
  • 7
    【数据结构】深入浅出理解链表中二级指针的应用
    44
  • 8
    【数据结构】线性表的链式存储结构
    29
  • 9
    【数据结构】C语言实现顺序表万字详解(附完整运行代码)
    52
  • 10
    【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现（字典）（二）
    75

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • “大数据+算法”助力B2B未来商业
  • 数据+算法定义新世界
  • Apache Flink 流式应用中状态的数据结构定义升级

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • RSA密码算法设计与实现
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    部署LAMP环境（Alibaba Cloud Linux 3）