Java循環隊列

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

上圖中顯示的隊列已完全填滿，由于條件rear == max - 1變為真，因此無法再插入任何元素。

但是，如果刪除隊列前端的2個元素，仍然無法插入任何元素，因為條件rear = max -1仍然成立。

這是線性隊列的主要問題，雖然在數組中有空間可用，但是不能在隊列中插入任何更多的元素。這只是內存浪費，需要克服這個問題。

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

 

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

時間復雜性

操作
Front	O(1)
Rear	O(1)
enQueue()	O(1)
deQueue()	O(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

實現代碼如下所示

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;  
}

從循環隊列中刪除元素的算法

要從循環隊列中刪除元素，必須檢查以下三個條件。

• 如果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步：退出

完整實現的代碼如下

#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