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

【初阶数据结构】栈和队列——C语言（详解）

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

一、栈


1.1栈的概念及结构


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

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

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

df35ff00bcf34887aac14bf73aa73842.png

b5d8e2f307ff4830a6087b4fcf2bb248.png


1.2栈的实现


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

8c5a09c3c14a40eabebfa6be67f4f65e.png

73bae85e38d5469abd479a5e204310b3.png


1.2.1静态栈的实现


实际中一般不用，我们主要使用支持动态增长的栈

typedef int STDataType;
#define N 10
typedef struct Stack
{
STDataType _a[N];
int _top; // 栈顶
}Stack;


1.3动态栈的实现


1.3.1栈的创建


typedef int STDatatype;
typedef struct STack
{
  STDatatype* a;
  int capacity;
  int top;
}ST;


这个结构和顺序表相似，a指向动态开辟的数组，capacity指的是动态开辟数组的容量，只不过这里的top指向的是栈顶也可以变相理解为栈里面的元素个数 。


1.3.2栈的初始化


void STInti(ST*st)
{
  st->a = NULL;
  st->capacity = 0;
  st->top = 0;//栈顶元素的下一个
}


当这里的top为0时我们插入一个元素，top会++，此时top可以取0或者1，但是我们已经插入一个数据了，因此top代表栈顶元素的下一个。


1.3.3栈的清空销毁


void STDer(ST* st)
{
  assert(st);
  free(st->a);
  st->capacity = st->top = 0;
}


首先就是要用assert判断是否传入栈了，如果传入栈就释放动态开辟的空间，再将容量置空，栈顶和栈底相融合。


1.3.4栈的元素插入


void STPush(ST* st,STDatatype x)
{
  if (st->capacity == st->top)
  {
    int newcapacity = st->capacity == 0 ? 4 : st->capacity * 2;
    STDatatype* tmp = (STDatatype*)realloc(st->a, sizeof(STDatatype) * newcapacity);
    if (tmp == NULL)
    {
      perror("realloc failed");
      exit(-1);
    }
    st->a = tmp;
    st->capacity = newcapacity;
  }
  st->a[st->top] = x;
  st->top++;
}


插入元素时我们要判断容量和栈顶是否融合，如果融合就要开辟新的空间，然后将想要插入的数据放入栈中，再将栈顶后移。


1.3.5栈顶元素的删除


void STPop(ST* st)
{
  assert(st);
  assert(st->top);
  st->top--;
}


删除元素时不仅要判断是否有栈还要判断栈中的top是否为0，如果不为0，直接将top--就行；


1.3.6返回栈顶数据


STDatatype STTop(ST* st)
{
  assert(st);
  assert(st->top > 0);
  return st->a[st->top-1];
}


返回栈顶数据top一定要大于0，当top为1时候返回的是top-1也就是0的值，然后top--此时top为0，当一开始的top为0时会造成越界，这点我们要注意。


1.3.7求栈的大小


int STSize(ST* st)
{
  assert(st);
  return st->top;
}


初始化时我们将top置为0，当我们添加一个有效数据时top会++，这里的top也可以理解为栈的大小。


1.3.8判断栈是否为空


bool STEmpty(ST* st)
{
  assert(st);
  return st->top == 0;
}


当top为0时可以表示栈空，0等于0，返回bool值为true。


二、栈的实现完整代码


#define _CRT_SECURE_NO_WARNINGS 67
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDatatype;
typedef struct STack
{
  STDatatype* a;
  int capacity;
  int top;
}ST;
//初始化
void STInti(ST*st)
{
  st->a = NULL;
  st->capacity = 0;//栈顶元素的下一个
  st->top = 0;
}
//清空
void STDer(ST* st)
{
  assert(st);
  free(st->a);
  st->capacity = st->top = 0;
}
//插入
void STPush(ST* st,STDatatype x)
{
  if (st->capacity == st->top)
  {
    int newcapacity = st->capacity == 0 ? 4 : st->capacity * 2;
    STDatatype* tmp = (STDatatype*)realloc(st->a, sizeof(STDatatype) * newcapacity);
    if (tmp == NULL)
    {
      perror("realloc failed");
      exit(-1);
    }
    st->a = tmp;
    st->capacity = newcapacity;
  }
  st->a[st->top] = x;
  st->top++;
}
//删除
void STPop(ST* st)
{
  assert(st);
  assert(st->top);
  st->top--;
}
//打印d
STDatatype STTop(ST* st)
{
  assert(st);
  assert(st->top > 0);
  return st->a[st->top-1];
}
//求大小
int STSize(ST* st)
{
  assert(st);
  return st->top;
}
//判断栈是否为空
bool STEmpty(ST* st)
{
  assert(st);
  return st->top == 0;
}
int main()
{
  ST st;
  STInti(&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);
  }
  STDer(&st);
  return 0;
}

