当前位置： 首页 > news >正文

C语言基础——⑩③数据结构——②栈和队列

news 来源：原创 2024/9/18 11:09:03

一、栈(Stack)

1、基本概念

栈是一种逻辑结构，是特殊的线性表。特殊在：

  • 只能在固定的一端操作

只要满足上述条件，那么这种特殊的线性表就会呈现一种“后进先出”的逻辑，这种逻辑就被称为栈。栈 在生活中到处可见，比如堆叠的盘子、电梯中的人们、嵌套函数的参数等等。

由于约定了只能在线性表固定的一端进行操作，于是给栈这种特殊的线性表的“插入”、“删除”，另起了 下面这些特定的名称：

  • 栈顶：可以进行插入删除的一端；
  • 栈底：栈顶的对端；
  • 入栈：将节点插入栈顶之上，也称为压栈，函数名通常为push()；
  • 出栈：将节点从栈顶剔除，也称为弹栈，函数名通常为pop()；
  • 取栈顶：取得栈顶元素，但不出栈，函数名通常为top()

基于这种固定一端操作的简单约定，栈获得了“后进先出”的基本特性，如下图所示，最后一个放入的元素，最先被拿出来：

2、存储形式

栈只是一种数据逻辑，如何将数据存储于内存则是另一回事。一般而言，可以采用顺序存储形成顺序栈，或采用链式存储形成链式栈。

1.顺序栈（sequenceStack）

顺序存储意味着开辟一块连续的内存来存储数据节点，一般而言，管理栈数据除了需要一块连续的 内存之外，还需要记录栈的总容量、当前栈的元素个数、当前栈顶元素位置，如果有多线程还需要 配互斥锁和信号量等信息，为了便于管理，通常将这些信息统一于在一个管理结构体之中：

// 顺序栈节点
struct seqStack
{datatype *data; // 顺序栈入口int size;       // 顺序栈总容量int top;        // 顺序栈栈顶元素下标
};

2.链式栈(linkStack)

链式栈的组织形式与链表无异，只不过插入删除被约束在固定的一端。为了便于操作，通常也会创 建所谓管理结构体，用来存储栈顶指针、栈元素个数等信息：

// 链式栈节点
typedef struct node
{datatype data;struct node *next;
}node;
// 链式栈管理结构体
struct linkStack
{node *top; // 链式栈栈顶指针int  size; // 链式栈当前元素个数
};

3、完整代码

  • 顺序栈(sequenceStack)

  1. sstack.h
    #ifndef __SSTACK_H
#define __SSTACK_H
// 数据类型
typedef int DATA;
// 顺序栈结构体
typedef  struct
{DATA      *pData; // 栈中元素的地址int         size; // 栈的总容量int         top;  // 栈顶元素下标
}SeqStack;
// 初始化栈
int SStack_init(SeqStack *s, int num);
// 判断栈是否已满
int SStack_isfull(SeqStack *st);
// 判断栈是否为空
int SStack_isempty(SeqStack *st);
// 入栈/压栈
int SStack_push(SeqStack *st,DATA data);
// 出栈/弹栈
int SStack_pop(SeqStack *st,DATA *data);
// 回收栈
int SStack_free(SeqStack *st);
#endif
  2. sstack.c
    #include <stdlib.h>
#include "sstack.h"
// 初始化栈
int SStack_init(SeqStack* s,int num)
{s -> pData = (DATA*)calloc(sizeof(DATA),num);if(s -> pData == NULL)return -1;s -> size  = num ;s -> top   = -1;return 0;
}
// 判断栈是否已满
int SStack_isfull(SeqStack *st)
{return st -> top + 1 == st -> size;
}
// 判断栈是否为空
int SStack_isempty(SeqStack *st)
{return st -> top == -1;
}
// 压栈/入栈
int SStack_push(SeqStack *st,DATA data)
{if(SStack_isfull(st))return -1;st -> top++;st -> pData[st -> top] = data;return 0;
}
// 出栈/弹栈
int SStack_pop(SeqStack *st,DATA *data)
{if(SStack_isempty(st))return -1;*data = st -> pData[st -> top];st -> top--;return 0;
}
// 回收栈
int SStack_free(SeqStack *st)
{if(st -> pData){free(st->pData);st -> pData = NULL;}st -> top = -1;  
}
  3. sstack_main.c
    #include "sstack.h"
