数据结构-队列(queue)

ゝ一世哀愁。 2022-08-22 00:27 175阅读 0赞

队列（queue）是一种采用先进先出(FIFO)策略的抽象数据结构，它的想法来自于生活中排队的策略。顾客在付款结账的时候，按照到来的先后顺序排队结账，先来的顾客先结账，后来的顾客后结账。

![这里写图片描述][20160509165022899]

# 队列实现 #

同栈的实现一样，队列的实现也有数组实现和链表实现两种方式。

## 数组实现 ##

先来看看数组实现的方法。栈使用top变量记录栈顶的位置，而队列则使用front和rear分别队列第一个元素和最后一个元素的位置。

![这里写图片描述][1243953170-57245f3329084_articlex]

#define SIZE 20
    typedef struct queue
    {
        int arr[SIZE];
        int front;
        int rear;
    
    } Queue;

入队、出队操作很简单。入队时，通过rear的位置判断队列是否已满。如果没有满，则将rear后移一位，将新元素放置在rear所在位置。出队时，也可以通过rear的位置判断队列是否为空。如果不空，则只需将front后移一位即可。 获取队头元素，判断队列不空，则只需返回front指向位置的元素即可。

哇塞！好简单啊！这样就完成了队列的实现啊！太天真了。。。想一下，通过出队操作将数据弹出队列后，front之前的空间还能够再次得到吗？不能。所以使用普通数组实现队列，就再也不能使用front之前的空间了，这会导致大量空间丢失。

### 循环数组 ###

为了解决这个问题，将普通数组换成**循环数组**。在循环数组中，末尾元素的下一个元素不是数组外，而是数组的头元素。这样就能够再次使用front之前的存储空间了。

![循环数组][20130806120215890]

哇塞！有解决了这个问题。可以开始码代码了！且慢，在实现修改入队和出队操作之前，再深思一步，这时是否还能简单通过判断rear的位置来判断队列空或满呢？当然不可以。那是否可以考虑front和rear之间的位置关系呢？考虑如下两种边界情况：

![这里写图片描述][20160509195955645]

在这两种情况下，rear都在front前一个位置，无法判断此时队列满还是空。为了解决这个问题，通常采用的最简单的方法就是，使用一个**counter记录队列中元素个数**。修改队列定义为下：

#define SIZE 20
    
    typedef struct queue
    {
        int arr[SIZE];
        int front;
        int rear;
        int counter;
    
    } Queue;
    
    Init(Queue *q)
    {
        q->front = 0;
        q->rear = -1;
        q->counter = 0;
    } 
    
    
    bool IsFull(Queue *q)
    {
        return (q->counter >= SIZE);
    }
    
    void EnQueue(Queue *q, int val)
    {
        if(IsFull(q))
            return;
    
        q->rear = (q->rear + 1) % SIZE;
        q->arr[q->rear] = val;
        q->counter++;
    }
    
    
    bool IsEmpty(Queue *q)
    {
        return (q->counter <= 0);
    }
    
    
    void DeQueue(Queue *q)
    {
        if (IsEmpty(q))
            return;
    
        q->front = (q->front + 1) % SIZE;
        q->counter--;
    
    }
    
    //get the front element from queue
    int Front(Queue *q)
    {
        if (IsEmpty(q))
            return;
    
        return q->arr[q->front];
    }

另外一种方法是，**在数组中空出一个位置**，用以标记队列是否已满。  
![这里写图片描述][20160509205702944]

![这里写图片描述][20160509205722148]

![这里写图片描述][20160509205737185]

bool IsFull(Queue *q)
    {
        return ((q->rear + 2) % SIZE == q->front);
    }
    
    bool IsEmpty(Queue *q)
    {
        return ((q->rear + 1) % SIZE == q->front);
    }

有时候，**rear表示队尾元素的下一个位置**，即表示即将插入元素的位置。  
![这里写图片描述][1381510097_5847.jpg]

此时，判断队列的操作应该修改如下：

