Java循環(huán)隊(duì)列

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

上圖中顯示的隊(duì)列已完全填滿，由于條件rear == max - 1變?yōu)檎妫虼藷o法再插入任何元素。

但是，如果刪除隊(duì)列前端的2個(gè)元素，仍然無法插入任何元素，因?yàn)闂l件rear = max -1仍然成立。

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

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

 

當(dāng)front = -1和rear = max-1時(shí)，循環(huán)隊(duì)列將滿。循環(huán)隊(duì)列的實(shí)現(xiàn)類似于線性隊(duì)列的實(shí)現(xiàn)。只有在插入和刪除的情況下實(shí)現(xiàn)的邏輯部分與線性隊(duì)列中的邏輯部分不同。

時(shí)間復(fù)雜性

操作
Front	O(1)
Rear	O(1)
enQueue()	O(1)
deQueue()	O(1)

插入循環(huán)隊(duì)列

在隊(duì)列中插入元素有三種情況。

• If (rear + 1)%maxsize = front, 隊(duì)列已滿。在這種情況下，發(fā)生溢出，因此無法在隊(duì)列中執(zhí)行插入。

• If rear != max - 1, 然后rear將增加到 mod(maxsize)，新值將插入隊(duì)列的后端。

• If front != 0 and rear = max - 1, 那么這意味著隊(duì)列未滿，因此將rear的值設(shè)置為0并在那里插入新元素。

在循環(huán)隊(duì)列中插入元素的算法

第1步 : IF (REAR+1)%MAX = FRONT
    提示 " OVERFLOW "
    轉(zhuǎn)到第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

實(shí)現(xiàn)代碼如下所示

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

從循環(huán)隊(duì)列中刪除元素的算法

要從循環(huán)隊(duì)列中刪除元素，必須檢查以下三個(gè)條件。

• 如果front = -1，那么隊(duì)列中沒有元素，因此這將是下溢情況。

• 如果隊(duì)列中只有一個(gè)元素，在這種情況下，條件rear = front為真，因此，兩者都設(shè)置為-1并且隊(duì)列被完全刪除。

• 如果front = max -1則從前端刪除該值，將front的值設(shè)置為0。

• 否則，front的值增加1，然后刪除前端的元素。

算法

第1步：IF FRONT = -1
    提示 “UNDERFLOW”
    轉(zhuǎn)到第4步
    [IF結(jié)束]
第2步：設(shè)置VAL = QUEUE [FRONT]
第3步：如果FRONT = REAR
    SET FRONT = REAR = -1
    其他
    IF FRONT = MAX -1
    SET FRONT = 0
    其他
    SET FRONT = FRONT + 1
    [IF結(jié)束]
  [結(jié)束]
第4步：退出

完整實(shí)現(xiàn)的代碼如下

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

執(zhí)行上面示例代碼，得到以下結(jié)果

**********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