C语言栈和队列的实现

article/2025/11/7 11:16:19

✅作者简介：嵌入式入坑者，与大家一起加油，希望文章能够帮助各位！！！！
📃个人主页：@rivencode的个人主页
🔥系列专栏：玩转数据结构
💬推荐一款模拟面试、刷题神器，从基础到大厂面试题👉点击跳转刷题网站进行注册学习

目录

  • 一.栈的定义和特点
  • 二.顺序栈与链栈的实现
    • 1.顺序栈的实现
    • 2.链式栈的实现
    • 3.顺序栈与链栈的对比
  • 三.队列的定义和特点
  • 四.顺序队与链队的实现
    • 1.顺序队列(循环)的实现
    • 2.链队列的实现
    • 3.顺序队列与链队的对比

一.栈的定义和特点

栈（stack）是一个特殊的线性表是限定仅在一端(通常在表尾进行插入，删除的线性表)，又称为后进先出（last in first out）的线性表简称 LIFO结构

栈是仅在表尾插入，删除操作的线性表，其实栈就是线性表的一个子集，表尾(an端)称为栈顶TOP，表头（a1端）称为栈底BASE.

  • 插入元素到栈顶的操作称为入栈、压栈、进栈

在这里插入图片描述

  • 从栈顶删除元素的操作称为出栈
    在这里插入图片描述
    栈的操作特性：后进先出

在这里插入图片描述
在这里插入图片描述

二.顺序栈与链栈的实现

在这里插入图片描述

由于栈本身就是线性表，所以栈也有顺序存储与链式存储
栈的顺序存储：顺序栈
栈的链式存储：链式栈

1.顺序栈的实现

  • 栈的顺序存储
    利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，栈底在底地址端。

在C语言中一般用数组来实现栈的顺序存储：

  • 当栈为空时
    在这里插入图片描述
  • 当栈不为空时
    在这里插入图片描述

为了操作更加方便top一般存储栈顶元素上面一个元素的下标

只要理解上面那句话，然后其实就是顺序表的尾插与尾删，用尾做了栈顶。因为顺序栈实现比较简单，这里直接上代码

stack.h


