※数据结构※→☆线性表结构（queue）☆============优先队列 链式存储结构（queue priority list）（十二）
优先队列(priority queue)
普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高进先出 （largest-in，first-out）的行为特征。
例如下图：任务的优先权及执行顺序的关系
优先队列是0个或多个元素的集合,每个元素都有一个优先权或值
时间复杂度
Push时进行排序
有序链表（即顺序存储结构），则插入时找插入点的时间复杂度为O(n)
直接出链表表头（也就是队头元素）的时间复杂度为O(1)
Pop时进行遍历
有序链表（即顺序存储结构），则插入时找插入点的时间复杂度为O(1)
遍历出优先级最高的链表表头（也就是队头元素）的时间复杂度为O(n)
======================================================================================================
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
在队列这种数据结构中，最先插入的元素将是最先被删除的元素；反之最后插入的元素将是最后被删除的元素，因此队列又称为“先进先出”（FIFO—first in first out）的线性表。
队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表
（1）允许删除的一端称为队头（Front）。
（2）允许插入的一端称为队尾（Rear）。
（3）当队列中没有元素时称为空队列。
（4）队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。
队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾（即不允许"加塞"），每次离开的成员总是队列头上的（不允许中途离队），即当前"最老的"成员离队。
链式存储结构
在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的).
它不要求逻辑上相邻的元素在物理位置上也相邻.因此它没有顺序存储结构所具有的弱点,但也同时失去了顺序表可随机存取的优点.
链式存储结构特点：
1、比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成，所以相同空间内假设全存满的话顺序比链式存储更多)。
2、逻辑上相邻的节点物理上不必相邻。
3、插入、删除灵活 (不必移动节点，只要改变节点中的指针)。
4、查找结点时链式存储要比顺序存储慢。
5、每个结点是由数据域和指针域组成。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
以后的笔记潇汀会尽量详细讲解一些相关知识的，希望大家继续关注、支持、顶起我的博客。
你们的关注就是我的动力，本节笔记到这里就结束了。
潇汀一有时间就会把自己的学习心得，觉得比较好的知识点写出来和大家一起分享。
编程开发的路很长很长，非常希望能和大家一起交流，共同学习，共同进步。
如果文章中有什么疏漏的地方，也请大家留言指正。也希望大家可以多留言来和我探讨编程相关的问题。
最后，谢谢你们一直的支持~~~
------------------------------------------
Country: China
Tel: +86-152******41
QQ: 451292510
E-mail: xiaoting_chen2010@163.com
------------------------------------------
C++完整个代码示例（代码在VS2005下测试可运行）
AL_QueuePriorityList.h
#ifdef TEST_AL_QUEUEPRIORITYLISTAL_QueuePriorityList<DWORD> cQueuePriorityList;BOOL bEmpty = cQueuePriorityList.IsEmpty();std::cout<<bEmpty<<std::endl;DWORD dwSize = cQueuePriorityList.Size();std::cout<<dwSize<<std::endl;DWORD dwFront = cQueuePriorityList.Front();std::cout<<dwFront<<std::endl;DWORD dwBack = cQueuePriorityList.Back();std::cout<<dwBack<<std::endl;DWORD dwPop = cQueuePriorityList.Pop();std::cout<<dwPop<<std::endl;cQueuePriorityList.Push(999);bEmpty = cQueuePriorityList.IsEmpty();std::cout<<bEmpty<<std::endl;dwSize = cQueuePriorityList.Size();std::cout<<dwSize<<std::endl;dwFront = cQueuePriorityList.Front();std::cout<<dwFront<<std::endl;dwBack = cQueuePriorityList.Back();std::cout<<dwBack<<std::endl;dwPop = cQueuePriorityList.Pop();std::cout<<dwPop<<std::endl;DWORD dwTestNum[]={14,10,56,7,83,22,36,91,3,47,72,0,91,100,7};for (DWORD dwCnt=0; dwCnt<(sizeof(dwTestNum)/sizeof(DWORD)); dwCnt++) {cQueuePriorityList.Push(dwTestNum[dwCnt]);dwBack = cQueuePriorityList.Back();std::cout<<dwTestNum[dwCnt]<<std::endl;}dwSize = cQueuePriorityList.Size();std::cout<<dwSize<<std::endl;for (DWORD dwCount=0; dwCount<dwSize; dwCount++) {dwPop = cQueuePriorityList.Pop();std::cout<<dwPop<<std::endl;}struct sMySelfData {BOOL operator > (sMySelfData sData) const{return this->dwPriority > sData.dwPriority;}DWORD dwPriority;DWORD dwValue;};// class sMySelfData {// public:// BOOL operator > (sMySelfData sData) const{// return this->dwPriority > sData.dwPriority;// }// DWORD dwPriority;// DWORD dwValue;// };bEmpty = cQueuePriorityList.IsEmpty();std::cout<<bEmpty<<std::endl;dwSize = cQueuePriorityList.Size();std::cout<<dwSize<<std::endl;dwFront = cQueuePriorityList.Front();std::cout<<dwFront<<std::endl;dwBack = cQueuePriorityList.Back();std::cout<<dwBack<<std::endl;dwPop = cQueuePriorityList.Pop();std::cout<<dwPop<<std::endl;//test myself datasMySelfData sData1;memset(&sData1, 0x00, sizeof(sMySelfData));sMySelfData sData2;memset(&sData1, 0x00, sizeof(sMySelfData));sMySelfData sData3;memset(&sData1, 0x00, sizeof(sMySelfData));sMySelfData sData4;memset(&sData1, 0x00, sizeof(sMySelfData));sData1.dwPriority = 1;sData1.dwValue = 1;sData2.dwPriority = 2;sData2.dwValue = 2;sData3.dwPriority = 3;sData3.dwValue = 3;sData4.dwPriority = 2;sData4.dwValue = 4;sMySelfData sData5;AL_QueuePriorityList<sMySelfData> cQueuePriorityListMy;cQueuePriorityListMy.Push(sData1);cQueuePriorityListMy.Push(sData2);cQueuePriorityListMy.Push(sData3);cQueuePriorityListMy.Push(sData4);dwSize = cQueuePriorityListMy.Size();std::cout<<dwSize<<std::endl;sMySelfData sData;memset(&sData, 0x00, sizeof(sMySelfData));for (DWORD dwCount=0; dwCount<dwSize; dwCount++) {memset(&sData, 0x00, sizeof(sMySelfData));sData = cQueuePriorityListMy.Pop();std::cout<<sData.dwPriority<<" "<<sData.dwValue<<std::endl;}#endif