#include <stdio.h>
int main(void)
{SeqStack  st;SStack_init(&st,10);register int i = 1;for(; i <=10; i++)SStack_push(&st,i);if(-1 == SStack_push(&st,1024))fprintf(stderr,"满栈,插入失败\n");while(!SStack_isempty(&st)){DATA   data = 0;SStack_pop(&st,&data);printf("%4d",data);         }printf("\n");SStack_free(&st);return 0;  
}

【课堂练习1】

使用顺序栈，接收键盘的输入，实现如下功能：

1. 输入数字时，依次入栈。

2. 输入字母时，依次出栈。

3. 每次入栈或者出栈，都将顺序栈中的各个元素输出出来。

  • 完整代码（链式栈(linkStack)）

  1. linkstack.h
    #ifndef __LINKSTACK_H
#define __LINKSTACK_H
// 数据类型
typedef   int   DATA;
// 链式栈节点
typedef   struct  _node
{DATA       data; // 数据struct _node *next; // 指向下一个栈的节点
}NODE;
// 链式栈管理结构体
typedef  struct
{NODE     *pHead;// 链式栈栈顶指针int       size; // 链式栈当前元素个数int       num;
}LinkStack;
// 初始化链式栈
int LStack_init(LinkStack *s, int num);
// 判断栈是否已满
int LStack_isfull(LinkStack *st);
// 判断栈是否为空
int LStack_isempty(LinkStack *st);
// 压栈/入栈
int LStack_push(LinkStack *st,DATA data);
// 弹栈/出栈
int LStack_pop(LinkStack *st,DATA *data);
// 回收栈
int LStack_free(LinkStack *st);
#endif
  2. linkstack.c
    #include "linkstack.h"
#include <stdio.h>
#include <stdlib.h>
// 初始化栈
int LStack_init(LinkStack *st, int num)
{st -> pHead = NULL;st -> size  = num;st -> num   = 0;return 0 ;
}
// 判断栈是否已满
int LStack_isfull(LinkStack *st)
{return st -> num == st -> size;
}
// 判断栈是否为空
int LStack_isempty(LinkStack *st)
{return st -> num == 0;
}
// 入栈
int LStack_push(LinkStack *st,DATA data)
{if(LStack_isfull(st))return -1;NODE* p = (NODE*)malloc(sizeof(NODE));if(!p)return -1;p -> data   = data;p -> next   = st -> pHead;st -> pHead = p;(st -> num)++;return 0;
}
// 出栈
int LStack_pop(LinkStack *st,DATA *data)
{if(LStack_isempty(st))return -1;NODE* p = st -> pHead;if(!p)return -1;*data = p -> data;st -> pHead = p -> next;free(p);(st -> num)--;return 0;
}
// 回收栈
int LStack_free(LinkStack *st)
{NODE* p = st -> pHead, *q = NULL;while(p){q  = p;p  = p -> next;free(q);       }st -> pHead = NULL;st -> num   = 0;return 0;
}
  3. linkstack_main.c
    #include "linkstack.h"
#include <stdio.h>
int main(void)
{LinkStack  st;LStack_init(&st,10);register int i = 1;for(; i <= 10; i++)LStack_push(&st,i);if(-1 == LStack_push(&st,1024))fprintf(stderr,"满栈,插入失败\n");while(!LStack_isempty(&st)){DATA   data = 0;LStack_pop(&st,&data);printf("%4d",data);         }printf("\n");LStack_free(&st);return 0;  
}

【课堂练习2】

使用链式栈，实现十进制转八进制：键盘输入一个十进制数，经过链式栈的相关算法，输出八进制 数。

代码：

二、队列(queue)

1、基本概念

