國考資訊處理工作室(高考二級資訊處理/高考三級資訊處理/調查局三等/關務人員三等/地方特考三等)

二、利用鏈結串列 (Linked list) 實做佇列 (Queues)，給予如下鏈結串列節點及 佇列定義，front 指標指在串列第一個節點，rear 指標指在串列最後一個節點，請使用 C 語言完成 insert(pq, x) 程序，將整數值 x 加入 (Insert) 到佇列，程式需檢查佇列加入前是否為空的鏈結串列，可使用函數 getnode( ) 配置 (Allocate) 一新節點。（25分）

#include <stdio.h>

#include <stdlib.h>

struct node {

    int info;

    struct node* next;

};

typedef struct node* NODEPTR;

struct queue {

    NODEPTR front, rear;

};

struct queue q;

// 產生一個新節點

NODEPTR getnode( ) {

    NODEPTR p;

    p = (NODEPTR)malloc(sizeof(struct node));

    return(p);

}

// 產生一個空的佇列

struct queue* CreateQueue( ) {

   struct queue* q = (struct queue*)malloc(sizeof(struct queue));

    q->front = q->rear = NULL;

    return q;

}

void insert(struct queue* q, int x) {

    NODEPTR p = getnode( ); // 產生一個佇列節點

    p->info = x;

    p->next = NULL;

    if (q->rear == NULL) { // 如果佇列是空的，新的節點同時是 front 和 rear

        q->front = q->rear = p;

        return;

    }

    q->rear->next = p; // 加入一個新節點到佇列尾端

    q->rear = p; // 將 rear 指向新節點

}

int main( ) {

    struct queue* pq = CreateQueue( ); // 指向佇列的指標

    insert(pq, 2);

    insert(pq, 8);

    insert(pq, 5);

    printf("Queue Front:%d \n", pq->front->info);

    printf("Queue Rear:%d", pq->rear->info);

    return 0;

}