隊(duì)列是一種FIFO（先入先出）的數(shù)據(jù)結(jié)構(gòu)
C++的STL std::queue q; 相關(guān)的隊(duì)列操作，包括

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

本文使用C語言的鏈表，實(shí)現(xiàn)隊(duì)列以上操作(文末有測試代碼)

• empty

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

• front 取隊(duì)列的頭元素，即返回鏈表的首節(jié)點(diǎn)

  Queue front(Queue *head) {Queue fro;if (NULL == head) {fro.next = NULL;return fro;}fro.data = head->data;//返回鏈表的首節(jié)點(diǎn)fro.next = head;return fro;
  }
  

• back 返回隊(duì)列的尾元素，即返回鏈表的尾節(jié)點(diǎn)

  Queue back(Queue *head) {Queue back;if (NULL == head) {back.next = NULL;return back;}while (head -> next) //獲取到鏈表的尾節(jié)點(diǎn){head = head ->next;}back.data = head->data;back.next = head;return back;
  }
  

• pop 彈出隊(duì)列的首元素，即刪除鏈表的頭節(jié)點(diǎn)

  Queue *pop(Queue *head) {if (head ->next == NULL || head == NULL)head = NULL;head = head ->next; //刪除鏈表的頭節(jié)點(diǎn)return head;
  }
  

• push 插入指定元素到隊(duì)列，即向使用尾插法插入新節(jié)點(diǎn)到鏈表

  Queue *push(Queue *head, Queue node) {if (head == NULL) {return NULL;}Queue *r = head;while(r -> next) { //獲取到鏈表的尾節(jié)點(diǎn)的上一個節(jié)點(diǎn)r = r -> next;}node.next = NULL;r ->next = &node; //使用尾插法，插入節(jié)點(diǎn)r = &node;return head;
  }
  

• size 返回隊(duì)列的大小，計(jì)算鏈表的長度

  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

總結(jié)

以上是生活随笔為你收集整理的C语言的单链表实现队列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。