数据结构之顺序队列的优化

￡神魔★判官ぃ 2022-05-31 06:57 208阅读 0赞

**顺序队列的优化**

我们既然想优化顺序队列，首先得知道目前顺序队列的瓶颈在哪里，那样才能对症下药。

**顺序队列的瓶颈：**

1.线性表的第一个元素作为队头，线性表的最后一个元素作为队尾；  
2.入队的新元素是在线性表的最后,时间复杂度为O(1)  
3.出队时需要将后续的所有元素向前移动，时间复杂度O(n)  
问题：如何将出队操作的时间复杂度降低到O(1)?

**顺序队列的优化方案**  
1.定义front使其始终代表队头的下标，出队时将队头元素返回，且front++；  
2.定义rear使其始终代表队尾下一个元素的下标，入队时将新元素插入，且rear++。  
没有必要只将下标为0的位置定义为队头！！

![70][]

队头元素: node\[4\] 队列长度：6

**顺序队列的关键状态**：  
1.初始状态：length == 0, front == 0, rear == 0;  
2.空队列状态：length == 0, front == rear;  
3.满队列状态：length == capacity, front == rear;

从关键状态我们发现，队列为空时或者满时都有front = rear，这样就不是很好判断队列的空和满的状态，但是这些都难不倒我们，我们可以通过两种方式来解决这个问题：1.另设一个标志位以区别队列的“空”还是“满”，就比如上面的length；2.少用一个元素空间，约定以“队列头指针在队列尾指针的下一位置上”作为队列呈“满”状态。满队列：front = (rear + 1) % capacity；空队列：front =rear。  
**循环使用队列中的空间**：  
1.入队：rear = (rear + 1) % capacity;

2.出队：front = (front + 1) % capacity;

下面我们看一下代码

创建队列

typedef unsigned int TSeqQueueNode;
    // 定义一个顺序队列结构体
    typedef struct _tag_SeqQueue
    {
        int capacity;
        int length;
        int front;
        int rear;
        TSeqQueueNode* node;
    } TSeqQueue;
    // 创建队列
    SeqQueue* SeqQueue_Create(int capacity) // O(1)
    {
        TSeqQueue* ret = NULL;
        // 队列容量合法性OK，为队列申请内存
        if( capacity >= 0 )
        {
            ret = (TSeqQueue*)malloc(sizeof(TSeqQueue) + sizeof(TSeqQueueNode) * capacity);
        }
        // 内存申请成功，定义空队列
        if( ret != NULL )
        {
            ret->capacity = capacity;
            ret->length = 0;
            ret->front = 0;
            ret->rear = 0;
            ret->node = (TSeqQueueNode*)(ret + 1);
        }
        
        return ret;
    }

从代码中看出，创建顺序队列和创建顺序表基本相似，就是多了ret->front = 0;和ret->rear = 0。

销毁队列和清空队列：

// 销毁队列
    void SeqQueue_Destroy(SeqQueue* queue) // O(1)
    {
        free(queue);
    }
    // 清空队列
    void SeqQueue_Clear(SeqQueue* queue) // O(1)
    {
        TSeqQueue* sQueue = (TSeqQueue*)queue;
        // 队列合法性检查OK
        if( sQueue != NULL )
        {
            sQueue->length = 0;
            sQueue->front = 0;
            sQueue->rear = 0;
        }
    }

还是和操作顺序表基本相似。

进队列代码

// 进队列
    int SeqQueue_Append(SeqQueue* queue, void* item) // O(1)
    {
    		// 定义顺序表队列变量，强制转换入口参数
        TSeqQueue* sQueue = (TSeqQueue*)queue;
    		// 入口参数合法性检查
        int ret = (sQueue != NULL) && (item != NULL);
        
        ret = ret && (sQueue->length + 1 <= sQueue->capacity);
        // 合法性检查OK，插入新元素，尾指针加1，队列长度加1
        if( ret )
        {
            sQueue->node[sQueue->rear] = (TSeqQueueNode)item;
            
            sQueue->rear = (sQueue->rear + 1) % sQueue->capacity;
            
            sQueue->length++;
        }
        
        return ret;
    }

出队列代码

// 出队列
    void* SeqQueue_Retrieve(SeqQueue* queue) // O(1)
    {
    		// 定义顺序表队列变量，强制转换入口参数
        TSeqQueue* sQueue = (TSeqQueue*)queue;
        // 取出队头元素
        void* ret = SeqQueue_Header(queue);
        // 取队头元素OK,头指针加1，队列长度减1
        if( ret != NULL )
        {
            sQueue->front = (sQueue->front + 1) % sQueue->capacity;
            
            sQueue->length--;
        }
        // 返回头元素地址
        return ret;
    }

获取对头元素、队列长度、队列容量

// 获取队头元素
    void* SeqQueue_Header(SeqQueue* queue) // O(1) 
    {
    		// 定义顺序表队列变量，强制转换入口参数
        TSeqQueue* sQueue = (TSeqQueue*)queue;
        void* ret = NULL;
        // 队列合法性检查OK，返回队列头元素地址
        if( (sQueue != NULL) && (sQueue->length > 0) )
        {
            ret = (void*)(sQueue->node[sQueue->front]);
        }
        
        return ret;
    }
    // 获取队列的长度
    int SeqQueue_Length(SeqQueue* queue) // O(1)
    {
    		// 定义顺序表队列变量，强制转换入口参数
        TSeqQueue* sQueue = (TSeqQueue*)queue;
        int ret = -1;
        
        // 队列合法性检查OK，返回队列长度
        if( sQueue != NULL )
        {
            ret = sQueue->length;
        }
        
        return ret;
    }
    // 获取队列的容量
    int SeqQueue_Capacity(SeqQueue* queue) // O(1)
    {
    		// 定义顺序表队列变量，强制转换入口参数
        TSeqQueue* sQueue = (TSeqQueue*)queue;
        int ret = -1;
        
        // 队列合法性检查OK，返回队列容量
        if( sQueue != NULL )
        {
            ret = sQueue->capacity;
        }
        
        return ret;
    }

测试代码

#include <stdio.h>
    #include <stdlib.h>
    #include "SeqQueue.h"
    
    /* run this program using the console pauser or add your own getch, system("pause") or input loop */
    
    int main(int argc, char *argv[]) 
    {
        SeqQueue* queue = SeqQueue_Create(6);
        int a[10] = {0};
        int i = 0;
        
        for(i=0; i<10; i++)
        {
            a[i] = i + 1;
            
            SeqQueue_Append(queue, a + i);
        }
        
        printf("Header: %d\n", *(int*)SeqQueue_Header(queue));
        printf("Length: %d\n", SeqQueue_Length(queue));
        printf("Capacity: %d\n", SeqQueue_Capacity(queue));
        
        while( SeqQueue_Length(queue) > 0 )
        {
            printf("Retrieve: %d\n", *(int*)SeqQueue_Retrieve(queue));
        }
        
        printf("\n");
        
        for(i=0; i<10; i++)
        {
            a[i] = i + 1;
            
            SeqQueue_Append(queue, a + i);
    
            printf("Retrieve: %d\n", *(int*)SeqQueue_Retrieve(queue));
        }
        
        SeqQueue_Destroy(queue);
        
    	return 0;
    }

到此也就完成了顺序队列的优化，整体代码请点击下方的链接。

[顺序队列的优化C实现][C]

[70]: /images/20220531/765d494179724e8398cf7b27fe5e3b57.png
[C]: http://download.csdn.net/download/u014754841/10248609