沒有浪費條目或使用計數器的循環隊列

Question

是否有可能通過使用array來實現循環隊列，而沒有計數器來計數隊列中的項目數或不浪費陣列的任何條目？

我想什麼：

這是不可能的，讓我們假設我們有兩個指針front和rear，第一個點到隊列的第一個元素，

我們可以定義後指針方法有兩種：

1.It點向其中插入到隊列的最後一個元素，那麼下一個條目是要插入的下一個元素可能的地方

2.它指向下一個元素將要插入的位置

無論哪種情況，我們都無法區分完整的&空隊列如果我們不浪費至少一個數組的條目或者我們不' t保留一個計數器the number of inserted - number of deleted elements

Answer 1

正如我曾經實施它，我用了一個額外的布爾稱爲'空'。 你是對的，在兩個指針都在同一位置的情況下，無法區分。

根據您使用的指針，您可以使用一個指針的最低位來存儲空變量。
如果size是一個變量整數，那麼也可以使用負值來指示隊列中沒有元素。

Answer 2

另一種方法是使用三個指針，其中第三個指針指向兩個指針之間的位置。有很多方法可以實施。但要注意的關鍵是中間指針只需要告訴以下兩件事。

• 隊列爲空。所有指針指向相同的地方（後指針的第二個定義）。
• 該隊列有1個元素，刪除元素將使其爲空。中間指針和另一個指針指向相同的地方。

這可以簡單地通過保持中間指針在第一個和最後一個之間，並且從第一個或最後一個指針偏移一個來完成，只要該隊列有一個或多個元素。

這可能充其量只是使用計數器略有改進，甚至可能是最差的。

Answer 3

您的疑慮通常被認爲是循環隊列的full vs. empty difficulty。引用：

爲了解決這種混亂有一些解決方案：

1. 始終保持一個槽開度。
2. 使用填充計數來區分這兩種情況。
3. 使用額外的鏡像位來區分這兩種情況。
4. 使用讀寫計數從中獲取填充計數。
5. 使用絕對指數。
6. 記錄上次操作。

你在問題中直接提到的數字1,2和4。除了數組和指針/指針之外，它們還會佔用一定數量的內存和開始/結束（或前後）。其他解決方案也會消耗內存。

＃3 - 使用鏡像位

只增加了一個額外的布爾或枚舉，實質上isEmpty或isFull。這種方法的想法，邏輯和證明是more complicated。

＃5 - absoulte指數時執行操作，從不降低

指數遞增。它們基本上是每種類型操作數量的計數器。這有other drawbacks。

＃6 - 記錄最後一次操作

基本相同，＃3，但不同的語義。

無論如何，所有這些鏈接都是維基百科的文章。我強烈推薦它。可能還有其他方法，但在您的文章中列出的6種方法之一中很難改進。它們都有缺點和優點，所以在決定實施之前仔細考慮預期的用例。

Answer 4

在開始時，讓first = 0，rear = -1;

我們添加下面的方式..... array [rear];後部=（後部+ 1）％MAX;

我們按照以下方法將其刪除.. array [front];前面=（前+ 1）％MAX;

，同時除去從數組的元素，我們可以把它如下之後添加一個條件...
if(front==rear+1) first=0, rear=-1

然後空條件可以被給定爲...

if(rear==-1) printf("Empty"); 

的全情況將然後...

if ((front==(rear+1) || (front==0 && rear==(n-1)) && rear!=-1) printf("Full"); 

這可能工作。沒有使用「count」功能