线性表--队列

概述

队列是一种限定性线性表，广泛应用于计算机系统中。它只许在表的一端进行插入，在另一端进行删除。由于它的操作特性与我们平时排队一样，体现出了先进先出的特点，所以把这种数据结构称为队列。

---

队列的数据结构

#define MAXSIZE <最大元素数>

typedef struct 
{
    datatype data[MAXSIZE];        //队员的存储空间
    int front, rear;               //队头队尾指针
}Sequeue;

使用的时候定义一个指向队列的指针变量，Sequeue *sq;申请一个顺序队的存储空间 sq = (Sequeue ×) malloc(sizeof(Sequeue));

---

顺序队列的“假溢出”

顺序队列的操作非常简单，置空队就是sq -> front = sq -> rear ;如队就给队列尾指针加1，出队就给队列头指针加1。但是仔细想想，这样做的操作是会造成一些问题的，好比“假溢出”。

假设我们设置一个表格，里面有10个格，刚开始的时候，我们都知道，将front，rear指针都初始化为-1，随着入队的操作，我们发现rear指针不断后移;然后进行出队操作，这个时候队头指针也在不断的后移，我们发现，整个队列会向后移动，当队尾指针指向最后时，此时极有可能前面的表格是空着的，这就会产生一个“假满员”的情况，这就是“假溢出”，也是我们使用循环队列最主要的原因。

---

循环队列

循环队列解决了上述问题，它不会造成“假溢出”的状态。因为循环队列就像一个环一样，元素的插入和删除并不会造成队列元素整体的后移。

---

循环队列的构造方法

数学上常用求模运算来构造循环队列。具体操作如下：

• 入队：sq -> rear = (sq -> rear+1) % MAXSIZE
• 出队：sq -> front = (sq -> front+1) % MAXSIZE

---

循环队列所造成的问题

虽然循环队列成功的解决了上述“假溢出”的问题，但并不代表我上面说的循环队列已经没有问题了。我们发现，在循环队列中，队列空的时候判断条件是 sq -> rear == sq -> front，在队列满的时候和队列空的时候的判断条件是一样的，所以我们规定就是在循环队列中一般少用一个元素空间，所以当队满的时候，条件自然变成了队尾指针加1等于队头指针就是队满的时候：(sq -> rear+1) % MAXSIZE == sq -> front。

还有一种不常用的方法就是附设一个记录队列中元素个数的变量，如num，当num == 0时就是队空，当num == MAXSIZE时队满。我们常用第一种方法。

---

循环队列的操作

1.置空队

Sequeue *Init_queue(Sequeue *q)
{
    q = malloc(sizeof(Sequeue));
    q -> front = q -> rear;
    return q;
}

---

2.入队

int In_sequeue(Sequeue *q, datatype x);
{
    /*判断队是否已满*/
    if((q -> rear+1) % MAXSIZE == q -> front)
        return -1;
    else
    {   
        q -> rear = (q -> rear+1) % MAXSIZE;
        q -> data[q -> rear] = x;
        return 0;
    }
}

---

3.出队

int Out_sequeue(Sequeue *q, datatype *x)
{
    /*判断队列是否已空*/
    if(q -> rear == q -> front)
    {
        return -1;
    }
    else
    {
        q -> front == (q -> front+1) % MAXSIZE;
        *x = q -> data[q -> front];    //读出队列头元素
        return 0;
    }
}

---

总结

总的来说，队列的基本操作和栈没有多大的区别。两者对比学习就可以了，还有关于链队的知识，其实就是将链表控制成队列的这种形式，拥有队列的特性，就是尾插法和第一个结点的删除，在此就不再赘述。