数据结构之链式队列的优化

古城微笑少年丶 2022-05-31 06:57 250阅读 0赞

**链式队列的优化**

上一节我们讲了一下顺序队列的优化，本节我们讲一下链式队列的优化。同理，我们得先知道链式队列的瓶颈在哪里。

**链式队列的瓶颈**

1.线性表的第一个元素作为队头，线性表的最后一个元素作为队尾；2.入队的新元素是在线性表的最后，时间复杂度为O(n)；

3.出队的元素即链表的第一个元素，时间复杂度O(1)。  
问题：如何将入队操作的时间复杂度降低到O(1)?

**链式队列的优化方案**  
1.定义rear指针始终指向链表中的最后一个元素，入队时将新元素通过rear插入队尾，且将rear指向新元素；

2.定义front指针使其始终指向链表中的第一个元素，出队时将队头元素返回，且front指向front下一个元素。  
![70][]

**链式队列的关键状态**：  
空队列状态：front == NULL, rear == NULL;  
**关键操作**：  
1.入队：

1.1.rear->next= node;

1.2.rear =node;

1.3.node->next= NULL;

2. 出队：

2.1.front =front->next;

下面看一下实现代码：

创建链式队列

// 定义链式队列结点指针结构体
    typedef struct _tag_LinkQueueNode TLinkQueueNode;
    struct _tag_LinkQueueNode
    {
        TLinkQueueNode* next;
        void* item;
    };
    // 定义链式队列结构体
    typedef struct _tag_LinkQueue
    {
        TLinkQueueNode* front;
        TLinkQueueNode* rear;
        int length;
    } TLinkQueue;
    // 创建队列
    LinkQueue* LinkQueue_Create() // O(1)
    {
    		// 定义返回变量，并申请链式队列队头内存
        TLinkQueue* ret = (TLinkQueue*)malloc(sizeof(TLinkQueue));
        // 申请成功，参考空队列条件操作
        if( ret != NULL )
        {
            ret->front = NULL;
            ret->rear = NULL;
            ret->length = 0;
        }
        
        return ret;
    }

销毁队列和清空队列

// 销毁队列
    void LinkQueue_Destroy(LinkQueue* queue) // O(n)
    {
    	 // 清空队列，释放内存
        LinkQueue_Clear(queue);
        free(queue);
    }
    // 清空队列
    void LinkQueue_Clear(LinkQueue* queue) // O(n)
    {
    	  // 队列不为空时，所有元素出队列
        while( LinkQueue_Length(queue) > 0 )
        {
            LinkQueue_Retrieve(queue);
        }
    }

进队列

// 进队列
    int LinkQueue_Append(LinkQueue* queue, void* item) // O(1)
    {
    		// 定义链式队列结构变量，并强制转换入口参数
        TLinkQueue* sQueue = (TLinkQueue*)queue;
    		// 定义链式队列结点指针结构变量，并申请内存
        TLinkQueueNode* node = (TLinkQueueNode*)malloc(sizeof(TLinkQueueNode));
        // 合法性检查
        int ret = (sQueue != NULL ) && (item != NULL) && (node != NULL);
        // 合法性OK
        if( ret )
        {
        	  // 保存插入的元素
            node->item = item;
            // 如果当前不是空队列
            if( sQueue->length > 0 )
            {
                sQueue->rear->next = node;         // 队尾指针next指向新元素
                sQueue->rear = node;               // 将队尾指针rear指向新元素
                node->next = NULL;                 // 新元素next指向空指针
            }
            // 当前是空队列
            else
            {
                sQueue->front = node;              // 队头指针指front向新元素
                sQueue->rear = node;               // 将对尾指针rear指向新元素
                node->next = NULL;                 // 新元素next指向空指针
            }
            // 队列长度加1
            sQueue->length++;
        }
        // 内存申请失败，释放内存，防止内存泄漏
        if( !ret )
        {
            free(node);
        }
        
        return ret;
    }

出队列

// 出队列
    void* LinkQueue_Retrieve(LinkQueue* queue) // O(1)
    {
    		// 定义链式队列结构变量，并强制转换入口参数
        TLinkQueue* sQueue = (TLinkQueue*)queue;
    		// 定义链式队列结点指针结构变量
        TLinkQueueNode* node = NULL;
        void* ret = NULL;
        // 合法性检查OK
        if( (sQueue != NULL) && (sQueue->length > 0) )
        {
        		// 保存当前队列尾指针
            node = sQueue->front;            
            // 队列尾指针指向下一个元素
            sQueue->front = node->next;      
            // 返回当前队列元素地址
            ret = node->item;                
            // 释放当前队列元素内存
            free(node);                      
            // 队列长度减1
            sQueue->length--;                
            // 队列为空，按队列条件操作
            if( sQueue->length == 0 )
            {
                sQueue->front = NULL;
                sQueue->rear = NULL;
            }
        }
        
        return ret;
    }

获取队列头指针

// 获取队列头元素
    void* LinkQueue_Header(LinkQueue* queue) // O(1)
    {
    		// 定义链式队列结构变量，并强制转换入口参数
        TLinkQueue* sQueue = (TLinkQueue*)queue;
        void* ret = NULL;
        // 合法性检查OK,返回队列头元素地址
        if( (sQueue != NULL) && (sQueue->length > 0) )
        {
            ret = sQueue->front->item;
        }
        
        return ret;
    }

获取队列长度

// 获取队列长度
    int LinkQueue_Length(LinkQueue* queue) // O(1)
    {
    		// 定义链式队列结构变量，并强制转换入口参数
        TLinkQueue* sQueue = (TLinkQueue*)queue;
        int ret = -1;
        
        // 合法性检查OK,返回队列长度
        if( sQueue != NULL )
        {
            ret = sQueue->length;
        }
        
        return ret;
    }

验证测试代码

#include <stdio.h>
    #include <stdlib.h>
    #include "LinkQueue.h"
    
    /* run this program using the console pauser or add your own getch, system("pause") or input loop */
    
    int main(int argc, char *argv[]) 
    {
        LinkQueue* queue = LinkQueue_Create();
        int a[10] = {0};
        int i = 0;
        
        for(i=0; i<10; i++)
        {
            a[i] = i + 1;
            
            LinkQueue_Append(queue, a + i);
        }
        
        printf("Header: %d\n", *(int*)LinkQueue_Header(queue));
        printf("Length: %d\n", LinkQueue_Length(queue));
        
        LinkQueue_Clear(queue);
        
        while( LinkQueue_Length(queue) > 0 )
        {
            printf("Retrieve: %d\n", *(int*)LinkQueue_Retrieve(queue));
        }
        
        LinkQueue_Destroy(queue);
        
    	return 0;
    }

到此我们就完成了链式队列的优化，详细代码见下方链接：

[链式队列优化C实现代码][C]

[70]: /images/20220531/ccbc931e63044b8fad963748012e7b8b.png
[C]: http://download.csdn.net/download/u014754841/10248680