队列的定义与实现（国嵌学习笔记）

一、队列的定义

    

1>队列是一种特殊的线性表

2>队列仅在线性表的两端进行操作

    *对头（Front）：取出数据元素的一端

    *队尾（Rear）：插入数据元素的一端

3>性质：先进先出（FIFO）

4>队列的操作

    

    *创建队列

    *销毁队列

    *清空队列

    *进队列

    *出队列

    *获取对头元素

    *获取队列的长度

队里是一种特殊的线性表，所以通常有两种实现方式，顺序结构实现。链式结构实现。从而我们可以

复用之前实现的链表会很简单的实现队列，在此就不做详细介绍了。下面来讨论队列的优化实现，其

中也包括顺序结构实现和链式结构实现。

二、顺序队列的优化实现

顺序队列的瓶颈  如何将出队操作的时间复杂度降低到O(1)?

定义front使其始终代表队头的下标

    出队时将队头元素返回，且front++

定义rear使其始终代表队尾下一个元素的小标

    入队时将新元素插入，且rear++

没有必要只将下标为0的位置定义为对头！！！

顺序状态的关键状态

    初始状态：length == 0， front == 0， rear == 0；

    空队列时：length == 0， front == rear；

    满队列状态：length == capacity， front == rear；

循环使用队列中的空间

    入队：rear = （rear + 1）% capacity；

    出队：front = （front + 1）% capacity；

/********************************SeqQueue.h**********************/

#ifndef _SEQQUEUE_H_
#define _SEQQUEUE_H_

typedef void SeqQueue;

SeqQueue* SeqQueue_Create(int capacity);

void SeqQueue_Destroy(SeqQueue* queue);

void SeqQueue_Clear(SeqQueue* queue);

int SeqQueue_Append(SeqQueue* queue, void* item);

void* SeqQueue_Retrieve(SeqQueue* queue);

void* SeqQueue_Header(SeqQueue* queue);

int SeqQueue_Length(SeqQueue* queue);

int SeqQueue_Capacity(SeqQueue* queue);

#endif

/*************************SeqQueue.c****************************/
#include <stdio.h>
#include <malloc.h>
#include "SeqQueue.h"

typedef unsigned int TSeqQueueNode;

typedef struct _tag_SeqQueue
{
    int capacity;
    int length;
    int front;
    int rear;
    TSeqQueueNode* node;
}TSeqQueue;

SeqQueue* SeqQueue_Create(int capacity)
{
    TSeqQueue* ret = NULL;
    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;
}

void SeqQueue_Destroy(SeqQueue* queue)
{
    free(queue);
}

void SeqQueue_Clear(SeqQueue* queue)
{
    TSeqQueue* sQueue = (TSeqQueue*)queue;

    if( sQueue != NULL )
    {
        sQueue->length = 0;
        sQueue->front = 0;
        sQueue->rear = 0;
    }
}

int SeqQueue_Append(SeqQueue* queue, void* item)
{
    TSeqQueue* sQueue = (TSeqQueue*)queue;
    int ret = (sQueue != NULL);

    ret = ret && (item != NULL) && (sQueue->length + 1 < sQueue->capacity );

    if( ret )
    {
        sQueue->node[sQueue->rear] = (TSeqQueueNode)item;

        sQueue->rear = (sQueue->rear + 1) % sQueue->capacity;

        sQueue->length++;
    }

    return ret;
}

void* SeqQueue_Retrieve(SeqQueue* queue)
{
    TSeqQueue* sQueue = (TSeqQueue*)queue;
    void* ret = SeqQueue_Header(queue);

    if( ret != NULL)
    {
        sQueue->front = (sQueue->front + 1) % sQueue->capacity ;

        sQueue->length--;

    }

    return ret;
}

void* SeqQueue_Header(SeqQueue* queue)
{
    TSeqQueue* sQueue = (TSeqQueue*)queue;
    void*ret = NULL;

    if( (sQueue != NULL) && (sQueue->length > 0))
    {
        ret = (void*)(sQueue->node[sQueue->front]);
    }

    return ret;
}

int SeqQueue_Length(SeqQueue* queue)
{
    TSeqQueue* sQueue = (TSeqQueue*)queue;
    int ret = -1;

    if( sQueue != NULL)
    {
        ret = sQueue->length;
    }

    return ret;
}

int SeqQueue_Capacity(SeqQueue* queue)
{
    TSeqQueue* sQueue = (TSeqQueue*)queue;
    int ret = -1;

    if( sQueue != NULL)
    {
        ret = sQueue->capacity;
    }

    return ret;

}
/*************************************main.c****************/
#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;
}

三、链式队列的优化实现

1>定义rear指针始终指向链表中的最后一个元素

    *入队时将新元素通过rear插入队尾，且将rear指向新元素

2>链式队列的关键状态

    *空队列状态：front == NULL，rear == NULL；

3>关键操作

    *入队：

        rear->next = node;

        rear = node;

        node->next = NULL;

    *出队：

    front = front->next;

/**********************LinkQueue.h********************/
#ifndef _LINKQUEUE_H_
#define _LINKQUEUE_H_

typedef void LinkQueue;

LinkQueue* LinkQueue_Create();

void LinkQueue_Destroy(LinkQueue* queue);

void LinkQueue_Clear(LinkQueue* queue);

int LinkQueue_Append(LinkQueue* queue, void* item);

void* LinkQueue_Retrieve(LinkQueue* queue);

void* LinkQueue_Header(LinkQueue* queue);

int LinkQueue_Length(LinkQueue* queue);

#endif

/**********************LinkQueue.c********************/
#include <malloc.h>
#include <stdio.h>
#include "LinkQueue.h"

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);

    if( ret )
    {
        node->item = item;

        if(sQueue->length > 0)
        {
            sQueue->rear->next = node;
            sQueue->rear = node;
            node->next = NULL;
        }
        else
        {
            sQueue->front = node;
            sQueue->rear = node;
            node->next = NULL;
        }

        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;

    if( (sQueue != NULL) && (sQueue->length > 0))
    {
        node = sQueue->front ;
        sQueue->front = node->next ;

        ret = node->item ;

        free(node);

        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;

   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;

    if(sQueue != NULL)
    {
        ret = sQueue->length;
    }

   return ret;
}

/**********************main.c*************************/
#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;
}

优化的顺序队列循环利用空间提高出队操作的效率，优化的链式队列定义rear指针指向队尾元素提高

出队操作的效率。

四、用栈实现队列的特别实现

实现思路：

    准备两个栈用于实现队列：inStack和outStack

    当有新元素入队时：将其压入inStack中

    当需要出队时：

    当outStack为空时：

    1、将inStack中的元素逐一弹出并压入outStack中

    2、将outStack的栈顶元素弹出

    当outStack不为空时：

    -直接将outStack的栈顶元素弹出