数据结构(C语言) —— 队列

队列的基本概念

队列也是一种特殊的线性表，队列的数据元素及数据元素间的逻辑关系和线性表完全相同；其差别在于，线性表允许在任意位置插入和删除数据元素，而队列只允许在其一端进行插入操作，在另一端进行删除操作；进行插入操作的一端称为队尾，允许删除操作的一端称为队头。队列是一种先进先出的线性表。

顺序循环队列的表示和实现

顺序循环队列的结构体定义如下：

typedef struct
{
    DataType queue[MaxQueueSize];
    int rear;                //队尾指针
    int front;               //队头指针
    int count;             //计数器
}SeqCQueue;

顺序循环队列的算法实现如下：

1.初始化

void QueueInitiate(SeqCQueue *Q)
{
    Q->rear = 0;
    Q->front = 0;
    Q->count = 0;
}

2.判断非空否

int QueueNotEmpty(SeqCQueue Q)
{
    if(Q.count != 0) return 1;
    else return 0;
}

3.入队列

QueueAppend(SeqCQueue *Q, DataType x)
{
    if(Q->count > 0 && Q->rear == Q->front)
    {
        printf("队列已满无法插入！");
        return 0;
    }
    else
    {
        Q->queue[Q->rear] = x;
        Q->rear = (Q->rear + 1) % MaxQueueSize;
        Q->count ++;
        return 1;
    }
}

4.出队列

QueueDelete(SeqCQueue *Q, DataType *d)
{
    if(Q->count == 0)
    {
        printf("队列已空！");
        return 0;
    }
    else
    {
        *d = Q->queue[Q->front];
        Q->front = (Q->front + 1) % MaxQueueSize;
        Q->count --;
        return 1;
    }
}

5.取队头数据元素

int QueueGet(SeqCQueue Q, DataType *d)
{
    if(Q.count == 0)
    {
        printf("队列已空！");
        return 0；
    }
    else
    {
        *d = Q.queue[Q.front];
        return 1;
    }
}

链式队列的表示和实现

链式队列的存储结构

链式队列中结点的结构体定义如下：

typedef struct qnode
{
    DataType data;
    struct qnode *next;
}LQNode;

定义链式队列的队头指针front和队尾指针rear的结构体如下：

typedef struct
{
    LQNode *front;
    LQNode *rear;
}LQueue;                   //可看做初始队列

链式队列操作的实现

1.初始化

void QueueInitiate(LQueue *Q)
{
    Q->rear = NULL;
    Q->front = NULL;
}

2.判断非空否

int QueueNotEmpty(LQueue Q)
{
    if(Q.front == NULL) return 0;
    else return 1;
}

3.入队列

void QueueAppend(LQueue *Q, DataType x)
{
    LQNode *p;
    p = (LQNode *)malloc(sizeof(LQNode));

    p->data = x;
    p->next = NULL;

    if(Q->rear != NULL) Q->rear->next = p;  //队列原本非空时，队尾加新节点
    Q->rear = p;                            //修改队尾指针
    if(Q->front == NULL) Q->front = p;      //队列原本为空时，修改队头指针
}

4.出队列

int QueueDelete(LQueue *Q, DataType *d)
{
    LQNode *p;
    if(Q->front == NULL)
    {
        printf("队列已空！");
        return 0;
    }
    else
    {
        *d = Q->front->data;
        p = Q->front;
        Q->front = Q->front->next;
        if(Q->front == NULL) Q->rear = NULL;    //删除最后一个结点后，要置队尾指针为空

        free(p);
        return 1;
    }
}

5.取队头数据元素

int QueueGet(LQueue Q, DataType *d)
{
    if(Q.front == NULL)
    {
        printf("队列已空！");
        return 0;
    }
    else
    {
        *d = Q.front->data;
        return 1;
    }
}

6.撤销动态申请空间

void Destory(LQueue Q)
{
    LQNode *p, *p1;

    p = Q.front;
    while(p != NULL)
    {
        p1 = p;
        p = p->next;
        free(p1);
    }
}

优先级队列

优先级队列与一般队列的主要区别是：优先级队列的出队操作不是把队头元素出队列，而是把队列中优先级最高的数据元素出队列。

顺序优先级队列的设计和实现

优先级队列的数据元素的结构体定义如下：

typedef struct
{
    int priority;           //优先级
     ElemType elem;      //其他内容
} DataType;

优先级队列的结构体定义如下：

typedef struct
{
    DataType queue[MaxQueueSize];
    int size;
} SeqPQueue;

1.初始化

void QueueInitiate(SeqPQueue *Q)
{
    Q->size = 0;
}

2.判断非空否

int QueueNotEmpty(SeqPQueue Q)
{
    if(Q.size <= 0) return 0;
    else return 1;
}

3.入队列

int QueueAppend(SeqPQueue *Q, DataType x)
{
    if(Q->size >=MaxQueueSize)
    {
        printf(“队列已满！”);
        return 0;
    }
    else
    {
        Q->queue[Q->size] = x;
        Q->size++;
        return 1;
    }
}

4.出队列

int QueueDelete(SeqPQueue *Q, DataType *d)
{
    DataType min;
    int minIndex, i;
    if(Q->size <= 0)
    {
        printf(“队列已空！”);
        return 0;
    }
    else
    {
        min = Q->queue[0];      //初始queue[0]为优先级最高元素
        minIndex = 0;               //minIndex为优先级最高元素下标
        for(i=0; i<Q->size; i++)    //寻找优先级最高元素对应下标
            if(Q->queue[i].priority <min.priority)
            {
                min = Q->queue[i];
                minIndex = i;
            }
            *d = Q->queue[minIndex];        //找到优先级最高元素
            for(i=minIndex+1; i<Q->size; i++) //数据元素依次前移
                Q->queue[i-1] = q->queue[i];

            Q->size --;
            return 1;
    }
}

5.取队列优先级最高元素

int QueueGet(SeqPQueue *Q, DataType x)
{
    DataType min;
    int minIndex, i;

    if(Q->size <= 0)
    {
        printf(“队列已空！”);
        return 0;
    }
    else
    {
        min = Q->queue[0];
        minIndex = 0;
        for(i=1; i<Q->size; i++)
            if(Q->queue[i].priority < min.priority)
            {
                min = Q->queue[i];
                minIndex = i;
            }

        *d = Q->queue[minIndex];
        return 1;
    }
}