数据结构——队列（链表实现）

一、队列的特点

先进先出

二、队列的代码

typedef int QDataType;

// 链式结构：表示队列 
typedef struct QListNode
{
    struct QListNode* next;
    QDataType data;
}QNode;

// 队列的结构 
typedef struct Queue
{
    QNode* front; //指向队列的第一个结点
    QNode* rear;//指向队列的最后一个结点
    int size;//记录队列中一共有几个元素
}Queue;

// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);


    
// 初始化队列 
void QueueInit(Queue* q)
{
    assert(q);
    q->front = NULL;  //初始化为NULL
    q->rear = NULL;//初始化为NULL
    q->size = 0;  //初始化个数为0
}

// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
    assert(q);

    QNode* newnode = (QNode*)malloc(sizeof(QNode));//申请新的结点
    if (newnode == NULL)
    {
        perror("malloc fail");
        return;
    }
    newnode->data = data; 
    newnode->next = NULL;

    if (q->front == NULL)  //如果front指针指向的是NULL，说明插入前队列是空队列
    {
        q->front = newnode;
        q->rear = newnode;
    }
    else        //front指向的不是NULL,说明不是空队列
    {
        q->rear->next = newnode;
        q->rear = newnode;
    }
    q->size++;  //插入完，个数加1
}

// 队头出队列 
void QueuePop(Queue* q)//出队就是头删
{
    assert(q);
    assert(q->size != 0);//队列不为空

    QNode* head = q->front;  //找到头结点
    if (head->next == NULL)//如果出队之前，前队列只有一个结点  
    {
        free(head);   //释放头结点，后front 和rear都要指向NULL,表示现在是空队列
        head = NULL;   
        q->front = q->rear = NULL;
        q->size = 0;     //个数置为0
        return; 
    }
    else   //出队前，队列有两个及其以上的结点数
    {
        QNode* del = head;  
        head = head->next; //更新头结点
        free(del);  
        del = NULL;
        q->front = head;   //将front 指向更新后的头结点
        q->size--;//个数减1
    }
}

// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
    assert(q);

    return q->front->data;
}

// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
    assert(q);

    return q->rear->data;
}

// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
    assert(q);

    return q->size;
}

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{
    assert(q);

    if (q->front == NULL)//队列为空，返回1
        return 1;
    else
        return 0;
}

// 销毁队列 
void QueueDestroy(Queue* q)
{
    assert(q);

    QNode* del = q->front;  //如果是空队列，就直接返回NULL，不要释放结点
    if (del == NULL)
    {
        ;
    }
    else
    {
        QNode* cur = del->next;
        while (del != NULL)    //逐个释放结点
        {

            free(del);
            del = cur;
            if (cur != NULL)
                cur = cur->next;
        }
    }
    //队头指针和队尾指针都是要置NULL的，size都是要置为0
    q->front = q->rear = NULL;
    q->size = 0;
}

三、队列的函数测试

1.取队头函数 QueueFront

int main()
{
    Queue Q;

    QueueInit(&Q);// 初始化队列 
    
    QueuePush(&Q, 1);// 队尾入队列 
    QueuePush(&Q, 2);// 队尾入队列 
    QueuePush(&Q, 3);// 队尾入队列 
    QueuePush(&Q,4);// 队尾入队列 

  
    QDataType x= QueueFront(&Q);// 获取队列头部元素 
printf("队头元素是%d \n", x);

QueueDestroy(&Q);// 销毁队列

    return 0;
}

结果：

2.取队尾函数QueueBack

int main()
{
    Queue Q;

    QueueInit(&Q);// 初始化队列 
    
    QueuePush(&Q, 1);// 队尾入队列 
    QueuePush(&Q, 2);// 队尾入队列 
    QueuePush(&Q, 3);// 队尾入队列 
    QueuePush(&Q,4);// 队尾入队列 

    QDataType y= QueueBack(&Q); // 获取队列队尾元素 
  printf("队尾元素是%d \n", y);
    
QueueDestroy(&Q);// 销毁队列

    return 0;
}

结果：

3.求队列中元素个数函数 QueueSize(&Q)

int main()
{
    Queue Q;

    QueueInit(&Q);// 初始化队列 
    
    QueuePush(&Q, 1);// 队尾入队列 
    QueuePush(&Q, 2);// 队尾入队列 
    QueuePush(&Q, 3);// 队尾入队列 
    QueuePush(&Q,4);// 队尾入队列 

    int z= QueueSize(&Q); // 获取队列中有效元素个数 
printf("一共有%d个成员 \n", z);

QueueDestroy(&Q);// 销毁队列

    return 0;
}

结果；

4.出队函数QueuePop（头删）

int main()
{
    Queue Q;

    QueueInit(&Q);// 初始化队列 
    
    QueuePush(&Q, 1);// 队尾入队列 
    QueuePush(&Q, 2);// 队尾入队列 
    QueuePush(&Q, 3);// 队尾入队列 
    QueuePush(&Q,4);// 队尾入队列 

   
    QueuePop(&Q);// 队头出队列 
QueuePop(&Q);// 队头出队列 


while (!QueueEmpty(&Q))
{
    printf("%d ", QueueFront(&Q));
    QueuePop(&Q);
}

    return 0;
}

结果：

原来 1 2 3 4 入队出队两次，变成 3 4 .

5.判断队列是否为空的函数QueueEmpty（不为空就会依次出队）

int main()
{
    Queue Q;

    QueueInit(&Q);// 初始化队列 
    
    QueuePush(&Q, 1);// 队尾入队列 
    QueuePush(&Q, 2);// 队尾入队列 
    QueuePush(&Q, 3);// 队尾入队列 
    QueuePush(&Q,4);// 队尾入队列 

   
    while (!QueueEmpty(&Q))  //队列不为空，就会依次出队
  {
    printf("%d ", QueueFront(&Q));
    QueuePop(&Q);//依次出队
  }

    printf("所有成员出完队后\n");
    int w= QueueEmpty(&Q);
if (w != 0)
    printf("队列已经空了");

    return 0;
}

结果：