本文共 2124 字,大约阅读时间需要 7 分钟。
声明:版权所有,欢迎转载。 联系信箱:yiluohuanghun@gmail.com】
感觉我的这个专题的顺序安排的有点问题,按照我们常规的思维应该是先线性表、队列、堆栈、单链表、双链表、但是我貌似给排反了,主要还是之前没想着要写这么细,那也就算了吧,既然专题名字叫“chaos的算法”,那就实实在在的让它“chaos”一次吧。
队列是一种特殊的线性表,它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。在队列这种数据结构中,最先插入的元素将是最先被删除的元素;反之最后插入的元素将最后被删除的元素,因此队列又称为“先进先出”(FIFO—first in first out)的线性表。队列的用途很广泛,一般在工程中比较常用的地方我感觉是消息部分,把N多的消息做成一个消息队列是最好不过的了。
对于队列来说,又分为静态队列结构和链式队列结构,相对而言静态队列结构要容易理解一些,其实队列跟我们下一篇要说的栈是很类似的,都既可以用链表实现、也可以用顺序表实现。但是队列跟栈相反,栈一般我们用顺序表、而队列我们一般采用链表实现,简称链式队列。先看数据结构吧:
1 2 3 4 5 6 7 8 9 10 11 | typedef int ElemType; typedef struct LNode { ElemType elem; struct LNode *next; }LNode, *LinkList; typedef struct queue { LinkList Front; //队头 LinkList Rear; //队尾 }QUEUE; |
我们一般将队头指针指向链队列的头结点,队尾指针指向终端结点。其实在链式队列中队头不是必要的,但是有了队头相对来说操作起来就容易的多了。创建一个队列一般要完成两件事情。一个是在内存中创建一个头结点,二是将队列的头指针(队头)和尾指针都指向这个新生成的头结点,因为此时还未插入任何结点,所以此时的队列为空队列。
1 2 3 4 5 6 7 8 | //初始化队列 void InitQueue(QUEUE *Q) { Q->Front = (LinkList) malloc ( sizeof (LNode)); if (NULL == Q->Front) return ; Q->Rear = Q->Front; } |
入队操作时,一般是将队尾结点的next指针指向待插入结点,而后将队尾指针指向待插入结点。思路倒是很简单的。在别的地方找了一个不错的图,就借鉴过来了(
1 2 3 4 5 6 7 8 9 10 11 | //入队 void EnQueue(QUEUE *Q, ElemType elem) { LinkList p = (LinkList) malloc ( sizeof (LNode)); if (NULL == p) return ; p->elem = elem; p->next = NULL; Q->Rear->next = p; Q->Rear = p; } |
出队操作时,将队头所指结点的值取出,并申请一个结点内存指向待出队结点,该结点主要用于使队头指针移向下一个结点。先看下代码吧:
1 2 3 4 5 6 7 8 9 10 11 | //出队 void DeQueue(QUEUE *Q, ElemType *elem) { LinkList s = (LinkList) malloc ( sizeof (LNode)); if (QueueEmpty(*Q)) return ; *elem = Q->Front->next->elem; s = Q->Front->next; Q->Front->next = s->next; free (s); } |
这里有一个比较重要的地方还没说,我们的Front队头指针是不存放数据的,这点大家一点要看清,要不然在出队和入队操作时回有点小迷糊的。
在某些时候我们还要判断队列是否为空,这个在一些清空下是必须的哟
1 2 3 4 5 6 7 | //判断队列空 bool QueueEmpty(QUEUE Q) { if (Q.Front == Q.Rear) return TRUE; return FALSE; } |
一般来说对于队列的操作无外乎也就几种,当然了,还有一种叫做获取队头元素
1 2 3 4 5 6 7 | /*获取队头元素内容 */ void GetFront(QUEUE Q, ElemType *elem) { if (QueueEmpty(Q)) return ; *elem = Q.Front->next->elem; } |
队列的操作也就这么多,在最好还是要强调一点,一定要做个测试程序出来,验证下自己所写程序的可用性。这个是非常的有必要的。
本文转自 驿落黄昏 51CTO博客,原文链接:http://blog.51cto.com/yiluohuanghun/1263369,如需转载请自行联系原作者