数据结构——栈和队列的表示与实现详解

目录

1.栈的定义与特点 

2.队列的定义与特点 

3.案例引入 

4.栈的表示和操作的实现 

1.顺序栈的表示 

代码示例：

2.顺序栈的初始化 

代码示例：

3.判断栈是否为空 

代码示例：

4.求顺序栈长度 

代码示例：

5.清空顺序栈 

代码示例：

6.销毁顺序栈 

代码示例：

7.顺序栈的入栈 

代码示例：

8.顺序栈的出栈 

代码示例：

5.链栈的表示和实现 

代码示例：

1.链栈的初始化 

代码示例：

2.判断链栈是否为空 

代码示例：

3.链栈的入栈 

代码示例：

4.链栈的出栈 

代码示例：

5.取栈顶元素 

代码示例：

6.栈与递归 

1.递归问题的求法 

2.递归的定义 

3.递归的优缺点 

7.队列的表示和操作 

1.队列的抽象数据类型定义 

2.队列的顺序表示和实现 

代码示例：

3.解决假上溢的办法——循环队列 

4.循环队列的类型定义 

代码示例：

5.队列的初始化 

代码示例：

6.求队列长度 

代码示例：

7循环队列入队 

代码示例：

8.循环队列出队 

代码示例：

9.取队头元素 

代码示例：

8.链队列

1.链队的类型定义 

代码示例：

2.链队初始化 

代码示例：

3.销毁链队列 

代码示例：

4.将元素e入队 

代码示例：

5.链队列出队 

代码示例：

6.求链队列的队头元素 

代码示例：

9.总的代码

1.栈的定义与特点 

874369c49c014acf9f6f9bad4369ef6c.png

313d5ec227264ce6b2093b4769a97be1.png

86ec6a93b6d94810972bf17404b6d16a.png

ab55bfce66d045ffaad646611229db8d.png

ca36895a430e4655a9d2073fe9ef4dc6.png

1cd453c687fa4a1e8c174afd8110ece4.png

8c4673c2fbe049f288bc7abb89058f51.png

2.队列的定义与特点 

705998c423464a2693638d425f3eebd9.png

03e851423fc74f8095fab42b91387942.png

3.案例引入 

2356252102f8455ca72aaff7e02a3528.png

4e85fee8d8384f3682449e603bc658eb.png

a3477b6d521846b5baa95dae8a0b25fa.png

7c77da222cfb49f4ba589fa8944a89e9.png

8d4a26ea0c2c428b827f299f81d6bf8c.png

15aa876b5e0d4474b13b429cd7194018.png

01d2c5b9d6ab4b6baac21d1cdfe14aa8.png

189901d3c73d447f9a53f1c465a58f46.png

ad586c8cfb944d26af135d7d0edbad73.png

4.栈的表示和操作的实现 

20ec2252eba24e75bc6b4ea05c15b230.png

1d077a5fa9b84b699a43e3ddb335fe2c.png

b0f78a91fe824e2db4db329fa5b99895.png

1b8e35151506471f98efe420d3393089.png

68d0c63c1a2f4035ba9a1053b6be667f.png

8923f58e6f7d49608d66d155e7f4a6a3.png

a5d96e3ad17c4c4e921b6e2e1d1bd80f.png

1.顺序栈的表示 

cedfde1b61c149259e742068b3581df4.png

代码示例：

#define maxsize 100;
typedef struct
{int *base;int *top;int stacksize;
}sqstack;

 

77cd34dee44c469bbcf2ddef46737490.png

2.顺序栈的初始化 

efd3b242780f4aa28129196bf73a4e92.png

代码示例：

int initstack(sqstack &s)
{s.base = new int[100];s.top = s.base;s.stacksize = 100;return 1;
}

3.判断栈是否为空 

f2717311403f4aa7a9b1ff8deba49e13.png

代码示例：

int stackempty(sqstack &s)
{if(s.top == s.base) return true;else return false;
}

4.求顺序栈长度 

0a9a0c8b6d92421ca17e0953646a3e89.png

代码示例：

int stacklength(sqstack &s)
{return s.top - s.base;
}

5.清空顺序栈 