队列是一种逻辑结构，是一种 特殊的线性表。特殊在： 只能在固定的两端操作线性表 只要满足上述条件，那么这种特殊的线性表就会呈现一种“先进先出”的逻辑，这种逻辑就被称为队列。

队列本质上，是从一端进，另一端出，为了保证跟生活的认知一致，我们建议把进的一端叫做队尾，出的一端叫做对头。

由于约定了只能在线性表固定的两端进行操作，于是给队列这种特殊的线性表的插入删除，起个特殊的名称：

  • 队头：可以删除节点的一端；
  • 队尾：可以插入节点的一端；
  • 入队：将节点插入到队尾之后，函数名通常为enQueue()；
  • 出队：将队头节点从队列中剔除，函数名通常为outQueue()；
  • 取队头：取得队头元素，但不出队，函数名通常为front()。

由于这种固定两端操作的简单约定，队列获得了“先进先出”的基本特性，如下图所示：

2、顺序存储的队列：循环队列(sequenceQueue)

与其他的逻辑结构类似，队列可以采用顺序存储形成循环队列，也可以采用链式存储形成链式队列。 顺序存储的队列之所以被称为循环队列，是因为可以利用更新队头队尾的下标信息，来循环地利用整个数组，出队入队时也不必移动当中的数据。循环队列示意图如下所示：

从上述动图中可以观察到，需要牺牲至少数组中的一个存储位置，来区分循环队列中的满队和空队。 满队和空队的约定如下：

  • 当front与rear相等时，队列为空；
  • 当rear循环加一与front相等时，队列为满；

与其他数据结构一样，管理循环队列除了需要一块连续的内存之外，还需要记录队列的总容量、当前 队列的元素个数、当前队头、队尾元素位置，如果有多线程还需要配互斥锁和信号量等信息，为了便于管理，通常将这些信息统一于在一个管理结构体之中：

typedef   int   DATA;
typedef  struct
{DATA      *pData; // 队列入口int         size;   // 队列总容量int         head;   // 队列队头元素下标int         tail;   // 队列队尾元素下标
}SQueue;

3、完整代码（顺序-循环队列）

  • squeue.h

    #ifndef __SQUEUE_H
#define __SQUEUE_H
typedef   int   DATA;
typedef  struct
{DATA      *pData; // 队列入口int         size;   // 队列总容量int         head;   // 队列队头元素下标int         tail;   // 队列队尾元素下标
}SQueue;
// 初始化队列
int SQ_init(SQueue *q, int num);
// 判断队列是否已满
int SQ_isfull(SQueue *q);
// 判断队列是否为空
int SQ_isempty(SQueue *q);
// 入队
int SQ_push(SQueue *q,DATA data);
// 出队
int SQ_pop(SQueue *q,DATA *data);
// 回收队
int SQ_free(SQueue *q);
#endif

  • squeue.c

    #include <stdlib.h>
#include "squeue.h"
// 初始化队列
int SQ_init(SQueue* q,int num)
{q -> pData = (DATA*)calloc(sizeof(DATA),num);if(q -> pData == NULL)return -1;q -> size  = num ;q -> head  = q -> tail = 0;return 0;
}
// 判断队列是否已满
int SQ_isfull(SQueue *q)
{return (q -> tail + 1) % q -> size  == q -> head;
}
// 判断队列是否为空
int SQ_isempty(SQueue *q)
{return q -> tail  == q -> head;
}
// 出队
int SQ_push(SQueue *st,DATA data)
{if(SQ_isfull(st))return -1;st -> pData[st -> tail] = data;st -> tail = (st -> tail+1) % st -> size;return 0;
}
// 入队
int SQ_pop(SQueue *st,DATA *data)
{if(SQ_isempty(st))return -1;*data = st -> pData[st -> head];st -> head = (st -> head+1) % st -> size;return 0;
}
// 回收队列
int SQ_free(SQueue *st)
{if(st -> pData){free(st->pData);st -> pData = NULL;}st -> head = st -> tail  = 0;  
}

注意： 循环队列中，需要牺牲一个存储位置来区分空队和满队

【课堂练习3】

