Link Queue

队列（链表实现）

队列概念

队列（Queue）和栈类似，相同点是都属于线性结构，不同点是栈遵循“后进先出”原则，而队列遵循“先进先出”的原则，也被成为“FIFO”结构，就是“First Input First Output”。

数据结构中的队列的两端都允许操作，只不过要求数据只能从队列的一端插入，从队列的另一端删除，可以把队列理解为一根水管，水管有进水口和出水口。一般把允许数据插入的一端称为队尾（Tail或者Rear），一般把允许删除数据的一端称为队头队首（Head或Front）。

---

队列的结构

• 结构图

• 代码描述

  // linkQueue.h
  
  #ifndef LINKQUEUE_H
  #define LINKQUEUE_H
  
  #include<stdio.h>
  #include<stdlib.h>
  
  #define DataType int               // 数据类型
  
  #define OUTPUTERROR  -2147483648   // 出栈错误时的返回值
  
  typedef struct node                // 结点结构体
  {
      DataType data;
      struct node *next;
  }QueueNode;
  
  typedef struct queue               // 队列结构体
  {
      int size;
      QueueNode *front;
      QueueNode *rear;    
  }LinkQueue;
  
  LinkQueue *Inti_LinkQueue(void); //初始化队列
  int Queue_IsEmpty(LinkQueue *queue); // 判空
  int Input(LinkQueue *queue,DataType data); // 入队
  DataType Output(LinkQueue *queue); // 出队
  void Display_Queue(LinkQueue *queue); // 展示队列
  void Distory_Queue(LinkQueue *queue); // 摧毁队列
  
  #endif

// linkQueue.c

#include"linkQueue.h"

// 创建新节点
static QueueNode *NewNode(DataType x)
{
    QueueNode *node = (QueueNode*)malloc(sizeof(QueueNode));
    if(node != NULL)
    {
        node->data = x;
        node->next = NULL; 
    }
    return node;
}

// 初始化队列
LinkQueue *Inti_LinkQueue(void)
{
    LinkQueue *queue = (LinkQueue*)malloc(sizeof(LinkQueue));
    queue->front = NULL;
    queue->rear = NULL;
    queue->size = 0;
    return queue;
}

// 判空
int Queue_IsEmpty(LinkQueue *queue)
{
    return queue->size == 0;
}

// 队头插入结点
static int Input_Node(LinkQueue *queue,QueueNode *node)
{
    if (queue == NULL || node == NULL)
        return 0;
    
    if (Queue_IsEmpty(queue))
    {
        queue->rear = node;
        queue->front = node;
    }
    else
    {
        queue->rear->next = node;
        queue->rear = node;
    }
    queue->size++;

    return 1;
}

// 入队
int Input(LinkQueue *queue,DataType data)
{
    return Input_Node(queue,NewNode(data));
}

// 出队
DataType Output(LinkQueue *queue)
{
    if (queue == NULL || Queue_IsEmpty(queue))
        return OUTPUTERROR;
    
    QueueNode *output_node = queue->front;
    DataType output_data = output_node->data;

    if (queue->size == 1)
    {
        queue->front = NULL;
        queue->rear = NULL;
    }
    else
        queue->front = output_node->next;

    queue->size--;
    free(output_node);
    
    return output_data;
}

// 展示队列
void Display_Queue(LinkQueue *queue)
{
    if(queue == NULL || Queue_IsEmpty(queue))
    {
        printf("queue can not display\n");
        return;
    }

    QueueNode *p = queue->front;

    printf("(queue front ↑)\n");
    for (int i = 0; i < queue->size; i++)
    {
        printf("%d\n",p->data);
        p = p->next;
    }
    printf("(queue rear  ↑)\n");
        
}

// 摧毁队列
void Distory_Queue(LinkQueue *queue)
{
    queue->rear->next = NULL;
    QueueNode *p = queue->front;
    QueueNode *q;
    while (p != NULL)
    {
        q = p->next;
        free(p);
        p = q;
    }
    free(queue);
}