f1bf4873fa0d482ea9b0e828bbb2fdb2.png

代码示例：

int clearstack(sqstack &s)
{if(s.base != NULL) s.top = s.base;return 1;
}

6.销毁顺序栈 

3b404cc107884b39acac57654cbd4c09.png

代码示例：

int destorystack(sqstack &s)
{if(s.base != NULL){delete s.base;s.stacksize = 0;s.base = s.top = NULL;}return 1;
}

7.顺序栈的入栈 

f9e8b2adb3244368a5e0aeec0b229134.png

代码示例：

int push(sqstack &s,int e)
{if(s.top - s.base == s.stacksize)return 0;*s.top = e;s.top++;return 1;
}

8.顺序栈的出栈 

b375fe65d1d8472eb5e4044ffa908ad5.png

代码示例：

int pop(sqstack &s,int &e)
{if(s.top == s.base) return 0;s.top--;e = *s.top;return 1;
}

5.链栈的表示和实现 

31d5d8ccfec84600863598453863006f.png

代码示例：

typedef struct stacknode
{int data;struct stacknode *next;
}stacknode,*linkstack;
linkstack s;

1.链栈的初始化 

bd9fe269c5904e2d938717b2b7689269.png

代码示例：

void initlinkstack(linkstack &s)
{s = NULL;
}

2.判断链栈是否为空 

4ded6a84817a4d688c2f4d5329f5e6e2.png

代码示例：

int stackempty(linkstack s)
{if(s == NULL) return false;else return true;
}

3.链栈的入栈 

2302d1fb3fc042d6b476456c8c5d0368.png

代码示例：

int push(linkstack &s,int e)
{stacknode *p;p = new stacknode;p -> data = e;p -> next = s;s = p;return 1;
}

4.链栈的出栈 

6018b64aa96d43b3a2a97b312d8c5773.png

代码示例：

int pop(linkstack &s,int &e)
{if(s == NULL) return 0;e = s -> data;stacknode *p;p = s;s = s -> next;delete p;return 1;
}

5.取栈顶元素 

3d130ac01bcb4c3583a45d7819eba3b6.png

代码示例：

int gettop(stacknode *s)
{if(s != NULL) return s -> data;
}

6.栈与递归 

8a7b27fc5515481481d97928c0c01f6c.png

4d81056e4fc34888ae9fe6579d1ddc71.png

40f900bbeb854b7da4e79c71de3bba13.png

189d44c42300431985f4861876bc6a09.png

207ffae311164868969efc67fea9d8cd.png

1.递归问题的求法 

271db5da6fdf4e298d3ae4650c836ca5.png

2.递归的定义 

14f3f92deda545cfa0b4ce7b6f884563.png

329669cd8029431e85b0131a1fbf7ce7.png

b072c77b854b424387b251699124b282.png

f78140218ac24fb880d6cafe16fae1ef.png

b8d0ff5de92049fd81e92c1997e119b4.png

56b9b319b8ce48e8aceb772ac927fbf4.png

86fa5f386517491aac69afdb76ae5340.png

3.递归的优缺点 

46d1e9ea2f654d8d94ab777bcd816da2.png

dd111a9e33d94c52b69fe72e89e93bd0.png

48d82c2910904314bf79cbb9e9d50910.png

cd9b120082194947b8ea5038042e9ff6.png

486e4cfbd1ce4a4a916b18902c1bcb7e.png

9188e283cb8641e090ea16242ff801db.png

8611065aa5554c95aa017c5bed39fb49.png

7.队列的表示和操作 

ff68151fc2c045558ac382e9db4194b1.png

651d11520722463e900f9f0b87c631d5.png

67dc1d06a3d64287b8d6b30ee83a2c38.png

a71a5f32fcb64f33a34331d90ab1eb5f.png

1.队列的抽象数据类型定义 

bab86cc1bc2b4fbdb5d8e03210c4f685.png

2.队列的顺序表示和实现 

c5b3de9788c04e31b19033bd35d36b3e.png

代码示例：

#define maxqsize = 100
typedef struct
{int *base;int front;int rear;
}sqqueue;

 

