数据结构之队列的定义与简单实现

布满荆棘的人生 2022-05-31 06:56 149阅读 0赞

#### **队列的定义与简单实现** ####

和栈相反，队列是一种**先进先出（FIFO）**的线性表，队列仅在线性表的两端进行操作：  
1.队头(Front)：取出数据元素的一端；

2.队尾(Rear)：插入数据元素的一端。

![70][]

现实中，队列的例子也有很多，比如：银行排队办业务，食堂排队打饭等。

既然队列也是一种线性表，那么理论上也应该有线性表该有的操作。

队列的一些常用操作：  
1.创建队列；  
2.销毁队列；  
3.清空队列；  
4.进队列；  
5.出队列；  
6.获取队头元素；  
7.获取队列的长度。

队列通常有两种实现方式：

1.顺序结构实现；

![70 1][]

2. 链式结构实现。

![70 2][]

或许有人已经发现本节开头说的队列是与栈相反的特殊线性表，那么队列的实现不就是将栈反过来吗？BINGO，就是这个道理。

回顾前面栈实现的方式，我们知道顺序栈是通过从尾部插入元素，尾部取出元素来实现后进先出的；链式栈是通过从头部插入元

素，头部取出元素来实现后进先出的。

所以这里队列的顺序实现就应该是从尾部插入元素，头部取出元素；链式实现方式也应该是从尾部插入元素，头部取出元素。这

样就可以实现先进先出了，可以通过复用顺序表和的单链表来实现。

首先看一下顺序队列的实现代码：

#include "SeqList.h"
    #include "SeqQueue.h"
    // 创建队列
    SeqQueue* SeqQueue_Create(int capacity) // O(1)
    {
        return SeqList_Create(capacity);
    }
    // 销毁队列
    void SeqQueue_Destroy(SeqQueue* queue) // O(1)
    {
        SeqList_Destroy(queue);
    }
    // 清空队列
    void SeqQueue_Clear(SeqQueue* queue) // O(1)
    {
        SeqList_Clear(queue);
    }
    // 进队列
    int SeqQueue_Append(SeqQueue* queue, void* item) // O(1)
    {
        return SeqList_Insert(queue, item, SeqList_Length(queue));
    }
    // 出队列
    void* SeqQueue_Retrieve(SeqQueue* queue) // O(n)
    {
        return SeqList_Delete(queue, 0);
    }
    // 获取队头元素
    void* SeqQueue_Header(SeqQueue* queue) // O(1) 
    {
        return SeqList_Get(queue, 0);
    }
    // 获取队列的长度
    int SeqQueue_Length(SeqQueue* queue) // O(1)
    {
        return SeqList_Length(queue);
    }
    // 获取队列的容量
    int SeqQueue_Capacity(SeqQueue* queue) // O(1)
    {
        return SeqList_Capacity(queue);
    }

链式队列的实现代码

#include <malloc.h>
    #include "LinkList.h"
    #include "LinkQueue.h"
    // 定义链式队列结点结构体
    typedef struct _tag_LinkQueueNode
    {
        LinkListNode header;
        void* item;
    } TLinkQueueNode;
    // 创建队列
    LinkQueue* LinkQueue_Create() // O(1)
    {
        return LinkList_Create();
    }
    // 销毁队列
    void LinkQueue_Destroy(LinkQueue* queue) // O(n)
    {
        LinkQueue_Clear(queue);
        LinkList_Destroy(queue);
    }
    // 清空队列
    void LinkQueue_Clear(LinkQueue* queue) // O(n)
    {
        while( LinkQueue_Length(queue) > 0 )
        {
            LinkQueue_Retrieve(queue);
        }
    }
    // 进队列
    int LinkQueue_Append(LinkQueue* queue, void* item) // O(n)
    {
        TLinkQueueNode* node = (TLinkQueueNode*)malloc(sizeof(TLinkQueueNode));
        int ret = (item != NULL) && (node != NULL);
        
        if( ret )
        {
            node->item = item;
            
            ret = LinkList_Insert(queue, (LinkListNode*)node, LinkList_Length(queue));
        }
        
        if( !ret )
        {
            free(node);
        }
        
        return ret;
    }
    // 出队列
    void* LinkQueue_Retrieve(LinkQueue* queue) // O(1)
    {
        TLinkQueueNode* node = (TLinkQueueNode*)LinkList_Delete(queue, 0);
        void* ret = NULL;
        
        if( node != NULL )
        {
            ret = node->item;
            
            free(node);
        }
        
        return ret;
    }
    // 获取队头元素
    void* LinkQueue_Header(LinkQueue* queue) // O(1)
    {
        TLinkQueueNode* node = (TLinkQueueNode*)LinkList_Get(queue, 0);
        void* ret = NULL;
        
        if( node != NULL )
        {
            ret = node->item;
        }
        
        return ret;
    }
    // 获取队列的长度
    int LinkQueue_Length(LinkQueue* queue) // O(1)
    {
        return LinkList_Length(queue);
    }

详细代码见下面链接：

[顺序队列C实现][C]

[链式队列C实现][C 1]

我们观察代码会发现，顺序队列的实现出队列的时间复杂度为O(n)，链式队列的进队列的时间复杂度为O(n)。所以，这样看来复用顺序表及单链表实现的队列还不够优秀，那么，队列有没有其他的实现形式，可以提高进队和出队的效率呢？答案是肯定，不过将在下节揭晓。

[70]: /images/20220531/2e45ac61dffe49f7a387fc5fc7380807.png
[70 1]: /images/20220531/ea7481c510b0425c84419ab31fda5bfc.png
[70 2]: /images/20220531/4836152d25d34e63840b690f1ce9e7fa.png
[C]: http://download.csdn.net/download/u014754841/10248529
[C 1]: http://download.csdn.net/download/u014754841/10248532