【数据结构算法】队列（一）

深碍√TFBOYSˉ_ 2022-05-21 02:19 212阅读 0赞

### 定义 ###

队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

### 队列的链式存储结构 ###

队列常用链式存储结构实现  
![这里写图片描述][70]

typedef struct QNode
    {
        ElemType data;
        struct QNode *next;
    }QNode, *QueuePrt;
    
    typedef struct
    {
        QueuePrt front, rear;
    }LinkQueue;

我们将头指针指向链表的头结点，而队尾指针指向终端结点。（头结点不是必要的，但为了方便操作才加上）空队列时，front和rear都指向头结点。

### 创建队列 ###

*  内存中创建头结点
 *  将队列头指针和尾指针都指向头结点（表示队列为空）

initQueue(LinkQueue *q)
    {
        q->front = q->rear = (QueuePtr)malloc(sizeof(QNode));
        if(!q->front)
            exit(0);
        q->front->next = NULL;
    }

### 入队列操作 ###

插入队列 到时候主要操作rear指针~因为是从尾部插入的，头部不需要动

InsertQueue(LinkQueue *q, ElemType e)
    {
        QueuePtr p;
        p = (QueuePtr)malloc(sizeof(QNode));
        if(p == NULL)
            exit(0);
        p->data = e;
        p->next = NULL;
        q->rear->next = p;
        q->rear = p;
    }

### 出队列操作 ###

出队列操作是将队列中的第一个元素移出，队头指针不发生改变，改变头结点的next指针即可（如图一）。但如果原始队列只有一个元素，那么就要处理队尾指针（如图二）。

![这里写图片描述][70 1]  
![这里写图片描述][70 2]

DeleQueue(LinkQueue *q, ElemType *e)
    {
        QueuePtr p;
        if(q->front == q->rear)
            return;
        p = q->front->next;
        *e = p->data;
        q->front->next = p->next;
        if(q->rear == p)
            q->rear = q->front;
        free(q);
    }

### 销毁队列 ###

由于链队列建立在内存动态区，因此当一个队列不再有用的时候就要及时销毁。

DestroyQueue(LinkQueue *q)
    {
        while(q->front)
        {
            q->rear = q->front->next;
            free(q->front);
            q->front = q->rear;
        }
    }

### 队列用顺序存储结构不好的地方 ###

如下图所示，每次出队列都要向前移动  
![这里写图片描述][70 3]

[70]: /images/20220521/8fa0aac0be83411faf223d36acb3edde.png
[70 1]: /images/20220521/fccf1409d6bd44ae89c4b448d204b997.png
[70 2]: /images/20220521/eac7c4797ea74bf689fc745cf78d4657.png
[70 3]: /images/20220521/9a6758960251437781eacb6a4c2d4db5.png