数据结构与算法——栈和队列＜也不过如此＞

2023-04-26 99

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 📖作者介绍：22级树莓人（计算机专业），热爱编程＜目前在c＋＋阶段，因为最近参加新星计划算法赛道(白佬)，所以加快了脚步，果然急迫感会增加动力>——目标Windows，MySQL，Qt，数据结构与算法，Linux，多线程，会持续分享学习成果和小项目的📖作者主页：king&南星📖专栏链接：数据结构🎉欢迎各位→点赞👏 + 收藏💞 + 留言🔔💬总结：希望你看完之后，能对你有所帮助，不足请指正！共同学习交流 🐾————————————————版权声明：本文为CSDN博主「热爱编程的小K」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。

🏅文章目录

一、🥇栈

1、🥈概念理解

2、🥈链表头插头删实现栈

1、🥉预备准备

2、🥉创建结点函数

3、🥉遍历函数

4、🥉头插

5、🥉头删

3、🥈链表尾插尾删实现栈

二、🥇队列

1、🥈概念理解

2、🥈数组头插尾删实现队列

1、🥉预备准备

2、🥉初始化

3、🥉头插函数

4、🥉浏览数据

5、🥉删除数据

3、🥈数组尾插头删实现队列

一、🥇栈

在讲解之前我先和大家说说栈有哪些好玩应用：比方说水桶，还有我们常用的撤销，粘贴板，大家学完这个可以用栈简单的实现一下四则运算😀

1、🥈概念理解

1、定义：栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

2、核心：

栈：先入后出，后入先出 First In Last Out FILO

先存进去的，最后才能拿出来

最后存进去的，一开始就能拿出来

3、图解：

2、🥈链表头插头删实现栈

1、🥉预备准备

先把头文件和函数声明写好

#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>

#include<stdlib.h>

#include<stdbool.h>

#include<assert.h>

typedef struct Node

{

int data;

struct Node* next;

}Node;

#define SIZE sizeof(Node)

//创建新节点

Node* createNode(int newData);

//浏览

void watchData(Node* head);

//头插

void push_front(Node** head, int insertData);

//头删

void pop_front(Node** head);

2、🥉创建结点函数

注意：要判断空间是否申请成功

Node* createNode(int newData)

{

//1 申请内存

Node* newNode = (Node*)malloc(SIZE);

assert(newNode);

//2 数据赋值

newNode->data = newData;

newNode->next = NULL;

//3 返回

return newNode;

}

3、🥉遍历函数

版权void watchData(Node* head)

{

printf("List:");

while (head)

{

printf("%d ", head->data);

//切换到下一个节点

head = head->next;

}

printf("\n");

}

4、🥉头插

注意：

1.防止传入的是空结点

2.要传入二级指针，因为要改变头结点

void push_front(Node** head, int insertData)

{

//1 防呆

if (NULL == head) return;

Node* pNode = createNode(insertData);

//2 新节点的next指针指向原来的第一个结点

pNode->next = *head;

//3 新节点成为第一个节点

*head = pNode;

}

5、🥉头删

要注意释放删除的结点和临时指针最后的指向

void pop_front(Node** head)

{

if (NULL == head || NULL == *head) return;

Node* pNode = *head;

//第二个节点成为头结点

*head = pNode->next;

//释放头结点

free(pNode);

pNode = NULL;

return;

}

3、🥈链表尾插尾删实现栈

一样的思路，这里我就不和大家啰嗦了，大家主要要记住栈的特点：先进后出，后进先出就可以了，代码我放下面了，感兴趣的可以看看哦！！！

#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>

#include<stdlib.h>

#include<stdbool.h>

#include<assert.h>

typedef struct Node

{

int data;

struct Node* next;

}Node;

#define SIZE sizeof(Node)

//创建新节点

Node* createNode(int newData);

//浏览

void watchData(Node* head);

//尾插

void push_back(Node** head, int insertData);

//尾删

void pop_back(Node** head);

int main()

{

Node* List = NULL; //创建链表

push_back(&List, 999);

watchData(List);

push_back(&List, 888);

watchData(List);

pop_back(&List);

watchData(List);

for (int i = 0; i < 10; i++)

{

push_back(&List, i);

}

watchData(List);

pop_back(&List);

watchData(List);

pop_back(&List);

watchData(List);

pop_back(&List);

watchData(List);

pop_back(&List);

watchData(List);

pop_back(&List);

watchData(List);

return 0;

}