```c
#ifndef   __QSTACK_H
#define  __QSTACK_H#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include <malloc.h>typedef    int   STDataType;typedef struct  Stack
{STDataType * a;int top;int 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);
//判断栈是否为空
bool  StackEmpty(ST*ps);
#endif /* __QSTACK_H */

stack.c

#include "Stack.h"
//初始化
void  StackInit(ST* ps)
{assert(ps !=NULL);ps->a = (STDataType*)malloc(sizeof(STDataType) * 10);if (ps->a == NULL){printf("扩容失败\n");exit(-1);}ps->capacity = 10;ps->top = 0;
}
//销毁
void  StackDestory(ST* ps)
{assert(ps != NULL);free(ps->a);ps->capacity = 0;ps->top = 0;
}
//入栈
void  StackPush(ST*ps, STDataType x)
{assert(ps != NULL);//容量不够增容if (ps->top == ps->capacity){STDataType *tmp = (STDataType *)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));if (tmp == NULL){printf("扩容失败\n");exit(-1);}else{ps->a = tmp;ps->capacity *= 2;}}ps->a[ps->top] = x;ps->top++;
}
//出栈
void  StackPop(ST*ps)
{assert(ps != NULL);assert(ps->top> 0);ps->top--;
}STDataType  StackTop(ST*ps)
{assert(ps != NULL);assert(ps->top> 0);return ps->a[ps->top - 1];
}
//栈元素个数
int  StackSize(ST*ps)
{return ps->top;
}
//判断栈是否为空
bool  StackEmpty(ST*ps)
{return ps->top == 0;
}

2.链式栈的实现

1.如果用尾结点做栈顶，那么要用双向链表，因为你用单向链表话出栈，需要找尾结点以及尾结点前一个结点，时间复杂度为O（n），时间效率低。

2.如果使用单链表实现，那么就用头结点做栈顶，入栈出栈，其实就是单链表的头插与头删。
在这里插入图片描述
直接上代码：
stack.h

#ifndef    __STACK_H
#define   __STACK_H#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include <malloc.h>
typedef    int   STDataType;typedef struct  StackNode
{STDataType data;struct  Stack *next;
}SNode;typedef struct  Stack
{SNode *head;
}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);
//判断栈是否为空
bool  StackEmpty(ST*ps);#endif /* __STACK_H */

stack.c

#include "stack.h"void  StackInit(ST* ps)
{assert(ps != NULL);ps->head = NULL;
}
void  StackDestory(ST* ps)
{assert(ps != NULL);SNode*cur = ps->head;while (cur){SNode*next = cur->next;free(cur);cur = next;}ps->head = NULL;
}void  StackPush(ST*ps, STDataType x)
{assert(ps != NULL);//创建新结点SNode* NewNode = (SNode*)malloc(sizeof(SNode));if (NewNode == NULL){printf("malloc fail");exit(-1);}NewNode->data = x;NewNode->next = NULL;NewNode->next = ps->head;ps->head = NewNode;
}
void  StackPop(ST*ps)
{assert(ps != NULL);//栈不能为空assert(ps->head != NULL);SNode*next = ps->head->next;free(ps->head);ps->head = next;
}
STDataType StackTop(ST*ps)
{assert(ps != NULL);//栈不能为空assert(ps->head != NULL);return ps->head->data;
}int  StackSize(ST*ps)
{assert(ps != NULL);int count = 0;SNode*cur = ps->head;while (cur){count++;cur = cur->next;}return count;
}
bool  StackEmpty(ST*ps)
{return ps->head == NULL;
}

3.顺序栈与链栈的对比

推荐使用顺序栈：

1.在开辟内存的角度来说，链栈插入元素就需要开辟一个结点的内存，而顺序栈，是隔多个结点在整体分配一块内存。相比之下链栈需要频繁申请空间。

2.CPU向内存取数据的时候是一次取地址连续的空间里的数据，在CPU中的高速缓存或寄存器，如果是顺序栈，取数据的命中率将大大增加，而由于链栈的结点物理存储并不是连续的也就是说结点的地址各不相同，则CPU在取数据的时候每次都要向内存中去取，相比之下效率较低。

当然算法都是灵活多变的，怎么实现取决于场景和你自己

三.队列的定义和特点

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

在这里插入图片描述
队列的操作特性：先进先出
在这里插入图片描述
在这里插入图片描述

四.顺序队与链队的实现

由于队列本身就是线性表，所以队列也有顺序存储与链式存储
队列的顺序存储：顺序栈（一般是循环队列）
队列链式存储：链式栈

1.顺序队列(循环)的实现

顺序队列：在内存中用一组地址连续存储单元依次存放从对头到队尾的数据元素，同时设置两个指针front和rear分别指示队头元素和队尾元素的位置

当队列为空时front == rear
在这里插入图片描述
队列不为空
在这里插入图片描述
rear指示的队尾元素的下一个位置

如果是像上面一样不使用循环队列会有很大的缺陷
由于队列是先进先出：只能从表尾插入元素从表头删除元素

则删除一个元素则该元素的空间就无法再进行利用，数组的前端可能会出现很多空的单元，这种现象称为假溢出，则空间利用率太低。

如果我们要采用顺序存储来实现队列只能使用循环队列

定义一个队列：
加粗样式

队空时

在这里插入图片描述
队非空
在这里插入图片描述
现在出现了两个问题：
1.队空与对满的条件都是rear==front
2.如果rear或者front指示了下标为7的位置，此时在进队一个元素rear如何指示下标为0的位置，或者此时在出队一个元素frontr如何指示下标为0的位置，进而实现循环。

  • 第一个问题如何实现循环：

在这里插入图片描述
在这里插入图片描述
front与rear一样
这里的MAX_SIZE是数组的最大容量
指针front 与rear在到达末尾后自动回到数组的起始位置，达到循环的目的

进队操作时：rear=(rear+1)%MAX_SIZE

出队操作时：front=(front+1)%MAX_SIZE

  • 如何区分队空与对满的条件
    这里有三种解决方式：
    1.另外设一个标志以区别队空，队满。
    2.另设一个变量记录元素个数
    3.少用一个元素的空间

这里我们使用第三种方式非常方便：
在这里插入图片描述
循环队列满的条件：(rear+1)%MAX_SIZE = front

  • 第三个问题如何求队列中元素个数
    在这里插入图片描述
    队列中元素个数：(rear-front+MAX_SIZE)%MAX_SIZE
    别问公式怎么来的反正一切都是巧合，公式正好适用所有情况

现在已经解决了最重要的三个问题现在再去写循环队列就跟玩一样
首先循环队列只能是静态的，容量是固定的
循环队列空的条件：rear= front

进队操作时：rear=(rear+1)%MAX_SIZE

出队操作时：front=(front+1)%MAX_SIZE

循环队列满的条件：(rear+1)%MAX_SIZE = front

直接上代码了：

queue.h

#ifndef  __QUEUE_H
#define  __QUEUE_H#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>#define   MAX_SIZE      8
typedef  int	  QDataType;
typedef struct Queue
{QDataType data[MAX_SIZE];int front;int rear;
}Queue;//初始化
void QueueInit(Queue * pq);
//进队
void QueuePush(Queue * pq, QDataType x);
//出队
void QueuePop(Queue * pq);
//取队头数据
QDataType QueueFront(Queue * pq);
QDataType QueueBack(Queue * pq);int QueueSize(Queue * pq);
bool QueueEmpty(Queue * pq);
#endif /*__QUEUE_H*/

queue.c

#include "Queue.h"//初始化
void QueueInit(Queue * pq)
{assert(pq!=NULL);pq->front = pq->rear = 0;
}//进队
void QueuePush(Queue * pq, QDataType x)
{assert(pq != NULL);//队满进队失败if ((pq->rear + 1) % MAX_SIZE == pq->front){printf("queue full");exit(-1);}pq->data[pq->rear] = x;pq->rear = (pq->rear + 1) % MAX_SIZE;
}//出队
void QueuePop(Queue * pq)
{assert(pq != NULL);//队空assert(pq->front != pq->rear);pq->front = (pq->front + 1) % MAX_SIZE;}//取队头数据
QDataType QueueFront(Queue * pq)
{assert(pq != NULL);//队空assert(pq->front != pq->rear);return pq->data[pq->front];
}int QueueSize(Queue * pq)
{assert(pq != NULL);return  ((pq->rear) - (pq->rear) + MAX_SIZE) % MAX_SIZE;
}bool QueueEmpty(Queue * pq)
{assert(pq != NULL);return pq->front == pq->rear;
}

2.链队列的实现

采用链表形式的队列称为链队列，队列中每一个元素对应的链表中的一个结点，并设两个分别指示队头和队尾的指针。

在这里插入图片描述
其实本质：
出队：链表的头删
入队：链表的尾插

直接上代码：

queue.h

#ifndef  __QUEUE_H
#define  __QUEUE_H#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include <malloc.h>typedef  int	  QDataType;typedef struct QueueNode
{struct QueueNode *next;QDataType data;
}QNode;typedef struct Queue
{QNode*head;QNode*tail;
}Queue;//初始化
void QueueInit(Queue * pq);
//销毁
void QueueDestory(Queue * pq);
//进队
void QueuePush(Queue * pq, QDataType x);
//出队
void QueuePop(Queue * pq);
//取队头数据
QDataType QueueFront(Queue * pq);
QDataType QueueBack(Queue * pq);int QueueSize(Queue * pq);
bool QueueEmpty(Queue * pq);
#endif /*__QUEUE_H*/

queue.c

#include "Queue.h"void QueueInit(Queue * pq)
{assert(pq !=NULL);pq->head = pq->tail = NULL;
}void QueueDestory(Queue * pq)
{assert(pq != NULL);QNode * cur = pq->head;while (cur){QNode * next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;
}void QueuePush(Queue * pq, QDataType x)
{assert(pq != NULL);QNode * NewNode = (QNode *)malloc(sizeof(QNode));if (NewNode == NULL){printf("malloc fail\n");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;}}
void QueuePop(Queue * pq)
{assert(pq != NULL);assert(pq->head !=NULL);//只有一个结点,保证tail指针也置NULLif (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode *next = pq->head->next;free(pq->head);pq->head = next;}}
QDataType QueueFront(Queue * pq)
{assert(pq != NULL);assert(pq->head != NULL);return pq->head->data;
}
QDataType QueueBack(Queue * pq)
{assert(pq != NULL);assert(pq->head != NULL);return pq->tail->data;
}int QueueSize(Queue * pq)
{assert(pq != NULL);int count = 0;QNode *cur = pq->head;while (cur){cur = cur->next;count++;}return count;
}bool QueueEmpty(Queue * pq)
{return  pq->head == NULL;
}

3.顺序队列与链队的对比

链式存储结构的优点：
空间利用率高需要一个空间就分配一个空间，一般没有队满的情况
顺序存储的优点：
存储密度为1最高，因为没有指针域空间利用率高
顺序存储的缺点：
容量固定，容易造成空间的浪费或者队满溢出的情况

如果能事先确定队列的长度，队长的变化不大，可以考虑使用顺序队列，反之采用链队列更加合适

结束语：
最近发现一款刷题神器，如果大家想提升编程水平，玩转C语言指针，还有常见的数据结构（最重要的是链表和队列）后面嵌入式学习操作系统的时如freerots、RT-Thread等操作系统，链表与队列知识大量使用。
大家可以点击下面连接进入牛客网刷题
点击跳转进入网站(C语言方向)
点击跳转进入网站(数据结构算法方向)

在这里插入图片描述


http://chatgpt.dhexx.cn/article/MRch8GBq.shtml

相关文章

栈和队列讲解

栈和队列讲解

目录 1、栈 &#xff08;1&#xff09;栈的概念及结构 &#xff08;2&#xff09;栈的实现 2、队列 &#xff08;1&#xff09;队列的概念及结构 &#xff08;2&#xff09;队列的实现 前言&#xff1a;栈和队列是在顺序表和链表的延伸&#xff0c;如果前面的顺序表和链…
阅读更多...
栈和队列（C++）

栈和队列（C++）

栈的相关概念 栈是仅在表尾进行插入&#xff0c;删除操作的线性表 表尾称为栈顶Top&#xff0c;表头称为栈底Base 插入元素到栈顶&#xff0c;称为入栈&#xff1b;从栈顶删除最后一个元素&#xff0c;称为出栈 栈的运算规则&#xff1a;先进后出 一.顺序栈 顺序栈的表示 …
阅读更多...
栈和队列的基本操作（栈和队列的区别）

栈和队列的基本操作（栈和队列的区别）

数据结构中的栈与内存中的栈的不同 一、数据结构中的堆栈 在数据结构中的堆栈&#xff0c;实际上堆栈是两种数据结构&#xff1a;堆和栈。堆和栈都是一种数据项按序排列的数据结构。 1.栈就像装数据的桶或箱子 我们先从大家比较熟悉的栈说起吧&#xff0c;它是一种具有后进先…
阅读更多...
栈和队列——python

栈和队列——python

目录 一、栈 定义一个栈 栈的应用——括号匹配问题 栈的应用——迷宫问题 二、队列 自定义队列 python队列的内置模块 队列应用——打印文件后五行 队列应用——迷宫问题 python的数据结构与算法之栈与队列 自学视频&#xff1a;bilibili路飞学城清华大学博士讲解Pyt…
阅读更多...
栈和队列的概念

栈和队列的概念

文章目录 栈、队列和双端队列栈队列双端队列Java 中的栈、队列和双端队列 单调栈和单调队列二叉堆和优先队列二叉堆优先队列 目录 栈、队列和双端队列 栈和队列是常见的数据结构。栈的特点是后进先出&#xff0c;添加元素、删除元素和查看元素都在栈顶操作。队列的特点是先进先…
阅读更多...
栈和队列详解

栈和队列详解

文章目录 前言一、栈&#xff1a;1.栈的基本概念&#xff1a;2.如何实现栈&#xff1f;3.栈代码演示&#xff1a; 二、队列&#xff1a;1.队列的基本概念&#xff1a;2.如何实现队列&#xff1f;3.队列代码演示&#xff1a; 总结 前言 栈和队列也属于线性表&#xff0c;但是它…
阅读更多...
【数据结构】栈和队列详细分析（全）

【数据结构】栈和队列详细分析（全）

目录 1.前言2.栈的定义与特点2.1顺序栈的定义2.2顺序栈的操作2.3链栈的定义2.4链栈的操作 3.队列的定义与特点3.1循环队列3.2循环队列的操作3.3链队的定义3.4链队的操作 4.总结 1.前言 栈和队列是两种重要的线性结构。从数据结构角度看&#xff0c;栈和队列也是线性表&#xf…
阅读更多...
【Python数据结构系列】❤️《栈（顺序栈与链栈）》——❤️知识点讲解+代码实现

【Python数据结构系列】❤️《栈（顺序栈与链栈）》——❤️知识点讲解+代码实现

灵魂拷问&#xff1a;为什么要学数据结构&#xff1f; 数据结构&#xff0c;直白地理解&#xff0c;就是研究数据的存储方式。数据存储只有一个目的&#xff0c;即为了方便后期对数据的再利用。因此&#xff0c;数据在计算机存储空间的存放&#xff0c;决不是胡乱的&#xff0c…
阅读更多...
数据结构——栈与队列

数据结构——栈与队列

目录 一、栈 1.栈的定义 2.栈的分类与基本操作 1. 顺序栈 2.链栈 3.栈与递归的实现 1.递归的简单描述 2.递归过程及与栈的关联 3.递归过程示意图 二.队列 1.队列的定义 2.队列的分类与基本操作 1.顺序队列 2.链队列 3.循环队列 1.假溢出 2.循环队列 3.循环队列相…
阅读更多...
栈与队列详解

栈与队列详解

目录 申明1. 栈的定义1.1 栈的定义1.2 进栈出栈变化形式 2. 栈的抽象数据类型3. 栈的顺序存储结构及实现3.1 栈的顺序存储结构3.2 栈的顺序存储结构——进栈操作3.3 栈的顺序存储结构——出栈操作 4. 两栈共享空间5. 栈的链式存储结构及实现5.1 栈的链式存储结构5.2 栈的链式存…
阅读更多...
栈与队列（超详细）

栈与队列（超详细）

目录 一、栈&#xff08;Stack&#xff09;1、什么是栈&#xff1f;2、栈的常见方法3、自己实现一个栈&#xff08;底层用一个数组实现&#xff09; 二、队列&#xff08;Queue&#xff09;1、什么是队列&#xff1f;2、队列的常见方法3、队列的实现&#xff08;单链表实现&…
阅读更多...
C语言---栈和队列

C语言---栈和队列

严格来说,栈和队列都属于线性表 "一对一" 栈:"先进后出" 队列: "先进先出" 栈 栈只能从一端存取,另一端是封闭的 在栈中,不论是存还是取,都必须遵循"先进后出"的原则 >栈是一种只能从表的一端存取数据,且遵循"先进后出…
阅读更多...
数据结构与算法——栈和队列

数据结构与算法——栈和队列

&#x1f60a;数据结构与算法——栈和队列 &#x1f680;前言&#x1f680;栈&#xff08;satck&#xff09;&#x1f6a2;栈的定义&#x1f6a2;共享栈&#xff08;节省空间&#xff09;&#x1f6a2;栈的表示和实现&#xff08;顺序栈&#xff09;&#x1f47b;顺序栈的定义&…
阅读更多...
数据结构：栈和队列(Stack Queue)【详解】

数据结构：栈和队列(Stack Queue)【详解】

友情链接&#xff1a;数据结构专栏 目录 栈和队列【知识框架】 栈一、栈的基本概念1、栈的定义2、栈的常见基本操作 二、栈的顺序存储结构1、栈的顺序存储2、顺序栈的基本算法&#xff08;1&#xff09;初始化&#xff08;2&#xff09;判栈空&#xff08;3&#xff09;进栈&a…
阅读更多...
web 移动端开发基础

web 移动端开发基础

web 移动端开发基础 文章目录 web 移动端开发基础了解视口相关内容meta 视口标签掌握二倍图用法物理像素 & 物理像素比多倍图二倍精灵图做法 了解移动端常见选择方案掌握移动端常见问题解决方案移动端常见的布局方式流式布局&#xff08;百分比布局&#xff09;flex 布局 -…
阅读更多...
Web移动端

Web移动端

1.PC端和移动端的区别: PC端:屏幕大 用网页固定版心,要考虑浏览器兼容问题,(布局:浮动&#xff0b;定位&#xff0b;标准流) 移动端: 手机屏幕小&#xff0c;网页宽度多数为100%&#xff0c;是适配手机屏幕宽度 移动端则基本不需要考虑兼容性问题&#xff0c;放心大胆使用CS…
阅读更多...
移动端网页开发基础

移动端网页开发基础

文章目录 前言一、浏览器1.pc端常见浏览器2.移动端常见浏览器 二、视口1.布局视口layout viewport2.视觉视口visual viewport3.理想视口ideal viewport 三、二倍图1.物理像素和物理像素比2.二倍图用法 四、移动端开发选择1.单独制作移动端页面2.响应式兼容pc移动端3.移动端常见…
阅读更多...
20.【移动端Web开发之响应式布局】

20.【移动端Web开发之响应式布局】

文章目录 【移动端Web开发之响应式布局】前端小抄(20)一、响应式开发1.1 响应式开发原理1.2 响应式布局容器 二、Bootstrap前端开发框架2.1 Bootstrap简介2.2 Bootstrap使用2.3 布局容器 三、Bootstrap栅格系统3.1 栅格系统简介3.2 栅格选项参数3.3 列嵌套3.4 列偏移3.5 列排序…
阅读更多...
H5移动web开发

H5移动web开发

目录 1、H5 的新特性有哪些&#xff1f;C3 的新特性有哪些&#xff1f; 2、如何使一个盒子水平垂直居中&#xff1f; 方法一&#xff1a;利用定位&#xff08;常用方法,推荐&#xff09; 方法二&#xff1a;利用 margin:auto 方法三&#xff1a;利用 display:table-cell 方法四…
阅读更多...
手摸手带你学移动端WEB开发

手摸手带你学移动端WEB开发

HTML常用标签总结手摸手带你学CSSHTML5与CSS3知识点总结 好好学习&#xff0c;天天向上 本文已收录至我的Github仓库DayDayUP&#xff1a;github.com/RobodLee/DayDayUP&#xff0c;欢迎Star ⭐⭐⭐⭐⭐转载请注明出处&#xff01;⭐⭐⭐⭐⭐ 链接&#xff1a;https://blog.c…
阅读更多...
推荐文章

Copyright @ 2022~2023