1f0bc88402484f58af5c8571f2108c2d.png

5585b22f3f904d08b782025b09aa86b9.png

3.解决假上溢的办法——循环队列 

fdd83e86f1c74f59b15e024942afffd8.png

dd796b2bace4450d8d24e98c3060db72.png

e79d6071247c4b5892dee7a3b9b5c813.png

b1d4200ed0e244dd99430089bb6c9367.png

320ded398d574e208cd315feb692f60c.png

4.循环队列的类型定义 

07e709266c5443b9a9a4b7158f004402.png

代码示例：

#define maxqsize = 100
typedef struct
{int *base;int front;int rear;
}sqqueue;

5.队列的初始化 

6470440569f14618931c8fe0ac92119d.png

代码示例：

int initqueue(sqqueue &q)
{q.base = new int[100];q.front = q.rear = 0;return 1;
}

6.求队列长度 

18dd178cff3b480a85c0f1a4d9b62cab.png

代码示例：

int queuelength(sqqueue &q)
{return ((q.rear - q.front + maxqsize) % maxqsize);
}

7循环队列入队 

b6fe21e9af5a41bf977509fae30abd35.png

代码示例：

int enqueue(sqqueue &q,int e)
{if((q.rear + 1) % maxqsize == q.front) return 0;q.base[q.rear] = e;q.rear = (q.rear + 1) % maxqsize;return 1;
}

8.循环队列出队 

c31f2b07fe3e467a96593cd72b8b5578.png

代码示例：

int dequeue(sqqueue &q,int &e)
{if(q.front == q.rear) return 0;e = q.base[q.front];q.front = (q.front + 1) % maxqsize;return 1;
}

9.取队头元素 

f1881dc69d964d409bf81f9a49c85c0b.png

代码示例：

int gethead(sqqueue &q)
{if(q.front != q.rear)return q.base[q.front];
}

8.链队列

1.链队的类型定义 

22977415d11e4d5890d4f0bb8a92ade1.png

代码示例：

typedef struct qnode
{int data;struct qnode *next;
}qnode,*queueptr;typedef struct
{queueptr front;queueptr rear;
}linkqueue;

 

6169096bb4774be4924a1027d88802ab.png

2.链队初始化 

51eb86cc622e40d49bfc5aeae02a1963.png

代码示例：

int lnitqueue(linkqueue &q)
{q.front = q.rear = new qnode;q.front -> next = NULL;return 1;
}

3.销毁链队列 

10d31302fe5f4aab8d87e8582cfbf135.png

fceb5c7b88024f35b6ee295f0a03e619.png

代码示例：

int destoryqueue(linkqueue &q)
{while(q.front){queueptr p;p = q.front -> next;delete q.front;q.front = p;}return 1;
}

4.将元素e入队 

b03c7c480b4542f2a5da210c527b2c61.png

代码示例：

int enqueue(linkqueue &q,int e)
{queueptr p;p = new qnode;p -> data = e;p -> next = NULL;q.rear -> next = p;q.rear = p;return 1;
}

5.链队列出队 

54c0d965ac3e431881ba8d5bc613325f.png

b370f9433d38485f8200b538a519158b.png

32bff9d1f35741c8b23e294fbe850fcb.png

代码示例：

int dequeue(linkqueue &q,int &e)
{if(q.front == q.rear) return 0;queueptr p;p = q.front -> next;e = p -> data;q.front -> next = p -> next;if(q.rear == p) q.rear = q.front;delete p;return 1;
}

6.求链队列的队头元素 

5ac2582611254f6592eabb8e197ce530.png

代码示例：

int gethead(linkqueue q,int &e)
{if(q.front == q.rear) return 0;e = q.front -> next -> data;return 1;
}

9.总的代码

