隊列的存儲實現
#include<stdio.h>
#include<stdbool.h>
#include<malloc.h>
typedef
int
typedata;
struct
node
{
struct
node
*prev,
*next;
typedata
data;
};
typedef
struct
node
node;
typedef
struct
node*
link;
//
============init_head===============
//
//頭節點的初始化
link
init_head(void)
{
link
head
=
(link)malloc(sizeof(node));
if(head
!=
NULL)
{
head->prev
=
head->next
=
head;
}
return
head;
}
//
============newnode
================
//
//創建新節點
link
newnode(typedata
data)
{
link
new
=
(link)malloc(sizeof(node));
if(new
!=
NULL)
{
//前趨指針和後趨指針都指向自己
new->prev
=
new->next
=
new;
new->data
=
data;
}
return
new;
}
//
=================is_empty================
//
bool
is_empty(link
head)
{
//為空時，頭節點的前趨指針和後趨指針都指向head（頭節點）
if((head->next==head)
&&
(head->prev==head))
return
true;
return
false;
}
//
================insert_tail
==================
//
void
insert_tail(link
head,
link
new)
{
if(is_empty(head))
{
//第一個節點插入
head->next
=
head->prev
=
new;
new->next
=
new->prev
=
head;
return
;
}
//除了第一個節點插入
new->prev
=
head->prev;
new->next
=
head;
new->prev->next
=
new;
new->next->prev
=
new;
}
//
================show
====================
//
void
show(link
head)
{
//為空時，直接返回
if(is_empty(head))
return
;
//遍歷整個鏈
link
tmp
=
head->next;
while(tmp
!=
head)
{
printf("%d\t",
tmp->data);
tmp
=
tmp->next;
}
printf("\n");
}
//
==============insert_opint
===============
//
void
insert_opint(link
end_node,
link
p)
{
p->prev
=
end_node;
p->next
=
end_node->next;
end_node->next->prev
=
p;
end_node->next
=
p;
}
//
================insertion_sort===========
//
//順序排序
void
insertion_sort(link
head)
{
if(is_empty(head))
return;
//把隊列分拆，頭節點和第一個節點為一個已排序的隊列，
//其他的節點逐個比較已排序隊列插
link
p
=
head->next->next;
head->prev->next
=
NULL;
head->next->next
=
head;
head->next->prev
=
head;
head->prev
=
head->next;
while(p
!=
NULL)
{
link
end_node
=
head->prev;
if(p->data
>
end_node->data)
{
link
tmp
=
p;
p
=
p->next;
insert_tail(head,
tmp);
}
else
{
while(end_node!=head
&&
p->data<end_node->data)
end_node
=
end_node->prev;
link
tmp
=
p;
p
=
p->next;
insert_opint(end_node,
tmp);
}
}
}
int
main(void)
{
link
head
=
init_head();
if(head
==
NULL)
{
printf("falure\n");
return
0;
}
typedata
data;
while(1)
{
if(scanf("%d",
&data)
!=
1
)
break;
link
new
=
newnode(data);
if(new
==
NULL)
{
printf("falure\n");
return
0;
}
insert_tail(head,
new);
show(head);
}
printf("the
figure
is:\n");
show(head);
insertion_sort(head);
show(head);
return
0;
}
㈡ 隊列的兩種存儲方式對比
隊列的兩種存儲方式分為消息投遞實時性：使用短輪詢方式，實時性取決於輪詢間隔時間：使用長輪詢，同寫入實時性一致，消息的寫入延時通常在幾個毫秒。總結：短輪詢：周期性的向服務提供方發起請求，獲取數據優點：前後端程序編寫比較容易。缺點：請求中有大半是無用，難於維護，浪費帶寬和伺服器資源；響應的結果沒有順序（因為是非同步請求，當發送的請求沒有返回結果的時候，後面的請求又被發送。而此時如果後面的請求比前面的請 求要先返回結果，那麼當前面的請求返回結果數據時已經是過時無效的數據了）。長輪詢：客戶端向伺服器發送請求，伺服器接到請求後保持住連接，直到有新消息才返回響應信息並關閉連接，客戶端處理完響應信息後再向伺服器發送新的請求。優點：在無消息的情況下不會頻繁的請求，耗費資源小。缺點：伺服器hold連接會消耗資源，難於管理維護。消費失敗重試Kafka：消費失敗不支持重試RocketMQ：消費失敗支持定時重試，每次重試間隔時間順延總結：kafka也可以通過編寫代碼來實現寫入和消費失敗的重試機制，這種要求需要用戶來編寫代碼實現，kafka只是提供了這種方式，但並不是他推薦的使用方式，他的設計模式上只是兼顧了這種情況，並不是重點。RocketMQ在設計上就考慮了這種情況，在提供的官方api中提供了重試的設置，用戶可以選擇多種模式的重試機制，以及自定義的重試邏輯，簡單場景下用戶只用設置一下參數即可。關於需要重試的場景例如充值類應用，當前時刻調用運營商網關，充值失敗，可能是對方壓力過多，稍後在調用就會成功，如支付寶到銀行扣款也是類似需求。這里的重試需要可靠的重試，即失敗重試的消息不因為Consumer宕機導致丟失。
㈢ 隊列的 2 種實現方式
隊列，是一個線性表，和數組，棧，鏈表類似。隊列和棧類似，戲稱「邊吃邊拉」。即 FIFO。
隊列和棧還有一個不同，棧只需維護一個棧頂指針，而隊列需要維護 2 個指針，隊首和隊尾。
隊列可以使用數組實現，例如 Java 類庫的 LinkedBlockingQueue，也可以使用數組實現，例如 Java 的 ArrayBlockingQueue。這里我們討論數組的實現。
通常使用數組實現，會使用循環數組，也稱 ringBuffer，好處是不用 數組進行遷移，另外，傳統實現，如果數組滿了，就不能再繼續插入了，即使前面還有空間，因此就需要剛剛說的 進行遷移。下面是最簡單的一個 Java 循環數組實現。
這個是一個標準的實現，但是存在一個問題：如果隊列長度是 8，那麼就只能存儲 7 個元素。原因下面分析。
這個圖，表示隊列為空，因為 put 指針和 get 指針，指向了同一個槽位。get 指針不能夠再繼續移動。
那如果表示滿了呢？
這個圖，get 指針在 5 槽位，put 指針 4 槽位，put 指針不能再繼續移動，否則會覆蓋 5 槽位的值。
由此我們得到公式：
isEmpty = put == get;
ifFull = (put + 1) % n == get;
所以，put 一定比 get 少在一個槽位。
當 put 在 7 這個槽位，get 在 0 這個槽位，他還能繼續放入元素在 7 這個位置嗎？答案是不能，因為我們通過 put + 1 % n == get 這個公式計算，如果 在 7 個槽位加入了元素，那麼 put 指針就會變成 0，問題來了，put 是 0 ，get 也是0。
而 isEmpty 的公式是 put == get。這個時候，就會發生判斷錯誤：原本是滿的，卻判斷是空的。
所以，這個實現導致必須有一個空位。當然，我們也可以把槽位加1，也就是把數組長度加 1，避免實際長度不符合預期，也可以避免這個問題。
通過上面的分析，我們知道了，如果不加上1，將導致 isEmpty 判斷錯誤。原因是如果 put 和 get 指針重合，我們無法區分到底是 滿了 還是 空了。因為我們判斷是滿還是空，利用的是指針。
如果不使用指針呢？使用一個計算器，例如，添加一個元素，計算器 + 1， 刪除一個元素，計算器 - 1. 是否可以呢？答案是可以的.
下面是具體實現：
我們判斷 ifEmpty ，使用 size == 0 判斷；判斷 isFull，使用 size == n 判斷，這樣就解決了這個問題。
隊列可以使用鏈表和數組實現，通常使用使用數組實現，效率高，不用搬移。使用循環數組，需要考慮的是 ifFull 判斷和 isEmpty 判斷。
這里我建議使用 size 這種方式，而不是 + 1 這種方式，為什麼呢？使用 size 這種方式，我們可以利用 & 運算來快速計算下標——只要用戶指定的隊列長度是 2 的冪次方。
如果使用 + 1 的方式，即使用戶指定的隊列長度是 2 的冪次方，也無法使用 & 運算快速獲取下標。
當然，我們也可以根據用戶指定的隊列長度是否為2 的冪次方，來覺得到底是使用 size 方式，還是使用 + 1 方式。
㈣ 隊列的存儲結構為什麼一般採用循環隊列的形式
循環隊列屬於邏輯結構,其實質還是順序存儲，只是使用指針進行首尾的聯結，其實現的存儲方式可以為分散的鏈表或是連續的線性表，與其邏輯結構實現功能無關