定义

队列,又称为伫列(Queue),是先进先出(FIFO, First-In-First-Out)的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端(称为rear)进行插入操作,在前端(称为front)进行删除操作。队列的操作方式和堆栈类似,唯一的区别在于队列只允许新数据在后端进行添加。

实现:

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define OK 1
#define NONONO -1;
typedef int Element_type; //定义 Element_type 类型,即队列数据类型为 int
typedef int Status;

typedef struct QUEUE_NODE
{
    Element_type data;
    struct QUEUE_NODE *next;
} QueueNode, *Queue_pointer;

typedef struct
{
    Queue_pointer front;
    Queue_pointer rear;
} Queue;

//  队列初始化
Status QueueInit(Queue *Q);
//  销毁队列
Status QueueDestroy(Queue *Q);
//  清除队列
Status QueueClear(Queue *Q);
//  队列空
Status isQueueEmpty(const Queue Q);
//  入队
Status QueueEnter(Queue *Q, Element_type value);
//  出队
Status QueueDelete(Queue *Q);
//  返回队头元素的值
Status QueueGetFront(const Queue Q, Element_type *x);
//  获取队列长度
Status QueueLength(const Queue Q);
//  遍历队列
void QueueTrave(const Queue Q);

Status QueueInit(Queue *Q)
{
    Q->front = Q->rear = (Queue_pointer)malloc(sizeof(QueueNode));
    assert(Q->front != NULL);
    assert(Q->rear != NULL);
    Q->front->next = NULL;
    return OK;
}

Status QueueDestroy(Queue *Q)
{
    while (Q->front)
    {
        Q->rear = Q->front->next;
        free(Q->front);
        Q->front = Q->rear;
    }
    return OK;
}
Status QueueClear(Queue *Q)
{
    QueueDestroy(Q);
    QueueInit(Q);
    return OK;
}

Status isQueueEmpty(const Queue Q)
{
    return Q.front->next == NULL;
}

Status QueueEnter(Queue *Q, Element_type value)
{
    QueueNode *p;
    p = (QueueNode *)malloc(sizeof(QueueNode));
    assert(p != NULL);
    p->data = value;
    p->next = NULL;
    Q->rear->next = p;
    Q->rear = p;
    return OK;
}

Status QueueDelete(Queue *Q)
{
    QueueNode *p;
    assert(!isQueueEmpty(*Q));
    p = Q->front->next;
    Q->front->next = p->next;
    free(p);
    return OK;
}

Status QueueGetFront(const Queue Q, Element_type *x)
{
    assert(!isQueueEmpty(Q));
    *x = Q.front->next->data;
    return OK;
}

Status QueueLength(const Queue Q)
{
    int i;
    QueueNode *p = Q.front;
    while (Q.rear != p)
    {
        i++;
        p = p->next;
    }
    return i;
}

void QueueTrave(const Queue Q)
{
    printf("Queue: ");
    QueueNode *p = Q.front->next;
    for (; p;)
    {
        printf("-> %d ", p->data);
        p = p->next;
    }
    printf("\n");
}

void test_queue()
{
    Queue Q;
    if (QueueInit(&Q))
    {
        Element_type temp;
        printf("LinkList init success\n");
        if (isQueueEmpty(Q))
            printf("LinkList is empty\n");
        printf("queue's length is %d\n", QueueLength(Q));
        for (int i = 10; i >= 0; i--)
            QueueEnter(&Q, i);
        QueueTrave(Q);
        printf("queue's length is %d\n", QueueLength(Q));
        if (QueueGetFront(Q, &temp))
            printf("The front element is %d\n", temp);
        QueueTrave(Q);
        QueueGetFront(Q, &temp);
        QueueDelete(&Q);
        printf("deleted element is %d\n", temp);
        QueueTrave(Q);
        printf("queue's length is %d\n", QueueLength(Q));
        QueueEnter(&Q, 99);
        printf("insert 99 to queue\n");
        QueueTrave(Q);
        if (QueueDestroy(&Q))
            printf("\ndestroy success\n");
    }
}

int main(void)
{
    test_queue();
    return 0;
}


如有错误还请 dalao 指正


2 Comments

jacknothing · 2018/10/20 at 20:14

hi

    somemamgel · 2018/10/22 at 13:17

    Hi!

Leave a Reply

Your email address will not be published. Required fields are marked *