转载:http://www.noobyard.com/article/p-zwjpgmjx-o.htmlhtml
1 链队列的存储结构编程
将对头指针front指向链队列的头结点,队尾指针rear指向终端结点。数组
空队列时,头指针front和尾指针rear都指向头结点。spa
链队列的存储结构为:.net
typedef int QElemType; typedef struct QNode { //结点结构 QElemType data; struct QNode *next; }QNode; typedef struct QNode * QueuePtr; typedef struct { //队列的链表结构 QueuePtr rear; QueuePtr front; }LinkQueue;
2 入队操做指针
//插入元素e为Q的新的队尾结点 Status EnQueue(QueuePtr Q, QElemType e) { QueuePtr q = (QueuePtr)malloc(sizeof(QNode)); if (!q) { //存储分配失败 exit(OVERFLOW); } q->data = e; q->next = NULL; Q->rear->next = q; Q->rear = q; return OK; }
3 出队操做code
出队操做,就是头结点的后继结点出队,将头结点的后继改成它后面的结点。htm
若链表除头结点外只剩一个元素时,则需将rear指针指向头结点。blog
//若队列不空,删除Q的队头元素,用e返回其值,并返回OK,不然返回ERROR。 Status DeQueue(QueuePtr Q, QElemType *e) { QueuePtr q; if (Q->rear == Q->front) { //空队列 return ERROR; } q = Q->front->next; //q指向第一个结点 *e = q->data; Q->front->next = q->next; if (Q->rear == p) { //若队头就是队尾,删除后,须要将rear指针指向头结点 Q->rear = Q->front; } free(q); return OK; }
4 循环队列与链队列的比较队列
从时间上考虑,循环队列和链队列的基本操做都是O(1),不过循环队列是事先已申请好空间,使用期间不会释放。而对于链队列,每次申请和释放结点也会存在一些时间开销。若是入队和出队频繁,二者仍是有细微差别的。
从空间来讲,循环队列必须有一个固定的长度,因此就有了存储元素个数和空间浪费的问题。而链队列不存在这个问题,尽管它须要一个指针域,会产生一些空间上的开销,可是是能够接受的。因此从空间上说,链队列更加灵活。
总的来讲,在能够肯定链队列最大长度的状况下,建议使用循环队列。若是没法预估队列的长度,则使用链队列。
转载:https://www.cnblogs.com/hughdong/archive/2017/05/11/6841970.html
(做者说的挺有意思的话:You know something and I know nothing.)
和顺序栈相相似,在队列的顺序存储结构中,除了用一组地址连续的存储单元依次存放从队头到队尾的元素外,尚需敷设两个指针front和rear分别指示队列头元素位置和队列尾元素的位置。
若是使用顺序表做为队列的话,当处于右图状态则不能继续插入新的队尾元素,不然会由于数组越界而致使程序代码被破坏。
由此产生了由链表实现的循环队列,只有队列未满时才能够插入新的队尾元素。
下面内容,转载:http://www.noobyard.com/article/p-konwsnvh-gw.html
1.图中有两个指针(其实就是两个整数型变量,由于在这里有指示做用,因此这里理解为指针)front、rear,一个指示队头,一个指示队尾。
2.rear和front互相追赶着,这个追赶过程就是队列添加和删除的过程,若是rear追到head说明队列满了,若是front追到rear说明队列。
说明:令队列空间中的一个单元闲置,使得队列非空时,Q.rear与Q.front之间至少间隔一个空闲单。(思考为何空一格)
3.咱们把它掰弯,用的是求余,这样两个值就不会跑出最大范围,而且能够实现弯曲的效果,因此说对于循环队列咱们必须给定最大值MAXQSIZE。
这实际上是咱们臆想的,反正咱们要作的就是利用循环来解决空间浪费的问题。
☆当添加一个元素时,(rear+1)%MAXQSIZE; //理解为何求余?
☆当删除一个元素时,(front+1)%MAXQSIZE;//理解为何求余?
☆当rear=front的时候,队列多是满,也多是空。(这也是为何空一格的缘由)
由于存在满和空两种状况,咱们须要分别判断:
☆满:当队列添加元素到rear的下一个元素是head的时候,也就是转圈子要碰头了,咱们就认为队列满了。(Q.rear+1)%MAXSIZE=Q.front
☆空:当队列删除元素到head=rear的时候,咱们认为队列空了。Q.rear==Q.front,不必定为0
上面这一段要好好理解,在其余编程的地方,也会用到相似的思想。
下面的代码思想很重要。
2.1对节点的定义
#define MAXQSIZE 100 typedef int QElemtype; typedef int status; typedef struct{ QElemtype *base; int front; int rear; }SqQueue;
2.2初始化队列
SqQueue* InitQueue() { SqQueue *q; q=new SqQueue; q->base=new int[MAXQSIZE]; q->rear=q->front=0; return q; }
2.3添加操做
status EnQueue(SqQueue *q,QElemtype e) { //插入到队尾 if((q->rear+1)%MAXQSIZE==q->front) return 0; q->base[q->rear]=e; q->rear=(q->rear+1)%MAXQSIZE; return 1; }
2.4删除操做
status DeQueue(SqQueue *q) { if(q->front==q->rear) return 0; printf("%d",q->base[q->front]); q->front =(q->front+1)%MAXQSIZE; return 1; }
备注,这插入和删除的操做,相似于标记。(这也很重要)
2.5获取队列长度
int QueueLength(SqQueue *q) { return (q->rear-q->front+MAXQSIZE)%MAXQSIZE; }
补:还有些其余的队列,好比优先队列,双端队列。(用的时候能够查STL)
队列练习: