自己做的网站为什么访问不,佛山网站优化平台,wordpress网站转app插件下载,ajax实现wordpress导航栏前言#xff1a; 本节博客是对基础数据结构队列的一种实现思路的分享#xff0c;有需要借鉴即可。 1.队列的概念
队列#xff1a;只允许在一端进行插入数据操作#xff0c;在另一端进行删除数据操作的特殊线性表#xff0c;队列具有先 进先出FIFO(First In First Out) 入… 前言 本节博客是对基础数据结构队列的一种实现思路的分享有需要借鉴即可。 1.队列的概念
队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先 进先出FIFO(First In First Out) 入队列进行插入操作的一端称为队尾 出队列进行删除操作的一 端称为队头 与此恰好相反的数据结构是栈的概念详情见博客LINK
2.队列的结构 在写代码之前我们首先要搞清楚几个问题 1.队列依托的底层数据结构是什么为什么 如果用数组来做队列的话有个问题就是需要不停的一个一个的挪动数据。 我们接下来看一下用链表做队列的情况: 所以选择单链表。因为单链表可行且效率较高。
总结一下:用数组实现队列无论怎么进行布局都避免不了挪动数据的问题用链表实现尾插可以作为队尾插入数据头删可以用来出数据。
2.队列的一个整体接口是如何的
3.为什么在队列的效率考虑我采用了一个结构体来存储指针这里指针意思是记录phead的内容与ptail的内容的指针 原因如果不用结构体来存储指针的话那我们每个接口传入都需要传入这两个指针比较麻烦。
3.各种接口的实现
1.初始化与销毁
void QueueInit(Queue* pq)
{assert(pq);pq-phead pq-ptail NULL;pq-size 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* pcur pq-phead;while (pcur){QNode* next pcur-next;//记录free(pcur);//销毁pcur next;//更新}pq-phead pq-ptail NULL;pq-size 0;
}int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}
2.进队列与出队列
这个模块属于队列的重点因而特地强调一下。
在进队列的情况下有两种情况一是没有结点的时候需要移动phead与ptail两个指针。二是有一个或者多个结点的时候只需要移动ptail进行尾插即可。
在出队列的情况下有三种情况一是没有结点的时候不能出队列二是有一个队列的时候需要对ptai和phead两个指针做改动三是有多个结点的时候只需要修改phead进行头删即可。
void QueuePush(Queue* pq, QDataType x)//尾插
{assert(pq);//申请一块堆空间QNode* newnode (QNode*)malloc(sizeof(QNode));if(newnode NULL){perror(malloc fail);exit(1);}//新节点的初始化newnode-val x;newnode-next NULL;//如果是没有结点时候需要插入if (pq-phead NULL){pq-phead pq-ptail newnode;}//至少有一个节点时需要插入尾插else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}void QueuePop(Queue* pq)
{assert(pq);//这里其实有三种不同的情况//1.没有结点这种是不可以删除的//2.一个结点那么就需要phead与ptail都需要调整(容易被坑)//3.多个结点只需要调整phead即可assert(pq-phead ! NULL);if (pq-phead pq-ptail){free(pq-phead);pq-phead pq-ptail NULL;}else{QNode* next pq-phead-next;free(pq-phead);pq-phead next;}pq-size--;
}3.取头结点与取尾结点
QDataType QueueFront(Queue* pq)
{assert(pq);//没有数据不能取出assert(pq-phead ! NULL);//有数据return pq-phead-val;
}QDataType QueueBack(Queue* pq)
{assert(pq);//没有数据不能取出assert(pq-phead ! NULL);//有数据return pq-ptail-val;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq-phead NULL;
}4.全部代码一览
#includeQueue.hvoid QueueInit(Queue* pq)
{assert(pq);pq-phead pq-ptail NULL;pq-size 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* pcur pq-phead;while (pcur){QNode* next pcur-next;//记录free(pcur);//销毁pcur next;//更新}pq-phead pq-ptail NULL;pq-size 0;
}int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}void QueuePush(Queue* pq, QDataType x)//尾插
{assert(pq);//申请一块堆空间QNode* newnode (QNode*)malloc(sizeof(QNode));if(newnode NULL){perror(malloc fail);exit(1);}//新节点的初始化newnode-val x;newnode-next NULL;//如果是没有结点时候需要插入if (pq-phead NULL){pq-phead pq-ptail newnode;}//至少有一个节点时需要插入尾插else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}void QueuePop(Queue* pq)
{assert(pq);//这里其实有三种不同的情况//1.没有结点这种是不可以删除的//2.一个结点那么就需要phead与ptail都需要调整(容易被坑)//3.多个结点只需要调整phead即可assert(pq-phead ! NULL);if (pq-phead pq-ptail){free(pq-phead);pq-phead pq-ptail NULL;}else{QNode* next pq-phead-next;free(pq-phead);pq-phead next;}pq-size--;
}QDataType QueueFront(Queue* pq)
{assert(pq);//没有数据不能取出assert(pq-phead ! NULL);//有数据return pq-phead-val;
}QDataType QueueBack(Queue* pq)
{assert(pq);//没有数据不能取出assert(pq-phead ! NULL);//有数据return pq-ptail-val;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq-phead NULL;
}#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#includestdio.h
#includestdbool.h
#includestdlib.h
#includeassert.h//队列结构-底层单链表实现
typedef int QDataType;
typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;//两个指针的结构体
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;//实现的各种接口
//初始化与销毁
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
int QueueSize(Queue* pq);
//插入与删除
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
//取头结点与取尾结点
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);#includeQueue.htest1()
{Queue q;QueueInit(q);QueuePush(q, 1);QueuePush(q, 2);QueuePush(q, 3);QDataType x QueueFront(q);printf(%d , x);QueuePop(q);x QueueFront(q);printf(%d , x);QueuePop(q);QueuePush(q, 4);QueuePush(q, 5);QueuePush(q, 6);//取出while (QueueSize(q) ! 0){x QueueFront(q);printf(%d , x);QueuePop(q);}}int main()
{test1();return 0;
} 完。
