目录
栈(Stack)
栈的结构体
初始化
销毁
入栈
判空
出栈
取栈顶元素
获取栈个数
测试:
队列(Queue)
队列的结构体
单个结点
队列
初始化
销毁
入队列,队尾
判空
出队列,队头
取队头数据
取队尾数据(非标准操作)
获取队列个数
测试:
栈(Stack)
栈是一种特殊的线性表,其只允许在特定的一端进行插入和删除操作。
进行插入和删除操作的一端叫做栈顶
另一端称为栈底
栈中的数据元素遵循后进先出LIFO(Last In First Out )的原则
压栈:栈的插入操作也被称为进栈、入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈,出数据也在栈顶。
因为栈只在一端进行操作,所以栈的实现使用数组更加优越。
栈的结构体
//重命名,方便统一修改typedef int STDataType;typedef struct stack {STDataType* arr;int capacity;//栈的容量int top;//栈顶位置(有效元素个数)}ST;
初始化
//初始化void STInit(ST* ps) {assert(ps);//不能传入NULLps->arr = NULL;ps->capacity = ps->top = 0;}
销毁
//销毁void STDestory(ST* ps) {assert(ps);//不能传入NULLif (ps->arr) {//防止对NULL指针的引用(即栈为空的情况)free(ps->arr);}ps->arr = NULL;ps->capacity = ps->top = 0;}
入栈
//入栈void STPush(ST* ps, STDataType x) {assert(ps);if (ps->capacity == ps->top) {//若空间不足int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//若栈容量为0,给定初始值,否则以两倍大小增长STDataType* p = (STDataType*)realloc(ps->arr, newcapacity * sizeof(STDataType));if (!p) {//申请失败,直接返回perror("realloc fail!");exit(1);}ps->arr = p;ps->capacity = newcapacity;//改变原容量大小}ps->arr[ps->top++] = x;//先给栈顶赋值,在加加}
判空
//判空bool STEmpty(ST* ps) {assert(ps);return ps->top == 0;//返回bool值,直接返回比较运算符的返回值}
出栈
//出栈void STPop(ST* ps) {assert(ps && !STEmpty(ps));//不能传入NULL && 栈为空ps->top--;//出栈,让栈顶减减}
取栈顶元素
//取栈顶元素STDataType STTop(ST* ps) {assert(ps && !STEmpty(ps));//不能传入NULL && 栈为空return ps->arr[ps->top - 1];//返回栈顶元素,让栈顶减减}
获取栈个数
//获取栈有多少元素int STSize(ST* ps) {assert(ps);return ps->top;//直接返回栈顶下标(即元素个数)}
测试:
队列(Queue)
队列也是一种特殊的线性表,其在一端进行插入操作,另一端进行删除操作。
进行插入操作的一端叫做队尾(rear)。
进行删除操作的一端叫做队头(front)。
队列中的数据元素遵循后进先出FIFO(Frist In First Out )的原则
入队:队列的插入操作,一般发生在队尾
出队:队列的删除操作,一般发生在队头
因为队列在头部删除数据,使用数组,移动数据的时间复杂比较高,所以使用链表更优越。
队列的结构体
单个结点
//重命名,方便统一修改typedef int QDataType;//队列单个结点结构typedef struct QueueNode {QDataType data;//数据struct QueueNode* next;//下一个结点}QN;
队列
//队列结构typedef struct queue {QN* front;//队头QN* rear;//队尾int size;//结点数}Q;
初始化
//初始化队列void QueueInit(Q* pq) {assert(pq);pq->front = pq->rear = NULL;pq->size = 0;}
销毁
//销毁void QueueDestory(Q* pq) {assert(pq);assert(!QueueEmpty(pq));//队列为空,不用销毁QN* pcur = pq->front;while (pcur) {QN* next = pcur->next;free(pcur);//依次释放每一个结点pcur= next;}pq->rear = pq->front = NULL;//置队头队尾pq->size = 0;}
入队列,队尾
//入队列,队尾void QueuePush(Q* pq, QDataType x) {assert(pq);QN* node = (QN*)malloc(sizeof(QN));//开辟一个新结点if (!node) {//防止为空perror("malloc fail!");exit(1);}node->data = x;//data元素node->next = NULL;//next指针if (pq->front == NULL) {//若队列为空,队头队尾都要改变pq->front = pq->rear = node;}else {//若不为空,则改变尾结点指向pq->rear->next = node;pq->rear = node;}pq->size++;//队列元素++}
判空
//判空bool QueueEmpty(Q* pq) {assert(pq);return pq->size == 0;}
出队列,队头
//出队列,队头void QueuePop(Q* pq) {assert(pq);assert(!QueueEmpty(pq));//不能为空if (pq->front->next == NULL) {//若只有一个元素,队尾的指向也要发生改变free(pq->front);pq->front = pq->rear = NULL;}else {//若有多个元素,只用改变队头指向QN* del = pq->front;pq->front = pq->front->next;free(del);del = NULL;}pq->size--;}
取队头数据
//取队头数据QDataType QueueFront(Q* pq) {assert(pq);assert(!QueueEmpty(pq));return pq->front->data;}
取队尾数据(非标准操作)
//取队尾数据QDataType QueueRear(Q* pq) {assert(pq);assert(!QueueEmpty(pq));return pq->rear->data;}
获取队列个数
//队列有效个数int QueueSize(Q* pq) {assert(pq);return pq->size;}