栈
概念与结构
1. 栈⼀种特殊的线性表，其只允许在固定的⼀端进行插入和删除元素操作。
2. 进行数据插入和删除操作的⼀端称为栈顶，另⼀端称为栈底。
3. 栈中的数据元素遵守后进先出的原则。
4. 栈的插入操作叫做进栈，栈的删除操作叫做出栈。
5. 栈的实现⼀般可以使用数组或者链表实现。
6. 相对而言，使用数组结构实现更优⼀些。因为数组结构更简单，而且能够胜任所有功能。
7. 栈不能遍历，也不找到中间和下面的数据，只能找到最上面的数据，是阉割版的线性表。
1. 想象一下玩具枪的弹夹，我们给弹夹上子弹的时候，先上的子弹被压在弹夹的最下面，后装的子弹在最上面，打枪的时候后装的子弹最先被打出。
2. 这个弹夹其实就是一种栈的数据结构。我们一般把先进后出，后进先出的这种数据结构称之为栈。
3. 从栈的操作特性上看栈这是一种"操作受限的线性表",它只支持在一端插入和删除数据。
分步实现栈的功能
创建栈的结构体
typedef int STDataType; typedef struct Stack { STDataType* arr;//创建动态数组（指针） int capacity;//栈的空间大小 int top;//栈顶，是栈中最后一个数据的下一位 }Stack;
初始化栈
void InitStack(Stack* ps) { assert(ps); //Stack* ps=&stack;本质上是判断：调用函数时候有没有传参数，如果没有那么ps指向任意值，就有可能是NULL。 ps->arr = NULL; ps->capacity = ps->top = 0; }
进栈
void StackPush(Stack* ps, int x) { //判断空间是否足够 if (ps->capacity == ps->top ) { int Newcapacity = ps->capacity == 0 ? 4: 2 * ps->capacity; //在原有的空间基础上继续开辟空间，需要使用realloc()。 STDataType* tmp = (STDataType*)realloc(ps->arr, Newcapacity * sizeof(STDataType)); //判断空间开辟是否成功 if (tmp == NULL) { perror("realloc fail"); exit(1); } else { ps->arr = tmp; ps->capacity = Newcapacity; } } ps->arr[ps->top++] = x;//指针当作动态数组使用 }
出栈
void StackPop(Stack* ps) { assert(ps); assert(ps->top!=0);//当栈中没有元素时候，就不能出栈了。 ps->top--; }
查找栈首元素
STDataType StackTop(Stack* ps) { assert(ps); assert(ps->top != 0); return ps->arr[ps->top - 1];//top指向最后一个元素的下一位 }
销毁栈
void DestroyStack(Stack* ps) { assert(ps); if (ps->arr) { free(ps->arr);//释放动态数组空间 } ps->arr = NULL; ps->capacity = ps->top = 0; }
实现栈的代码
<stack.h> 文件
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int STDataType; typedef struct Stack { STDataType* arr;//创建动态数组（指针） int capacity;//栈的空间大小 int top;//栈顶 }Stack; //初始化 void InitStack(Stack* ps); void DestroyStack(Stack* ps); void StackPush(Stack* ps, STDataType x); void StackPop(Stack* ps); STDataType StackTop(Stack* ps);
<stack.c>文件
#include "stack.h" void InitStack(Stack* ps) { assert(ps); ps->arr = NULL; ps->capacity = ps->top = 0; } void DestroyStack(Stack* ps) { assert(ps); if (ps->arr) free(ps->arr); ps->arr = NULL; ps->capacity = ps->top = 0; } void StackPush(Stack* ps, int x) { //判断空间是否足够 if (ps->capacity == ps->top ) { int Newcapacity = ps->capacity == 0 ? 4: 2 * ps->capacity; STDataType* tmp = (STDataType*)realloc(ps->arr, Newcapacity * sizeof(STDataType)); if (tmp == NULL) { perror("realloc fail"); exit(1); } else { ps->arr = tmp; ps->capacity = Newcapacity; } } ps->arr[ps->top++] = x; } void StackPop(Stack* ps) { assert(ps); assert(ps->top!=0); ps->top--; } STDataType StackTop(Stack* ps) { assert(ps); assert(ps->top != 0); return ps->arr[ps->top - 1];//top指向最后一个元素的下一位 }
<test.c>文件
#include "stack.h" int main()//栈里面的数据不能被遍历，也不能被随机访问。 { Stack stack1; InitStack(&stack1); //DestroyStack(&stack1); StackPush(&stack1, 1); StackPush(&stack1, 2); StackPush(&stack1, 3); StackPush(&stack1, 4); StackPush(&stack1, 5); StackPush(&stack1, 6); while (stack1.top != 0) { int data=StackTop(&stack1); printf("%d\n", data); StackPop(&stack1); } DestroyStack(&stack1); return 0; }
队列
概念与结构
1. 只允许在⼀端进行插入数据操作，在另⼀端进行删除数据操作的特殊线性表。
2. 队列具有先进先出的原则。
3. 队列也可以用数组和链表的结构实现。
4. 使用链表的结构实现更优⼀些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
5. 在数组实现的列队中，出队操作通常需要将队首元素移除。如果队首元素被移除后，队列中的其他元素需要向前移动一位以填补空缺。这个过程的时间复杂度是 O(n)，其中 n 是队列中元素的数量。
分步实现列队的功能
创建列队结构体
typedef int DataType; typedef struct QueueNode //列队节点结构体 { DataType data; struct QueueNode* next; }QueueNode; typedef struct Queue //列队结构体 { QueueNode* phead; QueueNode* ptail; int size; }Queue;
初始化列队
void InitQueue(Queue* ps) { assert(ps); ps->phead = ps->ptail = NULL; ps->size = 0; }
入队
void AddQueue(Queue* ps, DataType x) { assert(ps); QueueNode* newnode = (QueueNode*)malloc(sizeof(DataType)); if (newnode == NULL) { perror("malloc fail"); exit(1); } newnode->data = x; newnode->next = NULL; if ((ps->phead == NULL) && (ps->ptail == NULL)) { ps->phead = ps->ptail = newnode; } else { ps->ptail->next = newnode; ps->ptail = newnode; } ps->size++; }
出队
void PopQueue(Queue* ps) { assert(ps); if ((ps->phead == NULL) && (ps->ptail == NULL)) { exit(1);//要求列队不能为空 } if (ps->phead == ps->ptail) { free(ps->phead);//列队只有一个节点时 ps->phead = ps->ptail = NULL; } else { QueueNode* next = ps->phead->next; free(ps->phead); ps->phead = next; } ps->size--; }
查找队头
DataType TakeFrontQueue(Queue* ps) { assert(ps); if ((ps->phead == NULL) && (ps->ptail == NULL)) { exit(1);//要求列队不能为空 } return ps->phead->data; }
查找对尾
DataType TakeBackQueue(Queue* ps) { assert(ps); if ((ps->phead == NULL) && (ps->ptail == NULL)) { exit(1);//要求列队不能为空 } return ps->ptail->data; }
查找队伍长度
int QueueSize(Queue* ps) { return ps->size; }
销毁队列
void DestroyQueue(Queue* ps) { assert(ps); if ((ps->phead == NULL) && (ps->ptail == NULL)) { exit(1);//要求列队不能为空 } QueueNode* pcur = ps->phead; while (pcur) { QueueNode* next = pcur->next; free(pcur); pcur = next; } ps->phead = ps->ptail = NULL; ps->size = 0; }
实现列队的代码
<queue.h>文件
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int DataType; typedef struct QueueNode { DataType data; struct QueueNode* next; }QueueNode; typedef struct Queue { QueueNode* phead; QueueNode* ptail; int size; }Queue; void InitQueue(Queue* ps); void AddQueue(Queue* ps, DataType x); void PopQueue(Queue* ps); DataType TakeFrontQueue(Queue* ps); DataType TakeBackQueue(Queue* ps); int QueueSize(Queue* ps); void DestroyQueue(Queue* ps);
<queue.c>文件
#include "queue.h" void InitQueue(Queue* ps) { assert(ps); ps->phead = ps->ptail = NULL; ps->size = 0; } void AddQueue(Queue* ps, DataType x) { assert(ps); QueueNode* newnode = (QueueNode*)malloc(sizeof(DataType)); if (newnode == NULL) { perror("malloc fail"); exit(1); } newnode->data = x; newnode->next = NULL; if ((ps->phead == NULL) && (ps->ptail == NULL)) { ps->phead = ps->ptail = newnode; } else { ps->ptail->next = newnode; ps->ptail = newnode; } ps->size++; } void PopQueue(Queue* ps) { assert(ps); if ((ps->phead == NULL) && (ps->ptail == NULL)) { exit(1);//要求列队不能为空 } if (ps->phead == ps->ptail) { free(ps->phead);//列队只有一个节点时 ps->phead = ps->ptail = NULL; } else { QueueNode* next = ps->phead->next; free(ps->phead); ps->phead = next; } ps->size--; } DataType TakeFrontQueue(Queue* ps) { assert(ps); if ((ps->phead == NULL) && (ps->ptail == NULL)) { exit(1);//要求列队不能为空 } return ps->phead->data; } DataType TakeBackQueue(Queue* ps) { assert(ps); if ((ps->phead == NULL) && (ps->ptail == NULL)) { exit(1);//要求列队不能为空 } return ps->ptail->data; } int QueueSize(Queue* ps) { return ps->size; } void DestroyQueue(Queue* ps) { assert(ps); if ((ps->phead == NULL) && (ps->ptail == NULL)) { exit(1);//要求列队不能为空 } QueueNode* pcur = ps->phead; while (pcur) { QueueNode* next = pcur->next; free(pcur); pcur = next; } ps->phead = ps->ptail = NULL; ps->size = 0; }
<test.c> 文件
#include "queue.h" int main() { Queue q; InitQueue(&q); AddQueue(&q, 1); AddQueue(&q, 2); AddQueue(&q, 3); AddQueue(&q, 4); AddQueue(&q, 5); printf("%d\n", TakeFrontQueue(&q)); PopQueue(&q); printf("%d\n", TakeFrontQueue(&q)); printf("%d\n", TakeBackQueue(&q)); printf("%d\n", QueueSize(&q)); DestroyQueue(&q); //PopQueue(&q); //PopQueue(&q); //PopQueue(&q); return 0; }
致谢
感谢您花时间阅读这篇文章！如果您对本文有任何疑问、建议或是想要分享您的看法，请不要犹豫，在评论区留下您的宝贵意见。每一次互动都是我前进的动力，您的支持是我最大的鼓励。期待与您的交流，让我们共同成长，探索技术世界的无限可能！
