佇列的連結串列實現
本教學前一節中討論了陣列實現佇列的缺點，陣列實現不能用於實現佇列的大規模應用程式。陣列實現的替代方法之一是佇列的連結串列實現。
具有n個元素的佇列的連結表示的儲存要求是o(n)，而操作的時間要求是o(1)。
在連結佇列中，佇列的每個節點由兩部分組成，即資料部分和連結部分。佇列的每個元素都指向記憶體中的緊鄰下一個元素。
在連結佇列中，在儲存器中保持兩個指標，即front指標和rear指標。front指標包含佇列的起始元素的地址，而rear指標包含佇列的最後一個元素的地址。
插入和刪除分別在後端和前端執行。如果front和rear指標都是NULL，則表示佇列為空。
佇列的連結表示如下圖所示。
連結佇列上的操作
可以在連結佇列上實現兩種基本操作。操作是插入和刪除。
1. 插入操作
插入操作通過向佇列末尾新增元素來追加佇列。新元素將是佇列的最後一個元素。
首先，使用以下語句為新節點ptr分配記憶體。
ptr = (struct node *) malloc (sizeof(struct node));
存在將此新節點ptr插入連結佇列的兩種情況。
第1種情況，將元素插入到空佇列中。 在這種情況下，條件front = NULL變為true。 現在，新元素將作為佇列的唯一元素新增，前後指標的下一個指標都將指向NULL。
ptr -> data = item;
if(front == NULL)
{
front = ptr;
rear = ptr;
front -> next = NULL;
rear -> next = NULL;
}
第2種情況，佇列包含多個元素。 條件front = NULL變為false。 在這種情況下，需要更新rear指標，以便rear的下一個指標指向新節點ptr。 因為，這是一個連結佇列，因此還需要使rear指標指向新新增的節點ptr。 還需要將rear的next指標設為NULL。
rear -> next = ptr;
rear = ptr;
rear->next = NULL;
通過這種方式，元素被插入佇列中。 演算法和C實現如下。
演算法
第2步：為新節點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步：結束
C語言的實現
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變為true，在這種情況下，只需在控制台上編寫下溢並退出。
否則，將刪除指標前面指向的元素。 為此，將前指標指向的節點複製到指標ptr中。 現在，移動front指標，指向下一個節點並釋放節點ptr指向的節點。通過使用以下語句完成。
ptr = front;
front = front -> next;
free(ptr);
演算法和C語言函式給出如下 -
第1步：IF FRONT = NULL
提示「下溢」
轉到第5步
[結束]
第2步：設定PTR = FRONT
第3步：SET FRONT = FRONT - > NEXT
第4步：釋放PTR
第5步：結束
C語言實現程式碼 -
void delete (struct node *ptr)
{
if(front == NULL)
{
printf("UNDERFLOW\n");
return;
}
else
{
ptr = front;
front = front -> next;
free(ptr);
}
}
完整的C語言實現程式碼如下所示 -
#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;
}
}
}
執行上面範例程式碼，得到以下結果 -
***********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