#define SIZE 20
    
    typedef struct queue
    {
        int arr[SIZE];
        int front;
        int rear;
    
    } Queue;
    
    
    Init(Queue *q)
    {
        q->front = 0;
        q->rear = 0;
    } 
    
    
    bool IsFull(Queue *q)
    {
        return ((q->rear + 1) % SIZE == q->front);
    }
    
    void EnQueue(Queue *q, int val)
    {
        if(IsFull(q))
            return;
    
        q->arr[q->rear] = val;
        q->rear = (q->rear + 1) % SIZE;
    }
    
    
    bool IsEmpty(Queue *q)
    {
        return (q->rear == q->front);
    }
    
    
    void DeQueue(Queue *q)
    {
        if (IsEmpty(q))
            return;
    
        q->front = (q->front + 1) % SIZE;
    
    }
    
    
    int Front(Queue *q)
    {
        if (IsEmpty(q))
            return;
    
        return q->arr[q->front];
    }

## 链表实现 ##

队列的数组实现比较麻烦，需要考虑各种边界情况，所以通常使用链表形式来实现队列。

使用单向链表来实现链式队列，链式队列中存储front和rear即可。

typedef struct node
    {
        int val;
        struct node *next;
    }Node;
    
    typedef struct queue
    {
        Node *front;
        Node *rear;
    };

为了方便实现，链式队列中的front表示链表的头节点，而front的next才表示队头。链式队列的入队和出队操作如下图所示。从图中可以看出链式队列的实现采用尾进头出的策略。

![链式队列][1367116889_2916.jpg]

在链式队列中，不需要考虑队列是否已满，只要内存足够就可以一直分配空间。而当front和rear都指向头节点的时候，则表示此时队列为空。

bool IsEmpty(Queue *q)
    {
        return (q->front == q->rear);
    }

**入队**时移动rear指向最后一个元素即可。

Node* CreateNode(int val)
    {
        Node *newNode = (Node*)malloc(sizeof(Node));
        if (newNode == NULL)
            return NULL;
        else {
            newNode->val = val;
            newNode->next = NULL;
            return newNode;
        }
    }
    
    
    void EnQueue(Queue *q, int val)
    {
        Node *newNode = CreateNode(val);
        if (newNode == NULL)
            return;
        else {
            q->rear->next = newNode;
            q->rear = q->rear->next;
        }
    }

出队时，不需要移动front指针，只需将其next指针指向下一个next元素即可。`q->front->next = q->front->next->next;` 但是需要考虑一种特殊情况，即当队列中只剩下一个元素时，还需要使rear指针重新指向头节点。

int Front(Queue *q)
    {
        if (IsEmpty(q))
            return -1;
        else
            return (q->front->next->val);
    }
    
    void DeQueue(Queue *q)
    {
        if (IsEmpty(q))
            return;
        else 
        {
            Node *deNode = q->front->next;
            q->front->next = deNode->next;
    
            if (q->rear == deNode) //only one element
                q->rear = q->front;
    
            free(deNode);
        }
    }

[20160509165022899]: /images/20220724/b8e1fd7921c34a51bb8cd9f842891ebe.png
[1243953170-57245f3329084_articlex]: https://sfault-image.b0.upaiyun.com/124/395/1243953170-57245f3329084_articlex
[20130806120215890]: /images/20220724/55750da227f941be9d809903a36fd258.png
[20160509195955645]: /images/20220724/84e9c2c4adef471689f7d9160a46946e.png
[20160509205702944]: /images/20220724/f81978a5331e4b318016b3b1d091be67.png
[20160509205722148]: /images/20220724/64fb11382a454d4e997b30a9d0f87097.png
[20160509205737185]: /images/20220724/77f58034b08848d78b7171bc797479dc.png
[1381510097_5847.jpg]: https://img-my.csdn.net/uploads/201310/12/1381510097_5847.jpg
[1367116889_2916.jpg]: https://img-my.csdn.net/uploads/201304/28/1367116889_2916.jpg