隊列的數(shù)組實現(xiàn)

使用線性數(shù)組可以很容易地表示隊列。 在每個隊列的情況下實現(xiàn)有兩個變量，即前面(front)和后面(rear)。 前后變量指向隊列中執(zhí)行插入和刪除的位置。 最初，front和queue的值為-1，表示空隊列。 包含5個元素的隊列的數(shù)組表示以及前后的值如下圖所示。

上圖顯示了形成英文單詞“HELLO”的字符隊列。 因為，到目前為止在隊列中沒有執(zhí)行刪除報操作，因此font的值保持為0。 但是，每次在隊列中執(zhí)行插入時，rear的值都會增加1。 將元素插入上圖所示的隊列后，隊列將如下所示。 rear的值將變?yōu)?，而font的值保持不變。

刪除一個元素后，front的值將從0增加到1。當前，隊列內(nèi)容將類似于如下。

1、在隊列中插入元素的算法

通過將rear與max - 1進行比較來檢查隊列是否已滿，如果是，則返回溢出錯誤。

如果要將數(shù)據(jù)項作為列表中的第一個元素插入，則在這種情況下將前后值設(shè)置為0并將元素插入后端。否則繼續(xù)增加rear的值并逐個插入每個元素，使用rear作為索引。

算法

第1步：IF REAR = MAX - 1
    寫OVERFLOW
    轉(zhuǎn)到第4步
    [IF結(jié)束]
第2步：IF FRONT = -1且REAR = -1
    SET FRONT = REAR = 0
    其他
    SET REAR = REAR + 1
    [IF結(jié)束]
第3步：設(shè)置QUEUE [REAR] = NUM
第4步：退出

實現(xiàn)以下算法如下所示：

void insert (int queue[], int max, int front, int rear, int item)   
{  
    if (rear + 1 == max)  
    {  
        printf("overflow");  
    }  
    else  
    {  
        if(front == -1 && rear == -1)  
        {  
            front = 0;  
            rear = 0;  
        }  
        else  
        {  
            rear = rear + 1;   
        }  
        queue[rear]=item;  
    }  
}

2、從隊列中刪除元素的算法

如果front的值為-1或front的值大于rear，則提示下溢信息并退出。

否則，繼續(xù)增加前后的值并每次返回存儲在隊列前端的數(shù)據(jù)項。

算法

第1步：IF FRONT = -1或FRONT> REAR
    提示溢出
    其他
    SET VAL = QUEUE [FRONT]
    SET FRONT = FRONT + 1
    [IF結(jié)束]
第2步：退出

實現(xiàn)算法，如下所示：

int delete (int queue[], int max, int front, int rear)  
{  
    int y;   
    if (front == -1 || front > rear)   

    {  
        printf("underflow");  
    }  
    else   
    {  
        y = queue[front];  
        if(front == rear)  
        {  
            front = rear = -1;  
            else   
            front = front + 1;   

        }  
        return y;  
    }  
}

完整的代碼實現(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("\nEnter the element\n");
    scanf("\n%d", &item);
    if (rear == maxsize - 1)
    {
        printf("OVERFLOW\n");
        return;
    }
    if (front == -1 && rear == -1)
    {
        front = 0;
        rear = 0;
    }
    else
    {
        rear = rear + 1;
    }
    queue[rear] = item;
    printf("Value inserted ");

}
void delete()
{
    int item;
    if (front == -1 || front > rear)
    {
        printf("UNDERFLOW\n");
        return;

    }
    else
    {
        item = queue[front];
        if (front == rear)
        {
            front = -1;
            rear = -1;
        }
        else
        {
            front = front + 1;
        }
        printf("value deleted ");
    }


}

void display()
{
    int i;
    if (rear == -1)
    {
        printf("Empty queue\n");
    }
    else
    {
        printf("printing values .....\n");
        for (i = front;i <= rear;i++)
        {
            printf("\n%d\n", queue[i]);
        }
    }
}

執(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
123

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
90

Value inserted 

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

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

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

Enter your choice ?2

value deleted 

*************Main Menu**************
==============================================

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

Enter your choice ?3

printing values .....

90

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

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

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

Enter your choice ?4

3、數(shù)組實現(xiàn)的缺點

雖然，創(chuàng)建隊列很容易，但是使用這種技術(shù)來實現(xiàn)隊列存在一些缺點。

• 內(nèi)存浪費：數(shù)組的空間(用于存儲隊列元素)永遠不能被重用來存儲該隊列的元素，因為元素只能插入前端而前面的值可能很高，所以， 在此之前的所有空間，永遠不會被填補。

上圖顯示了如何在隊列的數(shù)組表示中浪費內(nèi)存空間。 在上圖中，示出了具有3個元素的大小為10的隊列。 front變量的值為5，因此，不能將值重新插入front位置之前已刪除元素的位置。 數(shù)組的那么多空間被浪費了，以后不能使用(對于這個隊列)。

• 確定數(shù)組大小

關(guān)于數(shù)組實現(xiàn)的最常見問題是需要事先聲明的數(shù)組的大小。 由于隊列可以在運行時根據(jù)問題進行擴展，因此數(shù)組大小的擴展是一個耗時的過程，并且由于發(fā)生了大量的重新分配，因此幾乎不可能在運行時執(zhí)行。 由于這個原因，要聲明數(shù)組足夠大，以便可以盡可能地存儲隊列元素，但這個聲明的主要問題是，大多數(shù)數(shù)組插槽(接近一半)永遠不能被重用。 它將再次導(dǎo)致內(nèi)存浪費。