2c8871a4fcbe49a0810a2cb67c752eaa.png

由于栈的特殊性我们在输出一个栈的数据时就要删除一个空间，刚开始top指向的是栈顶元素的下一个，打印有效数据是会减一也就是栈顶元素，然后删除top--指向刚才的栈顶元素的位置。


3b9599854e1b4c2c907a04df31defd43.png


三、队列


3.1队列的概念及结构


队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头

2829c983cc3a4681bcbfae3db79af706.png


3.2队列的实现


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


b9db2c53a25243f69ef8102f4bc3f519.png


3.2.1队列的创建


typedef int QDatatype;
typedef struct QueueNode
{
  struct Queue* next;
  QDatatype data;
}QNode;
typedef struct Queue
{
  QNode* phead;
  QNode* tail;
  int size;
}Que;

这里我们使用的是无头单向非循环链表实现，但是队列的特点是先进先出，也就是对应链表中的尾插和头删，由于无头单项链表寻找尾部特别麻烦我们就在创建一个结构体里面放着指向链表结构头和尾的指针。


3.2.2队列的初始化


void QueueInit(Que* pq)
{
  assert(pq);
  pq->phead = pq->tail = NULL;
  pq->size = 0;
}

我们不能直接对队列进行初始化，只能对指向队列头和尾的两个指针初始化，将其置空。


3.2.3队列内存的释放和销毁


void QueueDer(Que* pq)
{
  assert(pq);
  QNode* cur = pq->phead;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
  free(pq->phead);
  pq->phead = pq->tail = NULL;
  pq->size = 0;
}


3.2.4插入有效数据


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


插入数据是我们要特别注意指向队列尾的指针是否尾空如果尾空代表此时还没有队列，创建新的空间让队列的头和尾都指向这个空间，如果指向队列尾的指针不为空代表尾插，让指向尾的下一个指针指向新开辟的空间，再将指向尾的指针指向新的空间。


3.2.5删除队列数据


void QueuePop(Que* pq)
{
  assert(pq);
  assert(pq->phead);
  QNode* cur = pq->phead->next;
  free(pq->phead);
  pq->phead = cur;
  pq->size--;
}

这里我们就要判断指向队列头的指针是否尾空了，如果为空代表此时没有队列即没有数据可以删除，如果不为空创建一个指针让其指向队列头的下一个，然后释放队列的头，然后再将队列的头指向刚才创建的指针。


3.2.6得到队头和队尾的数据


//得到队头数据
QDatatype QueueFront(Que* pq)
{
  assert(pq);
  assert(pq->phead);
  return pq->phead->data;
}
//得到队尾数据
QDatatype QueueBack(Que* pq)
{
  assert(pq);
  assert(pq->phead);
  return pq->tail->data;
}

这里我们也要判断指向队列头的指针是否为空，如果为空代表此时没有队列，如果不为空则直接返回指向头或者尾所指向队列内部的有效数据。


3.2.7判断是否为空


bool QueueEmpty(Que* pq)
{
  assert(pq);
  return pq->phead == NULL;
}


四、队列完整代码


