2.3队列

╰+攻爆jí腚メ 2024-04-08 09:25 34阅读 0赞

### 什么是队列 ###

队列（queue）是一种先进先出（First In First Out， FIFO）的线性表。

!\[queue.png\]\[1\]

### 队列的表示 ###

队列也有顺序和链式两种表示方法。同样，我们可以将链式队列理解为一种特殊的链表，只允许在表头删除，在表尾插入。

/* 队列节点 */
    typedef struct queue_node {
        
        /* 后继节点 */
        struct queue_node *next;
        /* 值 */
        void *data;
    }queue_node;
    
    /* 队列本身 */
    typedef struct queue {
        
        /* 队头 */
        struct queue_node *head;
        /* 队尾 */
        struct queue_node *tail;
        /* 队列长度 */
        int length;
    }queue;

### 队列的操作 ###

通常来说，队列常用的操作也是插入和删除两种。为了方便理解，可以将执行删除的一端称为队头（head），执行插入操作的一端称为队尾（tail）。

### 函数清单 ###

下面是用于操作队列的函数名及其作用与复杂度

<table> 
 <thead> 
  <tr> 
   <th>函数</th> 
   <th>作用</th> 
   <th>算法复杂度</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>queue_create</td> 
   <td>创建新队列</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>queue_release</td> 
   <td>释放队列，以及队列中的节点</td> 
   <td>O(N)</td> 
  </tr> 
  <tr> 
   <td>queue_push_data</td> 
   <td>入队</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>queue_pull_data</td> 
   <td>出队</td> 
   <td>O(1)</td> 
  </tr> 
  <tr> 
   <td>queue_empty</td> 
   <td>释放队列中节点(头节点除外)，但不释放队列本身</td> 
   <td>O(N)</td> 
  </tr> 
 </tbody> 
</table>

### 创建新队列 ###

/* 创建队列 */
    queue *queue_create()
    {
        
        /* 创建一个队列 */
        queue *queue = (struct queue*)malloc(sizeof(struct queue));
        
        /* 为了方便操作，队列默认创建一个队列节点 */
        queue_node *node = (struct queue_node*)malloc(sizeof(struct queue_node));
        if(queue==NULL || node==NULL) return NULL;
    
        node->data = NULL;
        node->next = NULL;
        
        /* 初始化队列 */
        queue->head = queue->tail = node;
        queue->length = 0;
    
        return queue;
    }

在创建新队列时，首先创建队列本身，接着，创建一个队列节点（头节点），并将队列的`head`和`tail`指针都指向这个节点。最后，队列的长度设置为0。

!\[queue\_create.png\]\[2\]

### 入队 ###

/* 入队 */
    queue *queue_push_data(queue *queue, void *data)
    {
        
        /* 创建一个节点 */
        queue_node *node = (struct queue_node*)malloc(sizeof(struct queue_node));
        if(node==NULL) return NULL;
        node->data = data;
    
        /* 在队尾插入元素 */
        queue->tail->next = node;
        queue->tail = queue->tail->next;
    
        queue->length++;
        return queue;
    }

在有元素需要入队的时候，执行在表尾的插入操作。  
首先创建一个新的节点，接着让最后一个节点，也即队尾指针`tail`指向的节点的`next`指针指向新的节点，然后，队尾指针`tail`也指向新的节点。最后，队列长度自增1。

### 出队 ###

/* 出队 */
    void* queue_pull_data(queue *queue)
    {
        
        queue_node *current = queue->head->next;
        
        /* 判断队列中是否有数据 */
        if(current==NULL) return NULL;
    
        void *data = current->data;
        
        queue->head->next = current->next;
        
        /* 判断队列中除头结点外，是否只有一个节点，避免尾指针丢失 */
        if(queue->tail==current) {
        
            queue->tail = queue->head;
        }
    
        free(current);
        queue->length--;
        return data;
    }

有元素出队时，首先判断队列是否有数据，如果没有，则返回**NULL**，如果没有，则返回头节点的下一个节点（首元节点）的数据。  
接着，**判断队列中除头结点外，是否只有一个节点**。如果只有首元节点，那么下一步释放首元节点的内存时，`tail`指针将会被一同释放，进而造成尾指针的丢失。  
最后，释放出队的节点内存，队列长度自减1。

### 清空队列 ###

// 释放队列中所有节点，但不释放队列本身
    void queue_empty(queue *queue)
    {
           
        int length = queue->length;
        queue_node *current, *next;
    
        // 注意这里不释放头节点
        current = queue->head->next;
        while (length--)
        {
           
            next = current->next;
            free(current);
            current = next;
        }
        
        queue->head->next = NULL;
        queue->head->data = NULL;
        queue->tail = queue->head;
        queue->length = 0;
    }

释放队列的所有数据节点，但不释放头节点，所有循环从`head->next`开始。  
因为，`head->next`被`free`过，所以再次设置为`NULL`。  
最后，设置队列长度为0，释放完毕。

### 清除队列 ###

// 释放队列，包括队列中节点
    void queue_release(queue *queue)
    {
        
        queue_empty(queue);
        /* 注意，头节点也要释放 */
        free(queue->head);
        free(queue);
    }

在释放队列本身及其节点的时候，我们只需要调用`queue_empty`函数，再释放头节点和队列本身即可。

### 测试 ###

int main()
    {
        
        char a = 'a';
        char b = 'b';
        char c = 'c';
        
        queue *queue = queue_create();
        printf("%p\n", queue_pull_data(queue));
        
        queue_push_data(queue, &a);
        queue_push_data(queue, &b);
        queue_push_data(queue, &c);
    
        while (queue->length)
        {
        
            printf("%c\n", *(char *)queue_pull_data(queue));
        }
        
        queue_push_data(queue, &c);
        queue_push_data(queue, &c);
        
        /* 释放队列中节点 */
        queue_empty(queue);
        printf("%p\n", queue_pull_data(queue));
        
        /* 释放队列 */
        queue_release(queue);
        return 0;
    }