1.栈（一端插和删）
1.1栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。//后进去的数据会先出来
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
【注意：】因为不知道什么时候出栈，所以顺序也是多变的
具体实现，可以看一下下面这个图片的演示
关键的元素有
接下来就是我们的增删查改，通过接口来实现啦
主体：
// 静态 //typedef int STDataType; // #define N 10 // typedef struct Stack // { // STDataType _a[N]; // int _top; // 栈顶 // }Stack; //更多用的是下面的动态 #pragma once #include<stdio.h> #include<stdlib.h> #include<stdbool.h> #include<assert.h> typedef int STDataType; typedef struct stack { STDataType* a;//栈底 int top; //栈顶 int capacity; //容量 }ST; //初始化栈 void STInit(ST* ps); //销毁栈 void STDestory(ST* ps); //入栈（压栈） void STPush(ST* ps, STDataType x); //出栈 void STPop(ST* ps); //获取栈顶元素 STDataType STTop(ST* ps); //获取栈中有效元素个数 int STSize(ST* ps); //检测栈是否为空，如果为空返回非零结果，如果不为空返回0 bool STEmpty(ST* ps);
点拨：
//入栈 ps->a[ps->top] = x; ps->top++; //出栈 ps->top--; //获取栈顶元素 STDataType STTop(ST* ps) { assert(ps); assert(!STEmpty(ps)); return ps->a[ps->top - 1]; //栈顶元素其实就是top前一位 //这里注意栈为空时不能获取到元素 }
有一个小细节：栈顶初始化的选择会影响到栈，所以还是要通过接口来实现，如下
栈的灵魂就在于top，top++，top--,更多的还是在做题中去理解吧
2.队列（一端插另一段删）
2.1队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数 组头上出数据，效率会比较低。
2.2 队列的实现
创建结构体QueueNode这个结构体是创建节点的，节点由数据和指向下一个节点的指针构成的
第二个结构体是创建指向节点的两个指针，对头指针head和队尾指针tail
typedef int QueueDataType; typedef struct QueueNode { struct QueueNode* next; QueueDataType data; }QNode; typedef struct Queue { QNode* head; QNode* tail; }Queue;
队列的接口
void QueueInit(Queue* pq); //初始化队列 void QueueDestory(Queue* pq); //销毁队列 void QueuePush(Queue* pq, QueueDataType x); //插入元素 void QueuePop(Queue* pq); //出队列 QueueDataType QueueFront(Queue* pq); //查看队头元素 QueueDataType QueueBack(Queue* pq); //查看队尾元素 bool QueueEmpty(Queue* pq); //检查队列是否为空 int QueueSize(Queue* pq); //查看队列的长度
1.初始化队列
void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; }
2.销毁队列
当队列不为空时，用一个代替对头往后访问的指针cur ，当cur不为空时，用一个新的节点del 接收cur指向的节点。将del节点释放并置为空，cur在往后走完成对队列的遍历，最后将对头指针和队尾指针都置为空指针
void QueueDestory(Queue* pq) { assert(pq); QNode* cur = pq->head;//再在其中定义Qnode引入 while (cur) { QNode* del = cur;//暂存销毁 cur = cur->next;//保留好进行后移 free(del); del = NULL;//del对每个节点进行释放，保留了cur后移 } pq->head = pq->tail = NULL; }
3.插入元素
队列的性质插入元素只能是尾插，分为两种情况来看：1.队列为空 2.队列不为空
1. 队列为空时，先去malloc一个新节点，让对头和队尾都指向这个新节点
2. 当队列不为空时，malloc一个新节点，将新节点插入到tail指针的下一个位置，新的队尾指向新节点的下一个位置
void QueuePush(Queue* pq, QueueDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); // 1.开辟一个新空间 if (newnode == NULL) { perror("malloc fail!!!"); exit(-1); //不成功直接退出程序 } else { newnode->data = x; //2. 将数据导入到新空间中 newnode->next = NULL; //新节点指向空 } //如果队列为空 if (pq->head ==NULL&& pq->tail==NULL)//说明队列空 { pq->head = pq->tail = newnode; //都指向新节点 } else { pq->tail->next = newnode;//3. 将tail的下一个定为new pq->tail = pq->tail->next;// tail后移 } }
4.出队列（头删）
出队列也分为两种情况：1.队列有一个节点 2.队列有多个节点
void QueuePop(Queue* pq)//队列特性 头删 { assert(pq); assert(!QueueEmpty(pq)); //一个节点 if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else//很多节点 { QNode* del = pq->head;//del暂存然后销毁 pq->head = pq->head->next;//保留起来好进行后移 free(del); del = NULL; } }
5.访问对头
访问得有元素，需要判断队列是否为空
QueueDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; }
6.访问队尾
访问得保证队列有元素，需要判断队列是否为空
QueueDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty); return pq->tail->data; }
7.判断队列是否为空
bool QueueEmpty(Queue* pq) { return pq->head == NULL; //空返回1 有元素0 }
8.查看队列的元素个数
查看队列元素的个数得保证队列有元素，生成一个新的指针接受队头指针，代替头指针往后访问队列,返回n 的数值就是队列的元素个数。
int QueueSize(Queue* pq) { assert(pq); assert(!QueueEmpty); int n = 0; QNode* cur = pq->head; while (cur) { ++n; cur = cur->next; } return n; }
Queue整体代码：
Queue.h
#include<stdio.h> #include<stdbool.h> #include<assert.h> #include<stdlib.h> typedef int QueueDataType; typedef struct QueueNode { struct QueueNode* next; QueueDataType data; }QNode; typedef struct Queue { QNode* head; QNode* tail; }Queue; void QueueInit(Queue* pq); void QueueDestory(Queue* pq); void QueuePush(Queue* pq, QueueDataType x); void QueuePop(Queue* pq); QueueDataType QueueFront(Queue* pq); QueueDataType QueueBack(Queue* pq); bool QueueEmpty(Queue* pq); int QueueSize(Queue* pq);
Queue.c
#include "Queue.h" void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; } void QueueDestory(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* del = cur; cur = cur->next; free(del); del = NULL; } pq->head = pq->tail = NULL; } void QueuePush(Queue* pq, QueueDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail!!!"); exit(-1); } else { newnode->data = x; newnode->next = NULL; } //如果队列为空 if (pq->head ==NULL&& pq->tail==NULL)//说明队列空 { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = pq->tail->next; } } void QueuePop(Queue* pq)//队列特性 头删 { assert(pq); assert(!QueueEmpty(pq)); //一个节点 if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else//很多节点 { QNode* del = pq->head; pq->head = pq->head->next; free(del); del = NULL; } } QueueDataType QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->head->data; } QueueDataType QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty); return pq->tail->data; } bool QueueEmpty(Queue* pq) { return pq->head == NULL; //空返回1 有元素0 } int QueueSize(Queue* pq) { assert(pq); assert(!QueueEmpty); int n = 0; QNode* cur = pq->head; while (cur) { ++n; cur = cur->next; } return n; }
test.c
#include"Queue.h" void testqueue() { Queue q; QueueInit(&q); QueuePush(&q, 555); QueuePush(&q, 666); QueuePush(&q, 777); QueuePush(&q, 1); while (!QueueEmpty(&q)) { printf("%d", QueueFront(&q)); QueuePop(&q); printf("\n"); } QueueDestory(&q); } int main() { testqueue(); return 0; }
