数据结构之链式队列_链式队列时间复杂度

我们实现了顺序队列，包括优化，现在我们再来学习下链式队列。

注：这里还是要包含前面我们实现的链式链表的头文件和实现文件。

第十个例子，链式队列的实现：

头文件

#ifndef _LINKQUEUE_H_
#define _LINKQUEUE_H_
 
typedef void LinkQueue;
 
LinkQueue* LinkQueue_Create();
 
void LinkQueue_Destroy(LinkQueue* queue);
 
void LinkQueue_Clear(LinkQueue* queue);
 
int LinkQueue_Length(LinkQueue* queue);
 
int LinkQueue_Append(LinkQueue* queue, void* item);
 
void* LinkQueue_Retrieve(LinkQueue* queue);
 
void* LinkQueue_Header(LinkQueue* queue);
 
#endif

我个人有点小小的强迫症，代码尽量要求简洁，所以没有注释，有什么不明白的可以留言。

实现文件

#include "LinkList.h"
#include "LinkQueue.h"
#include <stdio.h>
#include <malloc.h>
 
typedef struct tag_LinkQueueNode
{
    LinkListNode header;
    void* item; 
}TLinkQueueNode;
 
LinkQueue* LinkQueue_Create()
{
    return LinkList_Create();
}
 
void LinkQueue_Destroy(LinkQueue* queue)
{
    LinkQueue_Clear(queue);
    LinkList_Destroy(queue);     
}
 
void LinkQueue_Clear(LinkQueue* queue)
{
    while (LinkQueue_Length(queue) > 0)
    {
        LinkQueue_Retrieve(queue);
    }  
}
 
int LinkQueue_Length(LinkQueue* queue)
{
    return LinkList_Length(queue);    
}
 
int LinkQueue_Append(LinkQueue* queue, void* item)
{
    TLinkQueueNode* node = (TLinkQueueNode*)malloc(sizeof(TLinkQueueNode));
    int ret = (node != NULL) && (item != NULL);
    
    if (ret)
    {
        node->item = item;
        ret = LinkList_Insert(queue, (LinkListNode*)node, LinkList_Length(queue)); 
    }
    else
    {
        free(node);
    } 
  
    return ret;
}
 
void* LinkQueue_Retrieve(LinkQueue* queue)
{
    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)
{
    TLinkQueueNode* node = (TLinkQueueNode*)LinkList_Get(queue, 0);   
    void* ret = NULL;
    
    if (node != NULL)
    {
        ret = node->item;
    }
    
    return ret; 
}

#include <stdio.h>
#include <stdlib.h>
#include "LinkQueue.h" 
 
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("length:%d\n", LinkQueue_Length(queue));  
    printf("header:%d\n", *((int*)LinkQueue_Header(queue)));  
      
    while (LinkQueue_Length(queue) > 0)  
    {  
        printf("retrieve:%d\n", *((int*)LinkQueue_Retrieve(queue)));        
    }  
      
    LinkQueue_Clear(queue);  
    LinkQueue_Destroy(queue);  
       
    system("PAUSE");      
    return 0;  
}  

所以下一篇文章我会实现一个优化版的链式队列。