网站搭建说明小程序开发定制公司北京

12 栈、队列、二叉树

目录

12 栈、队列、二叉树

一、栈、队列、二叉树是什么？

二、栈

1. 特点：先进后出 -- 有底的盒子

2. 使用场景：函数调用 -- 中断机制

3. 实现栈的形式：

三、队列

1. 特点：先进先出 -- 水管

2. 使用场景：消息队列（MQTT）

3. 实现队列的形式：

四、二叉树 -- 了解

1. 树形结构 -- 链式结构 -- 族谱

2. 使用场景：文件系统

---

一、栈、队列、二叉树是什么？

        -- 数据的一种存储结构         -- 保存数据

二、栈

1. 特点：先进后出         -- 有底的盒子

2. 使用场景：函数调用         -- 中断机制

3. 实现栈的形式：

（1）线性栈：数组

（2）链式栈：

        -- 链表的头插法         --因为链表是从头开始遍历的。

#include "stdio.h"
#include "string.h"
#include "stdlib.h"struct stack
{int data[5];  //栈存储空间int *ptemp;     //栈指针int *pstart;    //栈底int *pend;    //栈顶};struct stack * init_stack();
void push_stack(struct stack *p);
void pup_stack(struct stack *p);int main(int argc, char const *argv[])
{struct stack *p = init_stack();while (1){printf("*******栈操作********\n");printf("1.入栈 2.出栈 3.退出\n");printf("**********************\n");printf("请选择:");int n = 0;scanf("%d", &n);switch (n){case 1:printf("--->入栈\n");push_stack(p);break;case 2:printf("--->出栈\n");pup_stack(p);break;case 3:printf("--->退出\n");return 0;default:printf("输入错误，请重新输入!\n");break;}}return 0;
}struct stack * init_stack() //初始化栈
{//开辟栈空间struct stack *p = (struct stack *)malloc(sizeof(struct stack));//初始化//栈的存储空间memset(p->data,0,sizeof(p->data));//栈底p->pstart = p->data; //数组的首地址//栈顶p->pend = p->data + sizeof(p->data) / sizeof(p->data[0])-1;//首地址+偏移量（长度-1）//栈指针p->ptemp = p->pstart;return p;
}void push_stack(struct stack *p)
{//判断是否栈满if(p->ptemp == p->pend+1)   //因为栈指针指向下一个可以存储的空间{printf("栈已满，请联系管理员!\n");return;}printf("请输入您要保存的数据：");scanf("%d",p->ptemp);   //数据保存在栈指针指向的位置//栈指针指向下一个可以存储数据的空间p->ptemp++;printf("入栈成功!\n");
}void pup_stack(struct stack *p)
{//判断是否栈空if(p->ptemp == p->pstart){printf("栈空，请先入栈数据!\n");return;}//栈指针回到有数据的空间p->ptemp --;int num = *p->ptemp;printf("您出栈的数据是:%d\n",num);}

三、队列

1. 特点：先进先出 -- 水管

2. 使用场景：消息队列（MQTT）

3. 实现队列的形式：

（1）线性队列：数组

（2）链式队列：

                -- 链表的尾插法

#include "stdio.h"
#include "stdlib.h"
#include "string.h"struct queue
{int data[5];  // 队存储空间int *pstart;  // 队底int *pend;    // 队顶int *pin;   // 入队指针int *pout;  // 出队指针int count;  // 计数器    因为入队和出队是循环的，无法判断栈满，栈空int total; //入队总数
};struct queue * init_queue();
void push_queue(struct queue *p);
void pup_queue(struct queue *p);int main(int argc, char const *argv[])
{struct queue *p=init_queue();while (1){printf("*******队操作********\n");printf("1.入队 2.出队 3.退出\n");printf("**********************\n");printf("请选择:");int n = 0;scanf("%d", &n);switch (n){case 1:printf("--->入队\n");push_queue(p);break;case 2:printf("--->出队\n");pup_queue(p);break;case 3:printf("--->退出\n");return 0;default:printf("输入错误，请重新输入!\n");return 0;}}return 0;
}struct queue * init_queue()
{//开辟队空间struct queue *p = (struct queue *)malloc(sizeof(struct queue));//初始化//队的存储空间memset(p->data,0,sizeof(p->data));//队底p->pstart = p->data;//队顶p->pend = p->data + sizeof(p->data) / sizeof(p->data[0])-1;//入队指针p->pin = p->pstart;//出队指针 p->pout = p->pstart;//计数器p->count = 0;//入队总数p->total = sizeof(p->data) / sizeof(p->data[0]);return p;
}void push_queue(struct queue *p)
{//判断是否队满if(p->count == p->total){printf("队已满，请联系管理员!\n");return;}printf("请输入您要保存的数据：");scanf("%d",p->pin);//队指针指向下一个可以存储数据的空间p->pin++;//计数器累加p->count ++;//循环入队if(p->pin == p->pend+1) //开始循环{p->pin = p->pstart;}printf("入队成功!\n");
}void pup_queue(struct queue *p)
{//判断是都队空if(p->count == 0){printf("队空，请先入队数据!\n");return;}//出队int num = *p->pout;//出队指针指向下一个可以出队的空间p->pout ++;//计数器累减p->count--;//循环出队if(p->pout == p->pend+1){p->pout = p->pstart;}printf("您出队的数据是:%d\n",num);
}

四、二叉树 -- 了解

1. 树形结构 -- 链式结构 -- 族谱

2. 使用场景：文件系统

树https://blog.csdn.net/m0_71813740/article/details/141090117?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22141090117%22%2C%22source%22%3A%22m0_71813740%22%7D