迴圈佇列

線性佇列而言，刪除和插入只能分別在前端(front)和後端(rear)執行。考慮下圖中顯示的佇列。

上圖中顯示的佇列已完全填滿，由於條件rear == max - 1變為真，因此無法再插入任何元素。
但是，如果刪除佇列前端的2個元素，仍然無法插入任何元素，因為條件rear = max -1仍然成立。

這是線性佇列的主要問題，雖然在陣列中有空間可用，但是不能在佇列中插入任何更多的元素。這只是記憶體浪費，需要克服這個問題。

這個問題的解決方案之一是迴圈佇列。在迴圈佇列中，第一個索引緊跟在最後一個索引之後。 可以考慮迴圈佇列，如下圖所示。

當front = -1和rear = max-1時，迴圈佇列將滿。迴圈佇列的實現類似於線性佇列的實現。只有在插入和刪除的情況下實現的邏輯部分與線性佇列中的邏輯部分不同。

時間複雜性

1. 插入迴圈佇列

在佇列中插入元素有三種情況。

• If (rear + 1)%maxsize = front, 佇列已滿。在這種情況下，發生溢位，因此無法在佇列中執行插入。
• If rear != max - 1, 然後rear將增加到 mod(maxsize)，新值將插入佇列的後端。
• If front != 0 and rear = max - 1, 那麼這意味著佇列未滿，因此將rear的值設定為0並在那裡插入新元素。

在迴圈佇列中插入元素的演算法

第1步 : IF (REAR+1)%MAX = FRONT
    提示 " OVERFLOW "
    轉到第4步
    [End OF IF]
第2步 : IF FRONT = -1 and REAR = -1
    SET FRONT = REAR = 0
    ELSE IF REAR = MAX - 1 and FRONT ! = 0
    SET REAR = 0
    ELSE
    SET REAR = (REAR + 1) % MAX
    [END OF IF]
第3步 : SET QUEUE[REAR] = VAL
第4步 : EXIT

C語言實現程式碼如下所示 -

void insert(int item, int queue[])  
{  
    if((rear+1)%maxsize == front)  
    {  
        printf("OVERFLOW");  
        return;  
    }  
    else if(front == -1 && rear == -1)  
    {  
        front = 0;  
        rear = 0;  
    }else if(rear == maxsize -1 && front != 0)   
    {  
        rear = 0;  
    }else   
    {  
        rear = (rear+1)%maxsize;  
    }  
    queue[rear] = item;  
}

2. 從迴圈佇列中刪除元素的演算法

要從迴圈佇列中刪除元素，必須檢查以下三個條件。

• 如果front = -1，那麼佇列中沒有元素，因此這將是下溢情況。
• 如果佇列中只有一個元素，在這種情況下，條件rear = front為真，因此，兩者都設定為-1並且佇列被完全刪除。
• 如果front = max -1則從前端刪除該值，將front的值設定為0。
• 否則，front的值增加1，然後刪除前端的元素。

演算法

第1步：IF FRONT = -1
    提示 「UNDERFLOW」
    轉到第4步
    [IF結束]
第2步：設定VAL = QUEUE [FRONT]
第3步：如果FRONT = REAR
    SET FRONT = REAR = -1
    其他
    IF FRONT = MAX -1
    SET FRONT = 0
    其他
    SET FRONT = FRONT + 1
    [IF結束]
  [結束]
第4步：退出

C語言完整實現的程式碼如下 -

#include<stdio.h>   
#include<stdlib.h>  
#define maxsize 5  
void insert();
void delete();
void display();
int front = -1, rear = -1;
int queue[maxsize];
void main()
{
    int choice;
    while (choice != 4)
    {
        printf("*************************Main Menu*****************************\n");
        printf("=================================================================\n");
        printf("1.insert an element\n2.Delete an element\n3.Display the queue\n4.Exit\n");
        printf("Enter your choice ?");
        scanf("%d", &choice);
        switch (choice)
        {
        case 1:
            insert();
            break;
        case 2:
            delete();
            break;
        case 3:
            display();
            break;
        case 4:
            exit(0);
            break;
        default:
            printf("Enter valid choice??\n");
        }
    }
}
void insert()
{
    int item;
    printf("Enter the element\n");
    scanf("%d", &item);
    if ((rear + 1) % maxsize == front)
    {
        printf("OVERFLOW");
        return;
    }
    else if (front == -1 && rear == -1)
    {
        front = 0;
        rear = 0;
    }
    else if (rear == maxsize - 1 && front != 0)
    {
        rear = 0;
    }
    else
    {
        rear = (rear + 1) % maxsize;
    }
    queue[rear] = item;
    printf("Value inserted ");
}
void delete()
{
    int item;
    if (front == -1 & rear == -1)
    {
        printf("UNDERFLOW\n");
        return;
    }
    else if (front == rear)
    {
        front = -1;
        rear = -1;
    }
    else if (front == maxsize - 1)
    {
        front = 0;
    }
    else
        front = front + 1;
}

void display()
{
    int i;
    if (front == -1)
        printf("Circular Queue is Empty!!!\n");
    else
    {
        i = front;
        printf("Circular Queue Elements are : \n");
        if (front <= rear) {
            while (i <= rear)
                printf("%d %d %d\n", queue[i++], front, rear);
        }
        else {
            while (i <= maxsize - 1)
                printf("%d %d %d\n", queue[i++], front, rear);
            i = 0;
            while (i <= rear)
                printf("%d %d %d\n", queue[i++], front, rear);
        }
    }
}

執行上面範例程式碼，得到以下結果 -

**********Main Menu**********

=============================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?1

Enter the element
1

Value inserted 
**********Main Menu**********

=============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?1

Enter the element
2

Value inserted 
**********Main Menu**********

=============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?1

Enter the element
3

Value inserted 
**********Main Menu**********

=============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?3

Circular Queue Elements are : 
1
2
3

**********Main Menu**********

=============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?2

**********Main Menu**********

=============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?1

Enter the element
4

Value inserted 
**********Main Menu**********

=============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?3

Circular Queue Elements are : 
2
3
4

**********Main Menu**********
=============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?1

Enter the element
1

OVERFLOW
**********Main Menu**********

=============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?

4