C語言的單連結清單實作隊列

隊列是一種FIFO（先入先出）的資料結構

C++的STL std::queue q; 相關的隊列操作，包括

q.empty() 判讀隊列是否為空
q.front() 傳回隊列的首元素
q.back() 傳回隊列的末尾元素
q.pop() 彈出隊列的頭部
q.push(x) 将x添加至隊列
q.size() 傳回隊列的大小      

本文使用C語言的連結清單，實作隊列以上操作(文末有測試代碼)

• ​

  ​empty​

  ​

bool empty(Queue *head){
    if (head == NULL)
        return true;
    else 
        return false;
}      

• ​

  ​front​

  ​ 取隊列的頭元素，即傳回連結清單的首節點

Queue front(Queue *head) {
    Queue fro;
    if (NULL == head) {
        fro.next = NULL;
        return fro;
    }
    fro.data = head->data;//傳回連結清單的首節點
    fro.next = head;
    return fro;
}      

• ​

  ​back​

  ​ 傳回隊列的尾元素，即傳回連結清單的尾節點

Queue back(Queue *head) {
    Queue back;
    if (NULL == head) {
        back.next = NULL;
        return back;
    }
    while (head -> next) //擷取到連結清單的尾節點
    {
        head = head ->next;
    }
    back.data = head->data;
    back.next = head;
    
    return back;
}      

• ​

  ​pop​

  ​ 彈出隊列的首元素，即删除連結清單的頭節點

Queue *pop(Queue *head) {
    if (head ->next == NULL || head == NULL)
        head = NULL;

    head = head ->next; //删除連結清單的頭節點
    return head;
}      

• ​

  ​push​

  ​ 插入指定元素到隊列，即向使用尾插法插入新節點到連結清單

Queue *push(Queue *head, Queue node) {
    if (head == NULL) {
        return NULL;
    }
    
    Queue *r = head;
    while(r -> next) { //擷取到連結清單的尾節點的上一個節點
        r = r -> next;
    }

    node.next = NULL;
    r ->next = &node; //使用尾插法，插入節點
    r = &node;

    return head;
}      

• ​

  ​size​

  ​ 傳回隊列的大小，計算連結清單的長度

int size(Queue *head) {
    int s_num = 0;
    if (head == NULL) {
        return s_num;
    }

    while (head)
    {
        s_num ++;
        head = head->next;       
    }
    return s_num;
}      

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

typedef struct  List
{
    int data;
    struct List *next;
}Queue;

void print_list(Queue *p) {
    if (NULL == p) {
        printf("link list is NULL\n");
        return ;
    }

    while (p)
    {
        printf("%d ", p -> data);
        p = p->next;
    }
    printf("\n");
}

Queue *insert_tail(int n) {
    Queue *head = (Queue *)malloc(sizeof(Queue));
    head ->next = NULL;
    Queue *r = head;
    while (n --)
    {
        Queue *p = (Queue *)malloc(sizeof(Queue));
        int tmp ;
        scanf("%d",&tmp);
        p -> data = tmp;

        p -> next = NULL;
        r -> next = p;
        r = p;
    }
    return head ->next;
}

Queue *pop(Queue *head) {
    if (head ->next == NULL || head == NULL)
        head = NULL;

    head = head ->next;
    return head;
}

Queue front(Queue *head) {
    Queue fro;
    if (NULL == head) {
        fro.next = NULL;
        return fro;
    }
    fro.data = head->data;
    fro.next = head;
    return fro;
}

Queue back(Queue *head) {
    Queue back;
    if (NULL == head) {
        back.next = NULL;
        return back;
    }
    while (head -> next)
    {
        head = head ->next;
    }
    back.data = head->data;
    back.next = head;
    
    return back;
}

Queue *push(Queue *head, Queue node) {
    if (head == NULL) {
        return NULL;
    }
    
    Queue *r = head;
    while(r -> next) {
        r = r -> next;
    }

    node.next = NULL;
    r ->next = &node;
    r = &node;

    return head;
}

bool empty(Queue *head){
    if (head == NULL)
        return true;
    else 
        return false;
}

int size(Queue *head) {
    int s_num = 0;
    if (head == NULL) {
        return s_num;
    }

    while (head)
    {
        s_num ++;
        head = head->next;       
    }
    return s_num;
}

int main() {
    printf("constuct queue \n");
    Queue *p = insert_tail(3);
    
    Queue node;
    node.data = 10;
    printf("push \n");
    Queue *q = push(p,node);
    print_list(q);

    printf("constuct queue \n");
    p = insert_tail(3);
    printf("pop \n");
    Queue *po = pop(p);
    print_list(po);

    printf("front %d\n",front(po).data);
    printf("size %d\n",size(po));
    printf("back %d\n",back(po).data);
    return 0;
}      

constuct queue 
1 2 3
push 
1 2 3 10 
constuct queue 
1 2 3
pop 
2 3 
front 2
size 2
back 3