如何實現一個動態分配數組的隊列？

Question

我想用動態分配的數組實現隊列。這提出了一些我不確定如何處理的問題。如何檢查隊列是否爲空？我如何跟蹤一次在隊列中有多少個元素？

對於第二個問題，我想我可以創建一個變量來跟蹤在其隨時更新我使用realloc()隊列元素的數量的。不過，我歡迎其他人提出建議。

如果您有任何更多的考慮，我應該考慮的問題請出示他們。

Answer 1

通常情況下，你把一個指針變量到您的隊列的「頭部」。當這個指針爲空時，該列表爲空，如果不是，則指向第一個節點。

現在談談在特定時間內隊列中元素的數量，另一種解決方案是建議實際運行所有節點並計數，但取決於元素的數量，這可能會很慢。

Answer 2

爲您計數，只是不停的有多少元素已被插入

INSERT() { 
    //code to insert element 
    size++; 
} 

POP(){ 
    //code to remove element 
    size--; 
} 

SIZE(){ 
    return size; 
} 

下一頁youre去必須決定youre去使用插接件什麼樣的策略的引用計數。

大多數人只使用一個列表。由於隊列通常是FILO（First Out Last out）或LILO（Last last out），所以它可能會有點棘手。

名單只是這個

struct Node{ 
    T* Value; 
    ptr Next; 
} 

，你必須按順序一幫這些它創建了一個列表。每個插入將產生一個新節點，並且刪除將取出節點並重新附加列表。

Answer 3

這裏有一個非常簡單的基於陣列的FIFO隊列：

struct queue { 
    T *store;  // where T is the data type you're working with 
    size_t size; // the physical array size 
    size_t count; // number of items in queue 
    size_t head; // location to pop from 
    size_t tail; // location to push to 
}; 

struct queue q; 
q.store = malloc(sizeof *q.store * SIZE); 
if (q.store) 
{ 
    q.size = SIZE; 
    q.count = q.head = q.tail = 0; 
} 

要推一個項目，像做了以下內容：

int push(struct queue q, T new_value) 
{ 
    if (q.count == q.size) 
    { 
    // queue full, handle as appropriate 
    return 0; 
    } 
    else 
    { 
    q.store[q.tail] = new_value; 
    q.count++; 
    q.tail = (q.tail + 1) % q.size; 
    } 
    return 1; 
} 

持久性有機污染物類似

int pop(struct queue q, T *value) 
{ 
    if (q.count == 0) 
    { 
    // queue is empty, handle as appropriate 
    return 0; 
    } 
    else 
    { 
    *value = q.store[q.head]; 
    q.count--; 
    q.head = (queue.head + 1) % q.size; 
    } 

    return 1; 
} 

由於寫，這是一個「通告」隊列; head和tail指針將在項目從隊列中推入並彈出時環繞。

與任何辦法，這都有長處和短處。這很簡單，它避免了過多的內存管理（只分配後備存儲）。只是更新count比試圖從head和tail更簡單。

擴展後備存儲並不是那麼簡單;如果你的尾指針已經纏，你必須head後，一切轉變：

Before: 

+---+---+---+---+---+ 
| x | x | x | x | x | 
+---+---+---+---+---+ 
     ^^
      | | 
      | +--- head 
      +------- tail 

After:   
+---+---+---+---+---+---+---+---+---+---+ 
| x | x | x | | | | | | x | x | 
+---+---+---+---+---+---+---+---+---+---+ 
     ^     ^
      |      | 
      |      +--- head 
      +------- tail 

另外，如果你想要的東西不是一個簡單的FIFO更復雜，你可能會想使用不同的數據結構你的後臺商店。