#include<bits/stdc++.h>
using namespace std;#define maxsize 100;
typedef struct
{int *base;int *top;int stacksize;
}sqstack;int initstack(sqstack &s)
{s.base = new int[100];s.top = s.base;s.stacksize = 100;return 1;
}int stackempty(sqstack &s)
{if(s.top == s.base) return true;else return false;
}int stacklength(sqstack &s)
{return s.top - s.base;
}int clearstack(sqstack &s)
{if(s.base != NULL) s.top = s.base;return 1;
}int destorystack(sqstack &s)
{if(s.base != NULL){delete s.base;s.stacksize = 0;s.base = s.top = NULL;}return 1;
}int push(sqstack &s,int e)
{if(s.top - s.base == s.stacksize)return 0;*s.top = e;s.top++;return 1;
}int pop(sqstack &s,int &e)
{if(s.top == s.base) return 0;s.top--;e = *s.top;return 1;
}typedef struct stacknode
{int data;struct stacknode *next;
}stacknode,*linkstack;
linkstack s;void initlinkstack(linkstack &s)
{s = NULL;
}int stackempty(linkstack s)
{if(s == NULL) return false;else return true;
}int push(linkstack &s,int e)
{stacknode *p;p = new stacknode;p -> data = e;p -> next = s;s = p;return 1;
}int pop(linkstack &s,int &e)
{if(s == NULL) return 0;e = s -> data;stacknode *p;p = s;s = s -> next;delete p;return 1;
}int gettop(stacknode *s)
{if(s != NULL) return s -> data;
}#define maxqsize = 100
typedef struct
{int *base;int front;int rear;
}sqqueue;int initqueue(sqqueue &q)
{q.base = new int[100];q.front = q.rear = 0;return 1;
}int queuelength(sqqueue &q)
{return ((q.rear - q.front + maxqsize) % maxqsize);
}int enqueue(sqqueue &q,int e)
{if((q.rear + 1) % maxqsize == q.front) return 0;q.base[q.rear] = e;q.rear = (q.rear + 1) % maxqsize;return 1;
}int dequeue(sqqueue &q,int &e)
{if(q.front == q.rear) return 0;e = q.base[q.front];q.front = (q.front + 1) % maxqsize;return 1;
}int gethead(sqqueue &q)
{if(q.front != q.rear)return q.base[q.front];
}typedef struct qnode
{int data;struct qnode *next;
}qnode,*queueptr;typedef struct
{queueptr front;queueptr rear;
}linkqueue;int lnitqueue(linkqueue &q)
{q.front = q.rear = new qnode;q.front -> next = NULL;return 1;
}int destoryqueue(linkqueue &q)
{while(q.front){queueptr p;p = q.front -> next;delete q.front;q.front = p;}return 1;
}int enqueue(linkqueue &q,int e)
{queueptr p;p = new qnode;p -> data = e;p -> next = NULL;q.rear -> next = p;q.rear = p;return 1;
}int dequeue(linkqueue &q,int &e)
{if(q.front == q.rear) return 0;queueptr p;p = q.front -> next;e = p -> data;q.front -> next = p -> next;if(q.rear == p) q.rear = q.front;delete p;return 1;
}int gethead(linkqueue q,int &e)
{if(q.front == q.rear) return 0;e = q.front -> next -> data;return 1;
}int main(){return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://xiahunao.cn/news/2871605.html

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

Spring Boot中application配置文件的生效顺序

Spring Boot中application配置文件的生效顺序

Spring Boot的一个重要特性就是它的自动配置&#xff0c;这一特性在很大程度上依赖于名称为application的配置文件。本文将详细介绍在Spring Boot中&#xff0c;这些配置文件的加载顺序以及每份文件的应用范围。 文章目录 配置文件的种类配置文件的加载顺序配置文件的环境切换 …
阅读更多...
操作系统内功篇:硬件结构之CPU缓存一致性

操作系统内功篇:硬件结构之CPU缓存一致性

一 CPU Cache的数据写入 1.1 CPU Cache的结构 是由很多个Cache Line组成的&#xff0c;CPU Line是CPU从内存读取的基本单位&#xff0c;CPU Line是由多个标志数据块组成。 1.2 CPU Cache数据的写入 数据不仅仅只有读取&#xff0c;还有数据的写入&#xff0c;写入数据也是先…
阅读更多...
【智能算法】斑鬣狗优化算法（SHO)原理及实现

【智能算法】斑鬣狗优化算法（SHO)原理及实现

