🏅文章目录

一、🥇栈

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