佇列的陣列實現


使用線性陣列可以很容易地表示佇列。 在每個佇列的情況下實現有兩個變數,即前面(front)和後面(rear)。 前後變數指向佇列中執行插入和刪除的位置。 最初,frontqueue的值為-1,表示空佇列。 包含5個元素的佇列的陣列表示以及前後的值如下圖所示。

上圖顯示了形成英文單詞「HELLO」的字元佇列。 因為,到目前為止在佇列中沒有執行刪除報操作,因此font的值保持為0。 但是,每次在佇列中執行插入時,rear的值都會增加1。 將元素插入上圖所示的佇列後,佇列將如下所示。 rear的值將變為5,而font的值保持不變。

刪除一個元素後,front的值將從0增加到1。當前,佇列內容將類似於如下。

1. 在佇列中插入元素的演算法

通過將rearmax - 1進行比較來檢查佇列是否已滿,如果是,則返回溢位錯誤。
如果要將資料項作為列表中的第一個元素插入,則在這種情況下將前後值設定為0並將元素插入後端。否則繼續增加rear的值並逐個插入每個元素,使用rear作為索引。

演算法

第1步:IF REAR = MAX - 1
    寫OVERFLOW
    轉到第4步
    [IF結束]
第2步:IF FRONT = -1且REAR = -1
    SET FRONT = REAR = 0
    其他
    SET REAR = REAR + 1
    [IF結束]
第3步:設定QUEUE [REAR] = NUM
第4步:退出

使用C語言實現以下演算法如下所示 -

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的值為-1front的值大於rear,則提示下溢資訊並退出。
否則,繼續增加前後的值並每次返回儲存在佇列前端的資料項。

演算法

第1步:IF FRONT = -1或FRONT> REAR
    提示溢位
    其他
    SET VAL = QUEUE [FRONT]
    SET FRONT = FRONT + 1
    [IF結束]
第2步:退出

C語言實現演算法,如下所示 -

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

完整的程式碼實現如下所示 -

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

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

*************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. 陣列實現的缺點

雖然,建立佇列很容易,但是使用這種技術來實現佇列存在一些缺點。

  • 記憶體浪費:陣列的空間(用於儲存佇列元素)永遠不能被重用來儲存該佇列的元素,因為元素只能插入前端而前面的值可能很高,所以, 在此之前的所有空間,永遠不會被填補。

    上圖顯示了如何在佇列的陣列表示中浪費記憶體空間。 在上圖中,示出了具有3個元素的大小為10的佇列。 front變數的值為5,因此,不能將值重新插入front位置之前已刪除元素的位置。 陣列的那麼多空間被浪費了,以後不能使用(對於這個佇列)。

  • 確定陣列大小
    關於陣列實現的最常見問題是需要事先宣告的陣列的大小。 由於佇列可以在執行時根據問題進行擴充套件,因此陣列大小的擴充套件是一個耗時的過程,並且由於發生了大量的重新分配,因此幾乎不可能在執行時執行。 由於這個原因,要宣告陣列足夠大,以便可以盡可能地儲存佇列元素,但這個宣告的主要問題是,大多數陣列插槽(接近一半)永遠不能被重用。 它將再次導致記憶體浪費。