【C语言】基本数据结构-队列(链表实现和数组实现)

首先回答第一个的问题，指针域推荐包含两个指针，那么为什么要包含两个指针呢，像单链表节点一样节点中只用一个指针可以吗。答案是可以的但是这样做耗时太长。举例来说，如果节点中只有一个指针，在表尾插入新元素时需要先查找一遍整个链表，找到最后一个节点后再进行插入操作，这样会浪费大量时间。为了解决这个问题，我们在结构体中声明两个指针，next指针用于存储下一个节点信息，rear指针用于指向链表末尾的节点。从而达到快速定位链表末尾的效果。

第二个问题要选择是(表头删除,表尾插入)的方式，这是因为(表头插入 ,表尾删除)这种方式在删除表尾时无法确定倒数第二个节点的位置。从而无法将上一个节点的next指针指向NULL。

第三个问题我建议头结点不要存储数据，将头节点当做记录节点来使用，如果头结点存储数据的情况下删除元素会使表头地址不断地变化，从而导致删除代码的流程变复杂。

2.2 初始化队列

队列的初始化非常简单，创建一个新的节点并且把指针域指向NULL 即可。因为初始化时需要

在函数中修改指针指向的地址，所以需要使用二级指针。

//声明队列节点
struct node
{
    int element;
    struct node *next;   //用于记录下一个节点地址
    struct node *rear;   //用于记录队尾节点地址
}

//初始化队列函数
void init_queue(struct node **pNode)
{
    *pNode = (struct node*)malloc(sizeof(struct node));
    if(NULL == *pNode)
    {
        printf("栈初始化申请内存失败");
        return NULL;
    }
    (*pNode)->next = NULL;
    (*pNode)->rear = NULL;
}
 
//测试用例
struct node *pQueue = NULL;
init_queue(&pQueue);

2.3 队列的判空

因为头结点不存储数据，所以对队列的判空其实就是对头结点的下一个节点的判空。

//队列判空  1-空 0-非空
bool is_empty(struct node *pQuene)
{
    assert(NULL != pQuene);
    return (NULL == pQuene->next);
}

//测试用例
struct node *pQuene;
is_empty(pQuene);

2.4 入队

入队就是在队列中插入新元素，我们使用尾插法，在链表尾部插入新元素。

//从队尾入队
void en_queue(struct node *pQueue, int element)
{
    //校验入参
    assert(NULL == pQueue);
    //入参指针不要直接使用
    struct node *pNode = pQueue;

    //创建新节点
    struct node *pNew = NULL;
    pNew = (struct node*)malloc(sizeof(struct node));
    if(NULL == pNew)
    {
        printf("新节点申请内存失败");
        return;
    }
    pNew->element = element;
    
    //从队尾插入新元素
    if(is_empty(pNode))   
    {   
        //连接新节点
        pNode->next = pNew;
        pNew->next = NULL;
        
        //记录队尾位置
        pNode->rear = pNew;
    }
    else
    {
        //连接新节点,pNode->rear是之前队尾地址
        pNode->rear->next = pNew;
        pNew->next = NULL;
        
        //重新记录队尾位置
        pNode->rear = pNew;
    }
}

//测试用例
struct node *pQuene;
en_queue(pQuene, 10);

2.5 出队

出队就是删除队列元素，我们刚才选择在队尾入队，现在在队头出队，就是删除头节点的下一个节点。

//从队头出队
void de_queue(struct node *pQueue)
{
    //校验入参
    assert(NULL == pQueue);
    //入参指针不要直接使用
    struct node *pNode = pQueue;
    
    //删除操作
    if(is_empty(pNode))
    {   
        printf("空队列，无法删除");
    }
    else
    {   
        pNode->next = pNode->next->next;
        free(pNode->next);
    }
}

//测试用例
struct node *pQueue;
de_queue(pQueue);

2.6 获取队头队尾元素

获取队头队尾元素非常简单，获取队头元素就是获取pNode->next地址的元素，获取队尾元素就是获取pNode->rear地址的元素。

//获取队列元素   flag为1返回队头，flag为0返回队尾
int get_Quene_element(struct node *pQuene, int flag)
{
    //校验入参
    assert(NULL == pQueue);
    //入参指针不要直接使用
    struct node *pNode = pQueue;

    if(is_empty(pNode))
    {   
        printf("空队列，无法获取");
        return 0;
    }

    if(flag)
    {
        return pNode->next->element;    
    }
    else
    {
        return pNode->rear->element;
    }

}

//测试用例
struct node *pQuene;
int Queuehead_value, QueueRear_value;
Queuehead_value = get_Quene_element(pQuene, 1);
QueueRear_value = get_Quene_element(pQuene, 0);

3. 队列的数组实现

正如前文所说，用数组实现队列需要固定长度并造成空间浪费，但是它的实现比链表要简单很多。我们这里采用双下标的方式来实现链表的操作，用front下标来实现队头元素的删除，用rear下标来实现队尾元素的插入。

3.1 初始化队列

初始化队列就是创建一个结构体后将front和rear下标都赋非法值。

#define MAXIDX 100  //队列最大容量

//队列结构体
struct Queue 
{
    int data[MAXIDX];
    int front;
    int reat;
}

//初始化队列
void init_queue(strcut Queue *queue)
{
    (*queue).front = -1;
    (*queue).rear = -1;
}

//测试用例
struct Queue queue;
init_queue(&queue);

3.2 队列的判空

队列的判空就是看front值是否合法。

//队列判空   1为空   0为非空
bool is_QueueEmpty(struct Queue queue)
{
    return (queue.front < 0) ? TRUE : FALSE;
}

3.3 入队

入队就是将新元素插入到队尾即可，需要注意队满时无法入队。

//从队尾入队
void en_queue(struct node *Queue, int element)
{
    //队满时无法入队
    if(rear >= (MAXIDX + 1))
    {
        printf("队列满，无法入队");
        return ;
    }

    //入队
    (*Queue).data[++rear] = element;
}

//测试用例
struct node pQuene;
en_queue(&pQuene, 10);

3.4 出队

出队就是将队头元素取出，即front++即可，需要注意队空时无法出队。

//从队头出队
void en_queue(struct node *Queue, int element)
{
    //队空时无法出队
    if(front <= 0)
    {
        printf("队列空，无法出队");
        return ;
    }

    //出队
    (*Queue).data[++front] = 0;
}

//测试用例
struct node pQuene;
en_queue(&pQuene, 10);

3.5 获取队头队尾元素

获取队头队尾元素就是读取front和rear中的元素即可。

//获取队列元素   flag为1返回队头，flag为0返回队尾
int get_Quene_element(struct node pQuene, int flag)
{
    if(is_empty(pNode))
    {   
        printf("空队列，无法获取");
        return 0;
    }

    if(flag)
    {
        return pNode.data[front];    
    }
    else
    {
        return pNode.data[rear];
    }

}

//测试用例
struct Quene queue;
int Queuehead_value, QueueRear_value;
Queuehead_value = get_Quene_element(queue, 1);
QueueRear_value = get_Quene_element(queue, 0);