【数据结构】 队列的简单理解和基本操纵

哥是痴情范儿

媒介：本章引见的次要内乱容是数据规划中行列的观点，并经由过程代码完成链式规划的行列。

---

文章目录

• 
  
  
  
  • 
    
    
    
    • 1.行列的根本观点
      
    • 
      
      
      
      • 1.1 行列的界说
        
      • 1.2 行列的特性
        
         
      
    • 2.行列的代码完成
      
    • 
      
      
      
      • 2.1 行列存储的阐明
        
      • 2.2 行列的界说
        
      • 2.3 行列的初初化
        
      • 2.4 行列的判空操纵
        
      • 2.5 行列的进队操纵
        
      • 2.6 行列的出队操纵
        
      • 2.7 行列的获得队尾元素操纵
        
      • 2.8 行列的获得队尾元素操纵
        
      • 2.9 行列的计较行列元素数量操纵
        
      • 2.10 行列的烧毁操纵
        
         
      
    • 3.源码链接
      
      
    
  
  

---

1.行列的根本观点

1.1 行列的界说

  只许可正在一端停止插进数据操纵，正在另外一端停止删除数据操纵的特别线性表，行列具有先辈先出的特征

---

1.2 行列的特性

  

• 行列是一种操纵受限的线性表
  
• 队头(尾)：许可删除的一端
  
• 队尾：许可插进的一端
  
• 空行列：出有元素的行列
  
• 删除操纵叫做出队,插进操纵叫做进队
  

---

2.行列的代码完成

法式名功用Queue.h函数声明Queue.c功用函数的界说test.c测试

---

2.1 行列存储的阐明

  front指针:指背队头元素
rear指针:指背队尾元素的下一个地位
空队时：rear == front
行列初初化：rear = front = 0
进队：队已谦时，先收值到队尾，再队尾指针减一
出队：队为空时，先与队头元素，再队头指针减一

---

2.2 行列的界说

  那里挑选完成链表链式规划的行列
  

• 链队素质上是一个同时带有队头指针、队尾指针的单链表
  
• 头指针指背队头结面
  
• 尾指针指背队尾结面
  
• 链式行列合适于数据元素变革较年夜的情况，没有存正在上溢
  
• 当利用多个行列时，最好利用链式行列，能够制止存储分派没有公允下的溢出成绩。
  

1. typedef int QDataType;
3. typedef struct QueueNode  //界说行列结面
4. {
5.     QDataType data;
6.     struct QueueNode* next;
7. }QueueNode;
9. typedef struct Queue   //界说行列
10. {
11.     QueueNode* head;  //队头
12.     QueueNode* tail;  //队尾
13. }Queue;

复造代码

---

2.3 行列的初初化

  间接初初化为NULL.

1. void QueueInit(Queue* pq)
2. {
3.     assert(pq);
4.     pq->head = pq->tail = NULL;
5. }

复造代码

---

2.4 行列的判空操纵

  只需头指针出有指背任何空间便阐明行列为空

1. bool QueueEmpty(Queue* pq)
2. {
3.     assert(pq);
4.    
5.     return pq->head == NULL;
6. }

复造代码

---

2.5 行列的进队操纵

  由于我们是链式规划，无需检查行列能否谦了，间接开拓一个新空间存储数据，背新结面的数据域赋值，然后**tail->next指背新结面**。

1. void QueuePush(Queue* pq, QDataType elem)
2. {
3.     assert(pq);
4.     QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
5.     if(newnode == NULL)
6.     {
7.         perror("空间申请:");
8.         exit(-1);
9.     }
10.     newnode->data = elem;
11.     newnode->next = NULL;
12.    
13.     //查抄行列能否为空
14.     pq->head == NULL ? (pq->tail = newnode ):(pq->tail->next = newnode,pq->tail = pq->tail->next);
15. }

复造代码

---

2.6 行列的出队操纵

  1.先断定能否是空队,保留下一个结面
  2.free开释头结面
  3.指背所保留的下一个结面
  （上述历程要当心呈现行列内乱元素局部浑完，pq->tail酿成家指针的状况）

1. void QueuePop(Queue* pq)
2. {
3.     assert(pq);
4.     assert(!QueueEmpty(pq));
5.    
6.     QueueNode* next = NULL;
7.    
8.     pq->head->next == NULL?
9.     (free(pq->head),pq->head = pq->tail = NULL):
10.     (next = pq->head->next, free(pq->head),pq->head = next);//制止家指针
11. }

复造代码

---

2.7 行列的获得队尾元素操纵

1. QDataType QueueFront(Queue* pq)
2. {
3.     assert(pq);
4.     assert(!QueueEmpty(pq)); //不克不及为空
5.    
6.     return pa->head->data;
7. }

复造代码

---

2.8 行列的获得队尾元素操纵

1. QDataType QueueBack(Queue* pq)
2. {
3.     assert(pq);
4.     assert(!QueueEmpty(pq)); //不克不及为空
5.    
6.     return pa->tail->data;
7. }

复造代码

---

2.9 行列的计较行列元素数量操纵

  间接遍历计数

1. int QueueSize(Queue* pq)
2. {
3.     assert(pq);
4.     int num = 0;
5.     QueueNode* cur = pq->head;
6.     while(cur)
7.     {
8.         num++;
9.         cur = cur->next;
10.     }
11.     return num;
12. }

复造代码

---

2.10 行列的烧毁操纵

  遍历free，最后记得置空

1. void QueueDestory(Queue* pq)
2. {
3.         assert(pq);
4.         QueueNode* cur = pq->head;
5.         while (cur)
6.         {
7.                 QueueNode* next = cur->next;
8.                 free(cur);
9.                 cur = next;
10.         }
11.         pq->head = pq->tail = NULL;
12. }

复造代码

---

3.源码链接

面击跳转源码堆栈

---

数据规划的行列内乱容到此设想结束了，感激您的浏览！！！假如内乱容对您有赞助的话，记得给我面个赞——做个脚不足喷鼻的人。

免责声明：假如进犯了您的权益，请联络站少，我们会实时删除侵权内乱容，感谢协作！