#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int QDatatype;
typedef struct QueueNode
{
  struct Queue* next;
  QDatatype data;
}QNode;
typedef struct Queue
{
  QNode* phead;
  QNode* tail;
  int size;
}Que;
//初始化
void QueueInit(Que* pq)
{
  assert(pq);
  pq->phead = pq->tail = NULL;
  pq->size = 0;
}
//释放销毁内存
void QueueDer(Que* pq)
{
  assert(pq);
  QNode* cur = pq->phead;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
  //free(pq->phead);
  pq->phead = 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->next = NULL;
  newnode->data = x;
  if ( pq->tail==NULL)
  {
    pq->phead=pq->tail = newnode;
  }
  else
  {
    pq->tail->next = newnode;
    pq->tail = newnode;
  }
  pq->size++;
}
//删除数据
void QueuePop(Que* pq)
{
  assert(pq);
  assert(pq->phead);
  QNode* cur = pq->phead->next;
  free(pq->phead);
  pq->phead = cur;
  pq->size--;
}
//得到队头数据
QDatatype QueueFront(Que* pq)
{
  assert(pq);
  assert(pq->phead);
  return pq->phead->data;
}
//得到队尾数据
QDatatype QueueBack(Que* pq)
{
  assert(pq);
  assert(pq->phead);
  return pq->tail->data;
}
//得到个数
int QueueSize(Que* pq)
{
  assert(pq);
  return pq->size;
}
//判断是否为空
bool QueueEmpty(Que* pq)
{
  assert(pq);
  return pq->phead == NULL;
}
int main()
{
  Que q;
  QueueInit(&q);
  QueuePush(&q, 1);
  QueuePush(&q, 2);
  QueuePush(&q, 3);
  QueuePush(&q, 4);
  QueuePush(&q, 5);
  QueuePush(&q, 6);
  while (!QueueEmpty(&q))
  {
    printf("%d ", QueueFront(&q));
    QueuePop(&q);
  }
  printf("\n");
  QueueDer(&q);
  return 0;
}


c13f7d7a81b14d69a3bcc1e440dea70d.png

b5b0335181e948dbb5b3e45d680b9d8a.png

栈和队列的相似之处是一边得到有效数据时会一边删除或者释放内存，所以我们在在打印有效数据时就会进行这样的操作。

C语言实现栈和队列的全部内容就讲解完了，欢迎大家在评论区多多讨论！

文章标签：
C语言
关键词：
数据结构栈
数据结构c语言
队列C语言
栈C语言
数据结构栈C语言
买个心动也用券
目录
相关文章
ephemerals__
|
15天前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
90 9
那年春天
|
6天前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
15 1
德国都芳最好
|
9天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构，在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈，可以有效地解决许多与数据存储和操作相关的问题。
德国都芳最好
48 21
ephemerals__
|
14天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）
本文介绍了树和二叉树的基本概念及结构，重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树，常用于实现优先队列和高效的排序算法（如堆排序）。文章详细描述了堆的性质、存储方式及其实现方法，包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容，读者可以全面了解堆的原理和应用。
ephemerals__
57 16
ephemerals__
|
14天前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
63 8
html的七十二变
|
12天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境，每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用，每当调用一个函数，就会在栈中添加一个新的执行上下文。
html的七十二变
26 2
dufadayang
|
14天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息？
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息，操作系统能够实现用户模式和内核模式之间的无缝切换，为用户程序提供稳定、可靠的系统服务。
dufadayang
41 4
這～悸ベ雨落憂殇
|
存储 缓存 C语言
数据结构——双链表（C语言）
数据结构——双链表（C语言）
這～悸ベ雨落憂殇
46 0
ephemerals__
|
17天前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
44 4
ephemerals__
|
17天前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
37 0

热门文章

最新文章

  • 1
    C语言中的逗号操作符
  • 2
    《C语言及程序设计》实践参考——改造链表
  • 3
    C语言连接MySQL数据库
  • 4
    C语言中用于计算数组长度的函数 “strlen（） ”。
  • 5
    C语言预处理之二-----宏定义那点事儿
  • 6
    《C语言程序设计进阶教程》一第3章 预防、检测及消除bug
  • 7
    《C语言及程序设计》实践项目——数据的输入
  • 8
    C语言库函数大全及应用实例十
  • 9
    C语言中大小写字母的转化
  • 10
    【C语言进阶】字符串函数与内存函数的学习与模拟实现（上）
  • 1
    `geopandas`是一个开源项目，它为Python提供了地理空间数据处理的能力。它基于`pandas`库，并扩展了其对地理空间数据（如点、线、多边形等）的支持。`GeoDataFrame`是`geopandas`中的核心数据结构，它类似于`pandas`的`DataFrame`，但包含了一个额外的地理列（通常是`geometry`列），用于存储地理空间数据。
    69
  • 2
    “解锁Python高级数据结构新姿势：图的表示与遍历，让你的算法思维跃升新高度
    40
  • 3
    Redis数据结构—跳跃表 skiplist 实现源码分析
    64
  • 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语言核心编程 - 数据结构和算法
  • 你的第一门C语言课
  • C语言学习教程
  • Go语言核心编程 - 基础语法、数组、切片、Map

    • 相关电子书

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