隊列的鏈表實現(xiàn)

本教程前一節(jié)中討論了數(shù)組實現(xiàn)隊列的缺點，數(shù)組實現(xiàn)不能用于實現(xiàn)隊列的大規(guī)模應用程序。數(shù)組實現(xiàn)的替代方法之一是隊列的鏈表實現(xiàn)。

具有n個元素的隊列的鏈接表示的存儲要求是o(n)，而操作的時間要求是o(1)。

在鏈接隊列中，隊列的每個節(jié)點由兩部分組成，即數(shù)據(jù)部分和鏈接部分。隊列的每個元素都指向內存中的緊鄰下一個元素。

在鏈接隊列中，在存儲器中保持兩個指針，即front指針和rear指針。front指針包含隊列的起始元素的地址，而rear指針包含隊列的最后一個元素的地址。

插入和刪除分別在后端和前端執(zhí)行。如果front和rear指針都是NULL，則表示隊列為空。

鏈接隊列上的操作

可以在鏈接隊列上實現(xiàn)兩種基本操作。操作是插入和刪除。

1、插入操作

插入操作通過向隊列末尾添加元素來追加隊列。新元素將是隊列的最后一個元素。

首先，使用以下語句為新節(jié)點ptr分配內存。

隊列的鏈接表示如下圖所示。

ptr = (struct node *) malloc (sizeof(struct node));

存在將此新節(jié)點ptr插入鏈接隊列的兩種情況。

第1種情況，將元素插入到空隊列中。 在這種情況下，條件front = NULL變?yōu)閠rue。 現(xiàn)在，新元素將作為隊列的唯一元素添加，前后指針的下一個指針都將指向NULL。

ptr -> data = item;  
if(front == NULL)  
{  
    front = ptr;  
    rear = ptr;    
    front -> next = NULL;  
    rear -> next = NULL;  
}

第2種情況，隊列包含多個元素。 條件front = NULL變?yōu)閒alse。 在這種情況下，需要更新rear指針，以便rear的下一個指針指向新節(jié)點ptr。 因為，這是一個鏈接隊列，因此還需要使rear指針指向新添加的節(jié)點ptr。 還需要將rear的next指針設為NULL。

rear -> next = ptr;  
rear = ptr;  
rear->next = NULL;

通過這種方式，元素被插入隊列中。 算法和C實現(xiàn)如下。

算法

第2步：為新節(jié)點PTR分配空間
第2步：設置PTR - > DATA = VAL
第3步：IF FRONT = NULL
    SET FRONT = REAR = PTR
    SET FRONT - > NEXT = REAR - > NEXT = NULL
    其他
    SET REAR - > NEXT = PTR
    SET REAR = PTR
    SET REAR - > NEXT = NULL
    [結束]
第4步：結束

實現(xiàn)：

void insert(struct node *ptr, int item; )  
{
    ptr = (struct node *) malloc (sizeof(struct node));  
    if(ptr == NULL)  
    {  
        printf("OVERFLOW\n");  
        return;  
    }else  
    {   
        ptr -> data = item;  
        if(front == NULL)  
        {  
            front = ptr;  
            rear = ptr;   
            front -> next = NULL;  
            rear -> next = NULL;  
        }else
        {  
            rear -> next = ptr;  
            rear = ptr;  
            rear->next = NULL;  
        }  
    }  
}

2、刪除

刪除操作將刪除在隊列所有元素中第一個插入的元素。 首先，需要檢查鏈表是否為空。 如果鏈表為空，則條件front == NULL變?yōu)閠rue，在這種情況下，只需在控制臺上編寫下溢并退出。

否則，將刪除指針前面指向的元素。 為此，將前指針指向的節(jié)點復制到指針ptr中。 現(xiàn)在，移動front指針，指向下一個節(jié)點并釋放節(jié)點ptr指向的節(jié)點。通過使用以下語句完成。

ptr = front;  
front = front -> next;  
free(ptr);

算法和函數(shù)給出如下：

第1步：IF FRONT = NULL
    提示“下溢”
    轉到第5步
    [結束]
第2步：設置PTR = FRONT
第3步：SET FRONT = FRONT - > NEXT
第4步：釋放PTR
第5步：結束

實現(xiàn)代碼如下：

void delete (struct node *ptr)  
{  
    if(front == NULL)  
    {  
        printf("UNDERFLOW\n");  
        return;  
    }  
    else   
    {  
        ptr = front;  
        front = front -> next;  
        free(ptr);  
    }  
}

完整的實現(xiàn)代碼如下所示：

#include<stdio.h>   
#include<stdlib.h>  
struct node
{
    int data;
    struct node *next;
};
struct node *front;
struct node *rear;
void insert();
void delete();
void display();
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()
{
    struct node *ptr;
    int item;

    ptr = (struct node *) malloc(sizeof(struct node));
    if (ptr == NULL)
    {
        printf("OVERFLOW\n");
        return;
    }
    else
    {
        printf("Enter value?\n");
        scanf("%d", &item);
        ptr->data = item;
        if (front == NULL)
        {
            front = ptr;
            rear = ptr;
            front->next = NULL;
            rear->next = NULL;
        }
        else
        {
            rear->next = ptr;
            rear = ptr;
            rear->next = NULL;
        }
    }
}
void delete ()
{
    struct node *ptr;
    if (front == NULL)
    {
        printf("UNDERFLOW\n");
        return;
    }
    else
    {
        ptr = front;
        front = front->next;
        free(ptr);
    }
}
void display()
{
    struct node *ptr;
    ptr = front;
    if (front == NULL)
    {
        printf("Empty queue\n");
    }
    else
    {
        printf("printing values .....\n");
        while (ptr != NULL)
        {
            printf("%d\n", ptr->data);
            ptr = ptr->next;
        }
    }
}

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

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

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

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

Enter your choice ?1

Enter value?
123

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

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

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

Enter your choice ?1

Enter value?
90

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

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

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

Enter your choice ?3

printing values .....

123

90

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

printing values .....

90

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

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

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

Enter your choice ?4