构建一个顺序存储的循环队列，当用户输入数字时，将数字入队，当用户输入字母时，将队头元素出队。每次操作队列之后，将队列中的元素显示出来。

4、链式存储的队列：链式队列(linkQueue)

链式队列的组织形式与链表无异，只不过插入删除被约束在固定的两端。为了便于操作，通常也会创建所谓管理结构体，用来存储队头指针、队尾指针、队列元素个数等信息：

从上图可以看到，链式队列主要控制队头和队尾，由于管理结构体中保存了当前队列元素个数size，因 此可以不必设计链表的头节点，初始化空队列时只需要让队头队尾指针同时指向空即可。

以下是队列链表节点设计和管理结构体设计的示例代码：

typedef  int  DATA;
// 链式队列节点
typedef struct _node
{DATA        data;struct _node  *next;
}NODE/*,*PNODE*/;// 链式队列管理结构体
typedef struct
{NODE     *pHead; // 队头指针NODE     *pTail; // 队尾指针int       size ; // 队列当前元素个数int       num ;
}LinkQueue;

5、完整代码（链式队列(linkQueue)）

当进入新数据时，创建新节点

  • linkQueue.h

    #ifndef __LINKQUEUE_H
#define __LINKQUEUE_H
typedef  int  DATA;
// 链式队列节点
typedef struct _node
{DATA        data;struct _node  *next;
}NODE/*,*PNODE*/;
// 链式队列管理结构体
typedef struct
{NODE     *pHead; // 队头指针NODE     *pTail; // 队尾指针int       size ; // 队列当前元素个数int       num ;
}LinkQueue;
void LQ_init(LinkQueue *q,int sz);
int  LQ_isfull(LinkQueue *q);
int  LQ_isempty(LinkQueue *q);
int  LQ_push(LinkQueue *q,DATA data);
int  LQ_pop(LinkQueue *q,DATA *data);
int LQ_free(LinkQueue *q);
#endif

  • linkQueue.c

    #include "LinkQueue.h"
#include <stdlib.h>
void LQ_init(LinkQueue *q,int sz)
{q -> pHead = q -> pTail = NULL;q -> size  = sz;q -> num   = 0;
}
int  LQ_isfull(LinkQueue *q)
{return q -> num == q -> size;
}
int  LQ_isempty(LinkQueue *q)
{return q -> num == 0;
}
int  LQ_push(LinkQueue *q,DATA data)
{if(LQ_isfull(q))return -1;NODE* pNew = (NODE*)malloc(sizeof(NODE));if(!pNew)return -1;pNew -> data  = data;pNew -> next  = NULL;if(!(q -> pTail))q -> pHead = q -> pTail = pNew;else{       q -> pTail -> next  = pNew;q -> pTail = pNew;}q -> num ++;return 0;
}
int  LQ_pop(LinkQueue *q,DATA *data)
{if(LQ_isempty(q))return -1;NODE* p = q -> pHead;*data  = p -> data;if(p == q -> pTail)q -> pHead = q -> pTail = NULL;else     q -> pHead = p -> next;free(p);q -> num --;return 0;
}
int LQ_free(LinkQueue *queue)
{NODE* p = queue -> pHead, *q = NULL;while(p){q  = p;p  = p -> next;free(q);}queue -> pHead = queue -> pTail = NULL;queue -> num   = 0;return 0;
}

  • linkQueue_main.c

    #include "LinkQueue.h"
#include <stdio.h>
int main(void)
{LinkQueue    queue;LQ_init(&queue,10);register  int i = 1;    for(; i <= 10 ; i++) LQ_push(&queue, i);if( -1 == LQ_push(&queue,1024))fprintf(stderr,"满队,入队失败!\n");while(!LQ_isempty(&queue)){DATA   data;LQ_pop(&queue,&data);printf("%4d",data);}printf("\n");LQ_free(&queue);return 0; 
}

【课堂练习4】

构建一个链式队列，当用户输入数字时，将数字入队，当用户输入字母时，将队头元素出队。每次操作队列之后，将队列中的元素显示出来。

章节作业

（栈的基本操作）

