程序员 修电脑 做网站,随机关键词生成器,东莞证券官网,vr技术对网站建设的影响Hello#xff0c;everyone#xff0c;今天小编讲解栈和队列的知识#xff01;#xff01;#xff01;
1.栈
1.1栈的概念及结构 栈#xff1a;一种特殊的线性表#xff0c;其只允许在固定的一端进行插入和删除元素操作。 进行数据插入和删除操作的一端 称为栈顶…Helloeveryone今天小编讲解栈和队列的知识
1.栈
1.1栈的概念及结构
栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。 进行数据插入和删除操作的一端 称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。 压栈栈的插入操作叫做进栈/压栈/入栈 入数据在栈顶。 出栈栈的删除操作叫做出栈。 出数据也在栈顶。 1.2栈的实现 栈的实现一般可以使用 数组或者链表实现相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。 1.2.1 头文件的建立 #include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.h
typedef int datatype;
//这里选用动态数组实现栈单链表也可以
typedef struct stack {datatype* a;int top;//栈顶int capacity;
}ST;
//栈的初始化和销毁
void STInit(ST* pst);
void STDestory(ST* pst);
//入栈和出栈
void STPush(ST* pst,datatype x);
void STPop(ST* pst);
//获取栈顶数据
datatype STTop(ST* pst);
//判空
bool STEmpty(ST* pst);
//栈的数据个数
int STSize(ST* pst);1.2.2 函数的实现 #define _CRT_SECURE_NO_WARNINGS
#include Stack.h
//栈的初始化和销毁
void STInit(ST* pst){assert(pst);pst-a NULL;//top指向栈顶数据的下一个位置,可以理解为下标pst-top 0;//top指向指向栈顶数据可以理解成栈的数据个数//pst-top-1;pst-capacity 0;
}
void STDestory(ST* pst) {assert(pst);free(pst);pst-a NULL;pst-top pst-capacity 0;
}
//容量检查
void Checkcapacity(ST* pst) {assert(pst);if (pst-top pst-capacity) {int newcapacity pst-capacity0?4:pst-capacity * 2;datatype* temp (datatype*)realloc(pst-a, newcapacity * sizeof(datatype));if (temp NULL) {perror(relloc fail);return;}pst-a temp;pst-capacity newcapacity;}
}
//入栈和出栈
void STPush(ST* pst, datatype x) {assert(pst);Checkcapacity(pst);pst-a[pst-top] x;pst-top;
}
void STPop(ST* pst) {assert(pst);assert(pst-top0);pst-top--;
}
//获取栈顶数据
datatype STTop(ST* pst) {assert(pst);assert(pst-top 0);return pst-a[pst-top-1];
}
//判空
bool STEmpty(ST* pst) {assert(pst);return pst-top 0;//表达式判断
}
//栈的数据个数
int STSize(ST* pst) {assert(pst);return pst-top;
} 1.2.3 测试文件 #define _CRT_SECURE_NO_WARNINGS
#include Stack.h
int main() {ST s;STInit(s);STPush(s, 1);STPush(s, 2);STPush(s, 3);STPush(s, 4);STPush(s, 5);printf(%d\n, STTop(s));STPop(s);//STPop(s);printf(%d\n, STTop(s));while (!STEmpty(s)) {printf(%d , STTop(s));STPop(s);}STDestory(s);return 0;
} 2.队列 2.1队列的概念及结构 队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出 FIFO(First In First Out) 入队列进行插入操作的一端称为 队尾 出队列进行删除操作的一端称为 队头 2.2队列的实现 队列也可以数组和链表的结构实现使用链表的结构实现更优一些因为如果使用数组的结构出队列在数组头上出数据效率会比较低。 2.2.1 头文件的建立 #pragma once
#include stdio.h
#include stdlib.h
#include stdbool.h
#include assert.h
typedef int Qdatatype;
//链式结构表示队列
typedef struct QueueNode {struct QueueNode* next;Qdatatype x;
}Node;
//定义结构体表示队头队尾,后续传参改变队列也很方便不用传二级指针。
typedef struct Queue {Node* head;Node* tail;int size;
}Queue;
// 初始化队列
void QueueInit(Queue* q);// 队尾入队列
void QueuePush(Queue* q, Qdatatype data);// 队头出队列
void QueuePop(Queue* q);// 获取队列头部元素
Qdatatype QueueFront(Queue* q);// 获取队列队尾元素
Qdatatype QueueBack(Queue* q);// 获取队列中有效元素个数
int QueueSize(Queue* q);// 检测队列是否为空如果为空返回非零结果如果非空返回0
bool QueueEmpty(Queue* q);// 销毁队列
void QueueDestroy(Queue* q); 2.2.2 函数的实现 #define _CRT_SECURE_NO_WARNINGS
#include Queue.h
void QueueInit(Queue* q) {assert(q);q-head NULL;q-tail NULL;q-size 0;
}
// 队尾入队列
void QueuePush(Queue* q, Qdatatype data) {assert(q);Node* newnode (Node*)malloc(sizeof(Node));if (newnode NULL) {perror(malloc fail);return;}newnode-next NULL;newnode-x data;if (q-tail NULL) {q-head q-tail newnode;}else {q-tail-next newnode;q-tail newnode;}q-size;
}
// 队头出队列
void QueuePop(Queue* q) {assert(q);assert(q-size ! 0);//一个节点if (q-head-next NULL) {free(q-head);q-head q-tail NULL;}else {Node* next q-head-next;free(q-head);q-head next;}q-size--;
}
// 获取队列头部元素
Qdatatype QueueFront(Queue* q) {assert(q);assert(q-head);return q-head-x;
}
// 获取队列队尾元素
Qdatatype QueueBack(Queue* q) {assert(q);assert(q-tail);return q-tail-x;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q) {assert(q);return q-size;
}
// 检测队列是否为空如果为空返回非零结果如果非空返回0
bool QueueEmpty(Queue* q) {assert(q);return q-size 0;//为0返回1不为0返回0
}
// 销毁队列
void QueueDestroy(Queue* q) {assert(q);Node* qcur q-head;while (qcur) {Node* next qcur-next;free(qcur);qcur next;}q-head q-tail NULL;q-size 0;
} 2.2.3 测试文件 #define _CRT_SECURE_NO_WARNINGS
#include Queue.h
int main() {Queue p;QueueInit(p);QueuePush(p,1);QueuePush(p,2);printf(%d\n, QueueFront(p));QueuePush(p, 3);QueuePush(p, 4);printf(%d\n,QueueBack(p));QueuePop(p);printf(%d\n, QueueFront(p));while (!QueueEmpty(p)){printf(%d , QueueFront(p));QueuePop(p);}printf(\n);return 0;
} 另外扩展了解一下实际中我们有时还会使用一种队列叫循环队列。如操作系统讲解生产者消费者模型时可以就会使用循环队列。环形队列可以使用数组实现也可以使用循环链表实现。 今天内容讲解结束下次小编将讲解栈和队列的相关习题。 希望各位友友留下三连和评论
