佇列 - 使用鏈結實作(C語言動態記憶體宣告)


說明

使用陣列來實作佇列,會有佇列空間的限制,如果使用鏈結配合動態記憶體宣告,就不會有長度的限制。

解法

在使用鏈結實作佇列時,為了方便,使用一個空的節點來指向佇列前端第一個元素,這個空節點的data欄位並不儲存資料,而next當作front的角色,如下圖所示:
Link



為了配合以上的空節點,將佇列是否為空的判斷方式,改為front->next是否指向下一個節點來完成,如果front->next指向NULL,表示鏈結中已無下一個資料,所以佇列為空。

由於必須同時維護front與rear兩個資訊,而C語言一次只能傳回一個值,為了簡化程式邏輯,我們將front與rear宣告為全域變數,有興趣的話,請自己試著不設為全域變數來撰寫,這會讓程式變得複雜一些。

實作

  • C
#include <stdio.h> 
#include <stdlib.h>

struct node {
int data;
struct node *next;
};

typedef struct node Node;

void createq();
void showfront();
void addq(int);
void delq();
void showqueue();

Node *front, *rear;

int main(void) {
int input, select;

createq();

while(1) {
printf("\n\n請輸入選項(-1結束):");
printf("\n(1)插入值至佇列");
printf("\n(2)顯示佇列前端");
printf("\n(3)刪除前端值");
printf("\n(4)顯示所有內容");
printf("\n\$c>");
scanf("%d", &select);

if(select == -1)
break;

switch(select) {
case 1:
printf("\n輸入值:");
scanf("%d", &input);
addq(input);
break;
case 2:
showfront();
break;
case 3:
delq();
break;
case 4:
showqueue();
break;
default:
printf("\n選項錯誤!");
}
}

printf("\n");

return 0;
}

void createq() {
front = rear = (Node*) malloc(sizeof(Node));
front->next = rear->next = NULL;
}

void showfront(){
if(front->next == NULL)
printf("\n佇列為空!");
else
printf("\n頂端值:%d", front->next->data);
}

void addq(int data) {
Node *newnode;

newnode = (Node*) malloc(sizeof(Node));

if(front->next == NULL)
front->next = newnode;

newnode->data = data;
newnode->next = NULL;
rear->next = newnode;
rear = newnode;
}

void delq() {
Node* tmpnode;

if(front->next == NULL) {
printf("\n佇列已空!");
return;
}

tmpnode = front->next;
front->next = tmpnode->next;
free(tmpnode);
}

void showqueue() {
Node* tmpnode;

tmpnode = front->next;

printf("\n佇列內容:");
while(tmpnode != NULL) {
printf("%d ", tmpnode->data);
tmpnode = tmpnode->next;
}
}