【1】编程实现功能：将键盘输入的十进制数，转换为十六进制输出。

（栈的基本操作）（选做）

【2】编程实现汉诺塔游戏。

（栈的基本操作）（选做）

【3】面试题

（队列的基本操作）（选做）

【4】蜗牛在制定今天的旅游计划，有 nn 个景点可选，它已经把这些景点按照顺路游览的顺序排成一排了，每个地方有相应的景观标号，这里用一个整数表示，相同的标号意味着相同的景观。 蜗牛希望选取连续的一段景点，还要选出来的每一个景点的景观都不同，问它最多能选出多少个景点进行旅游。

提示：

假设景点的景观标号是： 6 2 8 2 6

那么蜗牛可选的最长不重复的连续景点数是3，即前三个6 2 8，或后三个8 2 6

v图像 小部件

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • （不用互三）AI绘画工具应该如何选择
  • C语言 | Leetcode C语言题解之第394题字符串解码
  • Spring Framework 学习总结博客
  • 快速入门编写一个Java程序
  • 【mysql】mysql之主从部署以及介绍
  • 无头服务（Headless Service）
  • gen_server补充基础学习
  • linux cmake版本升级教程（Centos7）
  • Vue3：el-table实现日期的格式化
  • 使用python绘制森林图的教程
  • 如何制作Vector Vflash中加载的DLL文件--自动解锁刷写过程中27服务
  • C++类与对象（下）--最后的收尾
  • jmeter依赖jar包找不到类路径
  • SQL入门题
  • 【IPV6从入门到起飞】5-3 IPV6+Home Assistant(ESP32+MQTT+GPIO)远程控制灯
  • Android框架之Volley
  • Java精华积累：初学者都应该搞懂的问题
  • Java深入 - 深入理解Java集合
  • JS基础之数据类型、对象、原型、原型链、继承
  • js学习笔记
  • Netty 4.1 源代码学习：线程模型
  • Python 反序列化安全问题（二）
  • Vue组件定义
  • 仿天猫超市收藏抛物线动画工具库
  • 分类模型——Logistics Regression
  • 聊聊redis的数据结构的应用
  • 目录与文件属性：编写ls
  • 鱼骨图 - 如何绘制？
  • shell使用lftp连接ftp和sftp,并可以指定私钥
  • ​ 无限可能性的探索：Amazon Lightsail轻量应用服务器引领数字化时代创新发展
  • ​Base64转换成图片,android studio build乱码,找不到okio.ByteString接腾讯人脸识别
  • ​Distil-Whisper：比Whisper快6倍，体积小50%的语音识别模型
  • ​ssh免密码登录设置及问题总结
  • ​无人机石油管道巡检方案新亮点：灵活准确又高效
  • （2）从源码角度聊聊Jetpack Navigator的工作流程
  • （27）4.8 习题课
  • (阿里云万网)-域名注册购买实名流程
  • (微服务实战)预付卡平台支付交易系统卡充值业务流程设计
  • (原創) 如何安裝Linux版本的Quartus II? (SOC) (Quartus II) (Linux) (RedHat) (VirtualBox)
  • .mat 文件的加载与创建 矩阵变图像？ ∈ Matlab 使用笔记
  • .net 4.0 A potentially dangerous Request.Form value was detected from the client 的解决方案
  • .net 7和core版 SignalR
  • .Net Core 笔试1
  • .Net Core中的内存缓存实现——Redis及MemoryCache（2个可选）方案的实现
  • .NET Framework 3.5中序列化成JSON数据及JSON数据的反序列化，以及jQuery的调用JSON
  • .Net 路由处理厉害了
  • .net 生成二级域名
  • .NET 自定义中间件 判断是否存在 AllowAnonymousAttribute 特性 来判断是否需要身份验证
  • .NET关于 跳过SSL中遇到的问题
  • .NET技术成长路线架构图
  • .Net通用分页类(存储过程分页版,可以选择页码的显示样式,且有中英选择)
  • .NET微信公众号开发-2.0创建自定义菜单
  • .NET中使用Redis (二)
  • .project文件
  • .sh