Node* createNode(int newData)

{

//1 申请内存

Node* newNode = (Node*)malloc(SIZE);

assert(newNode);

//2 数据赋值

newNode->data = newData;

newNode->next = NULL;

//3 返回

return newNode;

}

void watchData(Node* head)

{

printf("List:");

while (head)

{

printf("%d ", head->data);

//切换到下一个节点

head = head->next;

}

printf("\n");

}

void push_back(Node** head, int insertData)

{

//1 防呆

if (NULL == head) return;

Node* pNode = *head;

Node* newNode = createNode(insertData);

if (*head)//*head为真，非空链表

{

//找到最后一个

while (pNode->next) pNode = pNode->next;

pNode->next = newNode;

}

else //空链表

{

*head = newNode;

}

void pop_back(Node** head)

{

if (NULL == head) return;

Node* pNode = *head;

Node* pLiftNode = *head;

if ( NULL == pNode->next ) //只有一个节点

{

//第二个成为新的头结点

(*head) = (*head)->next;

//释放节点

free(pNode);

pNode = NULL;

return;

}

//找到最后一个和倒数第二个节点

while (1)

{

pNode = pNode->next;

if (NULL == pNode->next) break;

pLiftNode = pNode;

}

//倒数第二个节点指向空

pLiftNode->next = pNode->next;

free(pNode);

pLiftNode = pNode = NULL;

}

二、🥇队列

1、🥈概念理解

1、定义：队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头

2、核心：

队列：先入先出，后入后出 First In First Out FIFO

做核酸排队

食堂打饭排队

看电影排队

3、图解：

2、🥈数组头插尾删实现队列

1、🥉预备准备

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<assert.h>

typedef struct student

{

char name[20];

int age;

double score;

}stu;

int curSize; //记录当前元素个数

int capacity; //记录当前容量

stu* pArr; //指向当前内存段的首地址

//初始化

void initData();

//insertData

void push(stu* inserData);

//浏览数据

void watchData();

//删除数据

void pop(stu* delData);

2、🥉初始化

把当前元素个数和当前容量都赋值为0，把结构体指针爷指向空

//初始化

void initData()

{

curSize = 0;

capacity = 0;

pArr = NULL;

}

3、🥉头插函数

这里用了很多的高端写法(比较刁钻）,大家要看明白函数要熟悉位操作和内存函数的应用

1、右移一位就相当于除以2

2、memcpy内存复制函数，第一个参数是目的地，第二个参数是要复制的地方，第三个参数是大小

3、memmove内存移动函数，第一个参数是目的地，第二个参数是要移动的地方，第三参数是大小

void push(stu* inserData)

{

//需要开内存

if (capacity <= curSize)

{

//计算新开内存

capacity += (capacity >> 1 > 1) ? (capacity >> 1) : 1;

stu* pNew = (stu*)malloc(sizeof(stu) * capacity);//新开内存

assert(pNew); //防御性编程

if (pArr)

{

memcpy(pNew+1, pArr , sizeof(stu) * curSize);

//释放原有内存段

free(pArr);

}

//pArr指向新开内存段

pArr = pNew;

}

else

{

memmove(pArr + 1, pArr, sizeof(stu) * curSize);

}

//inserData放入数组中

#if 0

memcpy(pArr, inserData, sizeof(stu));//pArr缓冲区溢出

#else

strcpy(pArr[0].name, inserData->name);

pArr[0].age = inserData->age;

pArr[0].score = inserData->score;

#endif

//元素个数加一

curSize++;

}

4、🥉浏览数据

这里写了一点不一样的东西：可以打印出容量和当前数据个数，可以看出空间使用情况🧠

void watchData()

{

printf("pArr[%d][%d]:\n", curSize, capacity);

for (int i = 0; i < curSize; i++)

{

printf("%s-%d-%.2f\n",

pArr[i].name, pArr[i].age, (pArr + i)->score);

}

printf("\n");

}

5、🥉删除数据

这里是直接申请一个新的数组，直接拷贝过去

void pop(stu* delData)

{

if (curSize < 1) return;

if ( 1 == curSize ) //只有一个元素时

{

free(pArr);

initData();

return;

}

else

{

//申请新空间

stu* pNew = (stu*)malloc(sizeof(stu) * (curSize - 1));

assert(pNew);

//拷贝，第一个到倒数第二个

memcpy(pNew, pArr, sizeof(stu) * (curSize - 1));

free(pArr); //释放原来的空间

pArr = pNew; //pArr指向新数据

curSize--;

capacity = curSize;

return;

}

3、🥈数组尾插头删实现队列

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<assert.h>

typedef struct student

{

char name[20];

int age;

double score;

}stu;

int curSize; //记录当前元素个数

int capacity; //记录当前容量

stu* pArr; //指向当前内存段的首地址

//初始化

void initData();

//insertData

void push(stu* inserData);

//浏览数据

void watchData();

//删除数据

void pop(stu* delData);

int main()

{

initData();

stu d[5] =

{

{ "关羽", 18, 18.67 },

{ "张飞", 28, 28.67 },

{ "赵云", 38, 38.67 },

{ "马超", 48, 58.67 },

{ "黄忠", 58, 48.67 }

};

for (int i = 0; i < 5; i++)

{

push(d + i);

}

watchData();

pop(d);

watchData();

pop(d);

watchData();

pop(d);

watchData();

pop(d);

watchData();

return 0;

}

//初始化

void initData()

{

curSize = 0;

capacity = 0;

pArr = NULL;

}

//insertData

void push(stu* inserData)

{

//需要开内存

if (capacity <= curSize)

{

//计算新开内存

capacity += (capacity >> 1 > 1) ? (capacity >> 1) : 1;

stu* pNew = (stu*)malloc(sizeof(stu) * capacity);//新开内存

assert(pNew); //防御性编程

if (pArr)

{

memcpy(pNew, pArr, sizeof(stu) * curSize);

//释放原有内存段

free(pArr);

}

//pArr指向新开内存段

pArr = pNew;

}

//inserData放入数组中

memcpy(pArr + curSize, inserData, sizeof(stu));

//元素个数加一

curSize++;

}

//浏览数据

void watchData()

{

printf("pArr[%d][%d]:\n", curSize, capacity);

for (int i = 0; i < curSize; i++)

{

printf("%s-%d-%.2f\n",

pArr[i].name, pArr[i].age, (pArr + i)->score);

}

printf("\n");

}

//删除数据

void pop(stu* delData)

{

if (curSize < 1) return;

if (curSize == 1) //只有一个元素时

{

free(pArr);

initData();

return;

}

else

{

//申请新空间

stu* pNew = (stu*)malloc(sizeof(stu) * (curSize - 1));

assert(pNew);

//拷贝，第二个到最后一个

memcpy(pNew, pArr + 1, sizeof(stu) * (curSize - 1));

free(pArr); //释放原来的空间

pArr = pNew; //pArr指向新数据

curSize--;

capacity = curSize;

return;

}

声明：本文为CSDN博主「热爱编程的小K」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。

原文链接：https://blog.csdn.net/qq_72157449/article/details/129624459

数据结构与算法——栈和队列＜也不过如此＞

🏅文章目录

一、🥇栈

二、🥇队列

一、🥇栈

1、🥈概念理解

2、🥈链表头插头删实现栈

1、🥉预备准备

2、🥉创建结点函数

3、🥉遍历函数

4、🥉头插

5、🥉头删

3、🥈链表尾插尾删实现栈

二、🥇队列

1、🥈概念理解

2、🥈数组头插尾删实现队列

1、🥉预备准备

2、🥉初始化

4、🥉浏览数据

5、🥉删除数据

3、🥈数组尾插头删实现队列

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

数据结构与算法——栈和队列＜也不过如此＞

🏅文章目录

一、🥇栈

二、🥇队列

一、🥇栈

1、🥈概念理解

2、🥈链表头插头删实现栈

1、🥉预备准备

2、🥉创建结点函数

3、🥉遍历函数

4、🥉头插

5、🥉头删

3、🥈链表尾插尾删实现栈

二、🥇队列

1、🥈概念理解

2、🥈数组头插尾删实现队列

1、🥉预备准备

2、🥉初始化

4、🥉浏览数据

5、🥉删除数据

3、🥈数组尾插头删实现队列

热门文章

最新文章

相关课程

相关电子书

相关实验场景