网站开发编程环境,域名备案网站备案查询,个人小程序开发多少钱,制作ppt的软件是什么队列是一种常见的数据结构#xff0c;它具有先进先出#xff08;First-In-First-Out#xff0c;FIFO#xff09;的特性#xff0c;类似于排队等候的场景。以下是队列的要点#xff1a;
1. 定义#xff1a;队列是一种线性数据结构#xff0c;由一系列元素组成#xff… 队列是一种常见的数据结构它具有先进先出First-In-First-OutFIFO的特性类似于排队等候的场景。以下是队列的要点
1. 定义队列是一种线性数据结构由一系列元素组成可以进行插入和删除操作。插入操作称为入队只能在队列的末尾进行删除操作称为出队只能从队列的前端进行。
2. 特性队列遵循先进先出的原则最先入队的元素将最先出队。
3. 基本操作 - 入队Enqueue将元素插入到队列的末尾。 - 出队Dequeue从队列的前端删除一个元素并返回删除的元素。 - 队列是否为空isEmpty判断队列是否为空即没有任何元素。 - 队列长度size返回队列中元素的个数。
4. 实现方式 - 数组使用数组实现队列时需要维护两个指针一个指向队列的前端另一个指向队列的末尾。出队时移动前端指针入队时移动末尾指针。注意需要循环利用数组空间。 - 链表使用链表实现队列时新元素可以直接添加到链表末尾出队时删除链表的头节点。
5. 队列的应用 - 广度优先搜索算法BFS在图的遍历中广度优先搜索需要使用队列来实现层次遍历。 - 计算机任务调度操作系统中的任务调度可以使用队列来管理任务的执行顺序。 - 队列作为其他数据结构的辅助结构例如树的层次遍历、图的广度优先搜索等。
6. 常见类型 - 普通队列普通队列遵循FIFO原则用于常规的数据排队。 - 优先队列Priority Queue在出队时按照优先级进行排序元素的出队顺序不一定按照插入顺序。 队列在计算机科学中具有广泛的应用从操作系统到算法设计都有着重要作用。它是解决许多问题的重要工具之一。
顺序表队列
/*
* 文件名称queue.c
* 创 建 者WM
* 创建日期2023年08月21日
* 描 述顺序队列//下标为rear里没有数据
*/
#include stdio.h
#includestdlib.h
#define SIZE 8
typedef int data_t;//构造节点类型
typedef struct node{data_t data[SIZE];//保存数据的数据域data_t front;data_t rear;
} sequeue;
sequeue *createEmptySequeue()
{sequeue *p (sequeue *)malloc(sizeof(sequeue));if(NULL p){perror(createEmptySequeue malloc failed);return NULL;}//只要你申请空间就是为了让他装上数据p-rear 0;//使用的时候是数组的下标p-front 0;//使用的时候是数组的下标return p;
}
int insert(sequeue* sq,data_t h)
{sq-data[sq-rear]h;sq-rear(sq-rear1)%SIZE;//注意
}
int out_queue(sequeue *sq)
{ data_t valsq-data[sq-front];sq-front(sq-front1)%SIZE;printf(%d \n,val);return val;
}
int isQueue_empty(sequeue *sq)
{if(sqNULL) -1;return sq-frontsq-rear;
}
//注意
int isQueue_full(sequeue *sq)
{//return (sq-rear-sq-frontSIZE)%SIZESIZE-1;//这个算法很重要return (sq-rear1) % SIZE sq-front;//或者这个。
}
//注意
int isQueue_full2(sequeue*sq)
{if(sq-frontsq-rear)return sq-front-sq-rear1;if(sq-frontsq-rear)return sq-rear-sq-frontSIZE-1;
}int queue_num(sequeue* sq)//谁大谁在前面。
{return (sq-frontsq-rear)?(sq-rear-sq-front):(sq-rear-sq-frontSIZE);
}void clear_queue(sequeue *sq)
{while (!isQueue_empty(sq))out_queue(sq);
}int main(int argc, char *argv[])
{ sequeue*pheadcreateEmptySequeue();for (int i 0; i SIZE-1; i){insert(phead,i1);}out_queue(phead);printf(%d \n,queue_num(phead));return 0;
} 链表队列
/*
* 文件名称queue.c
* 创 建 者WM
* 创建日期2023年08月21日
* 描 述链表队列
*/
#include stdio.h
#includestdlib.h
typedef int data_t;//构造链表节点类型
typedef struct node{data_t data;//保存数据的数据域struct node*next;//保存下一个节点的地址
} linklist ;
typedef struct {linklist *front;linklist* rear;
} lqueue;lqueue* creat_lqueue()
{lqueue*lq(lqueue*)malloc(sizeof(lqueue));lq-front(linklist*)malloc(sizeof(linklist));lq-front-nextNULL;lq-rearlq-front;return lq;
}
int insert(lqueue* lq,data_t h)
{linklist *new(linklist *)malloc(sizeof(linklist));if(NULLnew) return -1;new-datah;new-nextNULL;lq-rear-nextnew;lq-rearnew;
}
int out_queue(lqueue*lq)
{linklist* mlq-front-next;lq-front-nextm-next;int valm-data;free(m);mNULL;printf(%d \n,val);return val;
}
int isQueue_empty(lqueue*lq)
{return lq-frontlq-rear;
}
int queue_num(lqueue*lq)
{int len0;linklist* h lq-front;while (h-next!NULL){hh-next;len;}return len;
}
void clear_queue(lqueue*lq)
{while (!isQueue_empty(lq))out_queue(lq);
}
int main(int argc, char *argv[])
{ lqueue*lqheadcreat_lqueue();insert(lqhead,9);insert(lqhead,110);printf(%d \n,queue_num(lqhead));out_queue(lqhead);out_queue(lqhead);printf(%d \n,queue_num(lqhead));clear_queue(lqhead);printf(%d \n,queue_num(lqhead));return 0;
}
