隊列這個概念非常好了解。你可以把它想象成排隊買票，先來的先買，後來的人隻能站末尾，不允許插隊。先進者先出，這就是典型的“隊列”。
我們知道，棧隻支援兩個基本操作：入棧 push()和出棧 pop()。隊列跟棧非常相似，支援的操作也很有限，最基本的操作也是兩個：入隊 enqueue()，放一個資料到隊列尾部；出隊 dequeue()，從隊列頭部取一個元素。
是以，
隊列(Queue)是允許在一端進行插入操作，而在另一端進行删除操作的線性表。
1.2.其它概念隊列是一種
先進先出(First In First Out，
FIFO)的線性表，在一端進行元素插入是
隊頭(front)，在另一端進行删除元素是
隊尾(rear)。
2.為什麼不要實作順序隊列？實作順序隊列時，可能出現下述三種"
溢出"的現象：
- “下溢”： 隊列為空時進行出隊；
- “真上溢”：隊列已滿時進行入隊；
- “假上溢”：對于順序隊列來說，由于删除元素時隊首指針增加，造成空間閑置，此時隊列的存儲元素數量總是小于實際容量；
解決“假溢出”問題1——循環隊列
循環隊列的定義：首尾相連的順序存儲結構稱為循環隊列。
即将隊列的頭尾相接，形成一個圓，聲明兩個指針，一個帶邊隊頭，一個代表隊尾，入隊和出隊的時候，直接操作對應的指針即可。
循環隊列的一些操作：
初始隊列：front=rear=0(或1)
空隊列：front==rear隊滿條件：(rear+1)%queuesize==front
進隊操作：rear=(rear+1)%queuesize
出隊操作：front=(front+1)%queuesize
隊列的大小：(rear-front+queuesize)%queuesize
解決“溢出”問題2——鍊隊
若使用鍊式存儲結構則不存在“溢出”現象，因為連結清單的節點建立和删除都是動态進行的，即在連結清單的一端進行插入，另一端進行删除，隻要允許連結清單不斷申請記憶體空間即可。
以c++實作一個循環隊列：
以c++實作一個鍊隊：
偷懶結合使用c++STL中的list。
時間複雜度：O(1)，所有方法都具有恒定的時間複雜度。
空間複雜度：O(N)，與數組實作相同。但是連結清單實作方式的記憶體效率更高。
6.用數組或連結清單實作隊列的比較a.數組
優點：存儲單元是連續的，存儲空間使用率高。無需為了存儲各機關之間的關系添加額外開銷。可以按照索引随機通路。
缺點：插入、删除操作時，操作的位置越靠近頭部效率越低。需要預先配置設定足夠大的記憶體空間，記憶體空間過小則溢出，空間過大則浪費資源。
b.連結清單
優點：插入、删除操作友善，隻需要修改相鄰節點的指向即可。存儲空間是動态的，不會溢出也不會有閑置空間。
缺點：需要額外空間來存儲每個節點的指向關系。存儲單元碎片化，空間使用率不高。查詢代價較高，必須從頭開始查找。
是以，在可以确定隊列長度最大值的情況下，建議用循環隊列； 如果無法預估隊列的長度，則使用鍊隊。
yaoshanxia/資料結構與算法c++gitee.com