隊(duì)列的鏈表實(shí)現(xiàn)

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

具有n個(gè)元素的隊(duì)列的鏈接表示的存儲(chǔ)要求是o(n)，而操作的時(shí)間要求是o(1)。

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

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

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

鏈接隊(duì)列上的操作

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

1、插入操作

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

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

隊(duì)列的鏈接表示如下圖所示。

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

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

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

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

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

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

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

算法

第2步：為新節(jié)點(diǎn)PTR分配空間
第2步：設(shè)置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
    [結(jié)束]
第4步：結(jié)束

實(shí)現(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、刪除

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

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

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

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

第1步：IF FRONT = NULL
    提示“下溢”
    轉(zhuǎn)到第5步
    [結(jié)束]
第2步：設(shè)置PTR = FRONT
第3步：SET FRONT = FRONT - > NEXT
第4步：釋放PTR
第5步：結(jié)束

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

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

完整的實(shí)現(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í)行上面示例代碼，得到以下結(jié)

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