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

🏆作者主页：king&南星
🎄专栏链接：数据结构

一、🥇栈

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

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 0memcpy(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;}
}

🎉欢迎各位→点赞👏 + 收藏💞 + 留言🔔​
💬总结：希望你看完之后，能对你有所帮助，不足请指正！共同学习交流 🐾