数据结构_知识点_队列

1. 队列定义

//顺序存储队列
typedef struct
{
    elemType data[maxSize];
    int front, rear;        
}queue; 

//链表存储队列
typedef struct Node
{
    elemType data;
    Node *next;
};

typedef struct queue
{
    Node *front;
    Node *rear;
};

通过队列的定义可以看出，队列除了按先后顺序都数据进行存储外，还需要两个指针，分别代表队头和队尾。

2. 进队出队操作

出队操作将队头指针往后移动一位，进队操作则将队尾指针向后移动一位

顺序存储队列

进队

bool enterQueue(queue &q, elemType data)
{
    if(q.rear == maxSize)
        return false;
    //队尾往后移一位，添加数据
    q.rear++;
    q.data[q.rear] = data;
    
    return true;    
}

出队

elemType outQueue(queue &q)
{
    //判断队列是否为空
    if(q.front == q.rear)
        return -9999;
    //返回队头元素，队头指针往后移动一位 
    return q.data[q.front++];
}

链表存储队列

进队

bool enterQueue(queue &q,elemType e)
{
    Node *p;
    p = (Node *)malloc(sizeof(Node));
    
    p->data = e;
    p->next = NULL;
    
    //队列最后一个元素指针域指向新添加的元素
    q.rear->next = p;
    //队尾指针指向新的队尾
    q.rear = p;
    
    return true;
}

出队

elemType outQueue(queue &q)
{
    //判断队伍是否为空
    if(q.front == q.rear)
        return -999;
    
    elemType e;
    e = q.front->next->data;
    
    //使队头指针指向新的队头
    Node *p = q.front->next;
    q.front->next = p->next;
    //释放已经出队的结点的空间  
    free(p);
    
    return e;
}

3. 特殊队列——循环队列与双端队列

此处仅讨论循环队列。循环队列是基于顺序表，与普通队列不同的是

1. 指针移动到数组最后的时候需要进行处理使之指向数组最前
2. 如何计算队伍长度
3. 如何判断队列空队，满队

问题1

//当指针指向最后一个位置时，再进一位时候，就会指向0
front = (front + 1) % maxSize;

问题2

//普通队列
length = q.rear - q.front;
//循环队列
length = (q.rear - q.front + maxSize) % maxSize;

与普通队列区别在于，循环队列存在 q.rear < q.front 的情况。

1. 当 q.rear < q.front 时，q.rear - q.front就等于队列中为空的位置个数的相反数，(q.rear - q.front + maxSize)就等于队伍长度，再%maxSize还是等于长度本身
2. 当 q.rear > q.front 时，(q.rear - q.front + maxSize) % maxSize等于q.rear - q.front 即队伍长度

问题3
一般情况下循环队列空的时候q.rear = q.front，队满的时候q.rear = q.front。所以无法区分队空，队满。

1. 添加tag，队空为0，队满为1.
2. 添加size属性，每次 出队/进队 后，修改队列长度
3. rear指向最后一个元素的后一个位置，队列中空出一个空位。
   (1) 队空的条件仍为：q.front == q.rear
   (2) 队满的条件为：(q.rear + 1) % maxSize == q.front
   此时队满只存在两种情况：
   (1) rear == maxSize && front == 0
   (2) rear > front
   都能通过(rear + 1) % maxSize 求得front。