目录 1.背景2.算法原理2.1算法思想2.2算法过。 3.代码实现4.参考文献 1.背景 2017年&#xff0c;Dhiman等人受到斑鬣狗自然狩猎行为启发&#xff0c;提出了斑鬣狗优化算法(Spotted Hyena Optimizer, SHO)。 2.算法原理 2.1算法思想 SHO将斑鬣狗狩猎行为分为围捕-狩猎-进攻三…
阅读更多...
JVM实战篇

JVM实战篇

内存调优 内存溢出和内存泄漏 内存泄漏&#xff1a;在java中如果不再使用一个对象&#xff0c;但是该对象依然在GC ROOT的引用链上&#xff0c;这个对象就不会被垃圾回收器回收。 内存泄漏绝大多数情况都是由堆内存泄漏引起的&#xff0c;所以后续没有特别说明则讨论的都是堆…
阅读更多...
matplotlib画堆叠、并列直方图

matplotlib画堆叠、并列直方图

在用 matplotlib.pyplot.hist 画分布图时&#xff0c;若总分布由几个分量组成&#xff08;如高斯混合&#xff09;&#xff0c;想用不同颜色标识出来&#xff0c;方便看到各分量占比&#xff0c;参考 [1]。 效果&#xff1a; 分布由两个分量&#xff08;x、y&#xff09;组成…
阅读更多...
二，几何相交---4，BO算法---（4）可能的三种情况

二，几何相交---4，BO算法---（4）可能的三种情况

从上到下&#xff0c;扫描线经过有三种情况&#xff1a; 第一种情况&#xff0c;加入线段e的左端点&#xff0c;那么原来的状态pred->suc变成pred->e->suc 第二种情况&#xff0c;经过线段e的右端点&#xff0c;状态pred->e->suc&#xff0c;变成pred->suc&a…
阅读更多...
Java 面试题之框架

Java 面试题之框架

1. Spring 是什么 Sping 是包含了众多工具方法的 IOC 容器&#xff0c;IOC是控制反转&#xff0c;说的是对象的创建和销毁的权利都交给 Spring 来管理了, 它本身又具备了存储对象和获取对象的能力. 。 容器&#xff1a;字面意思&#xff0c;用来容纳某种物品的装置。 比如 L…
阅读更多...
JavaScript练手小技巧：数字反转时钟

JavaScript练手小技巧：数字反转时钟

样式基于博主的这篇文章&#xff1a; CSS3技巧38&#xff1a;3D 翻转数字效果-CSDN博客 既然可以实现翻转数字了&#xff0c;肯定就可以跟 JS 相结合去完成一些数字展示效果。 比如&#xff0c;数字反转时钟。 为了方便&#xff0c;所有 HTML 数字根据时间动态生成。因此&a…
阅读更多...
企业内部培训考试系统培训计划功能说明

企业内部培训考试系统培训计划功能说明

培训计划是预设好的一套课程系列&#xff0c;包含课程和考试&#xff0c;分多个阶段&#xff0c;每完成一个阶段就会在学习地图上留下标记&#xff0c;让用户看到自己的努力成果&#xff0c;增强成就感&#xff0c;从而坚持完成课程。 企业内部培训考试系统中如何设置培训计划…
阅读更多...
一起玩儿3D打印机——06 Marlin固件的配置（三）

一起玩儿3D打印机——06 Marlin固件的配置（三）

摘要&#xff1a;本文介绍Marlin固件的配置方法 25. 启用EEPROM参数保存功能 #define EEPROM_SETTINGS 打开此功能&#xff0c;会将部分参数保存在打印机中&#xff0c;这样通过屏幕就可以进行调节&#xff0c;而无需重刷固件。 26. 启用板载SD卡支持 #define SDSUPPORT 如…
阅读更多...
【QT+QGIS跨平台编译】之七十七：【QGIS_Gui跨平台编译】—【错误处理：字符串错误】

【QT+QGIS跨平台编译】之七十七：【QGIS_Gui跨平台编译】—【错误处理：字符串错误】

文章目录 一、字符串错误二、处理方法三、涉及到的文件一、字符串错误 常量中有换行符错误：（也有const char * 到 LPCWSTR 转换的错误） 二、处理方法 需要把对应的文档用记事本打开，另存为 “带有BOM的UTF-8” 三、涉及到的文件 src\gui\qgsadvanceddigitizingdockwidge…
阅读更多...
WebServer -- 架构图 面试题(上)

WebServer -- 架构图 面试题(上)

目录 &#x1f382;前言 &#x1f33c;流程图 && 架构图 1&#xff09;什么是 WebServer 2&#xff09;服务器基本框架 3&#xff09;Reactor && Proactor 模式 4&#xff09;同步 I/O 模拟Proactor模式&#xff08;Linux&#xff09; 5&#xff09;主从…
阅读更多...
C语言基础练习——Day10

C语言基础练习——Day10

目录 选择题 编程题 不用加减乘除做加法 找到所有数组中消失的数字 选择题 1、求函数返回值&#xff0c;传入-1&#xff0c;则在64位机器上函数返回 int func(int x) {int count 0;while (x){count;x x&(x - 1);//与运算}return count; } A 死循环B 64C 32D 16 答案&…
阅读更多...
别急，先了解一下什么是REST API吧

别急，先了解一下什么是REST API吧

1、先想一想Rest API的用途和场景 Rest API的常用场景&#xff1a;前后端分离&#xff0c;前端可多样化&#xff0c;还有与其他系统集成&#xff1a;RESTful API 可以与其他系统进行集成&#xff0c;例如第三方登录、支付和社交媒体平台等。 现在我们知道了如何使用 servlet …
阅读更多...
redis 常见的异常

redis 常见的异常

目录 一、缓存穿透 1、概念 解决方案 &#xff08;1&#xff09;布隆过滤器 (2)、缓存空对象 二、缓存雪崩 1、概念 解决方案 &#xff08;1&#xff09;redis高可用 &#xff08;2&#xff09;限流降级 &#xff08;3&#xff09;数据预热 一、缓存穿透 1、概念 缓…
阅读更多...
仰卧起坐计数，YOLOV8POSE

仰卧起坐计数，YOLOV8POSE

仰卧起坐计数&#xff0c;YOLOV8POSE 通过计算膝盖、腰部、肩部的夹角&#xff0c;计算仰卧起坐的次数
阅读更多...
分数相加减（C语言）

分数相加减（C语言）

一、流程图&#xff1b; 二、源代码&#xff1b; # define _CRT_SECURE_NO_WARNINGS # include <stdio.h>int main() {//初始化变量值&#xff1b;int fenmu 2;int result 1;int fuhao 1;//执行循环&#xff1b;while (fenmu < 100){//运算&#xff1b;fuhao (-1…
阅读更多...
汽车电子与软件架构概述

汽车电子与软件架构概述

汽车电子与软件架构概述 我是穿拖鞋的汉子，魔都中坚持长期主义的汽车电子工程师 （Wechat：gongkenan2013）。 老规矩，分享一段喜欢的文字，避免自己成为高知识低文化的工程师： 本就是小人物，输了就是输了，不要在意别人怎么看自己。江湖一碗茶，喝完再挣扎，出门靠自己…
阅读更多...
Sentinel篇：线程隔离和熔断降级

Sentinel篇：线程隔离和熔断降级

书接上回&#xff1a;微服务&#xff1a;Sentinel篇 3. 隔离和降级 限流是一种预防措施&#xff0c;虽然限流可以尽量避免因高并发而引起的服务故障&#xff0c;但服务还会因为其它原因而故障。 而要将这些故障控制在一定范围&#xff0c;避免雪崩&#xff0c;就要靠线程隔离…
阅读更多...
MySQL数据库实现增删改查基础操作

MySQL数据库实现增删改查基础操作

准备工作 安装mysql8.0 (安装时一定要记住用户名和密码)安装数据库可视化视图工具Navicat 请注意⚠️⚠️⚠️⚠️ a. 编程类所有软件不要安装在中文目录下 b. Navicat破解版下载安装教程&#xff1a;&#xff08;由于文章审核提示版权问题&#xff0c;链接不方便给出&#xff…
阅读更多...
最新文章

Copyright @ 2022~2023