队列——队列的定义及基本操作（顺序存储队列和链队列的初始化、入队、出队、判空等）_初始化顺序存储队列

---

队列

 队列（Queue）简称队，也是一种操作受限的线性表，只允许在表的一端进行插入而在表的另一端进行删除。向队列中插入元素称为入队或进队，删除元素称为出队或离队。最早进队的也是最早出队的，故其操作特性是先进先出FIFO（First In First Out），故又称为先进先出的线性表。

• 队头Front：允许删除的一端，又称队首。
• 队尾Rear：允许插入的一端。

---

队列的存储

 队列的存储一般分为两种：顺序存储和链式存储。
 队列的顺序实现是指分配一块连续的的存储单元存放队列中的元素，并附设两个指针front和rear分别指示队头元素和队尾元素的位置。

 队列的顺序存储类型描述：

#define MaxSize 100
typedef struct SqQueue{
    ElemType data[MaxSize]; //存放队列元素
    int front,rear; //队头指针和队尾指针
}SqQueue;
1
2
3
4
5

 队列的链式表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表，头指针指向队头结点，尾指针指向对为节点，即单链表的最后一个结点。

 队列的链式存储类型描述：

typedef struct LinkNode{ //链式队列结点
    ElemType data;
    struct LinkNode *next;
}LinkNode;

typedef struct LinkQueue{ //链式队列
    LinkNode *front,*rear; //队列的队头和队尾指针
}LinkQueue;
1
2
3
4
5
6
7
8

---

队列的基本操作

 队列常见的基本操作包括：

• 初始化队列InitQueue(&Q);
• 判空Empty(Q);
• 入队EnQueue(&Q, x);
• 出队DeQueue(&Q, &x);
• 读队首元素GetElem(Q, &x);

 说明：队头指针指向队头元素，队尾指针指向队尾元素的下一个位置。

---

顺序存储下队列的基本操作实现

 下图为一个元素最大个数为5的队列的队列操作情况。

• 起始状态（队空条件）：Q.front == Q.rear == 0。
• 进队操作：队不满时，先送值到队尾元素，再将队尾指针加1。
• 出队操作：队不空时，先取队头元素值，再将队头指针加1。

 但是，这样存在一个很大的问题，就是怎么判断队满？能否用rear=MaxSize作为队列满的条件呢？答案是否定的。由(d)可以看出，此时rear=MaxSize=5，但数组中仍然存在可以存放元素的空位置，因为原先入队的元素出队了，所以是一种假溢出。故引入了循环队列，在下面的内容中给出。

---

循环队列

 

 循环队列是将队列臆造为一个环状的空间，即把存储队列元素的表从逻辑上视为一个环，称为循环队列。
 当队首指针front=MaxSize-1后，再前进一个位置就自动到0，通过除法取余运算%来实现。

• 初始时：Q.front == Q.rear == 0
• 队首指针进1：Q.front = (Q.front+1)%MaxSize
• 队尾指针进1：Q.rear = (Q.rear+1)%MaxSize
• 队列长度：(Q.rear - Q.front + MaxSize)%MaxSize
• 出队入队时：指针都按顺时针方向进1，如上图所示。

---

1. 初始化

//初始化
void InitQueue(SqQueue &Q){ //初始化队首、队尾指针
    Q.front = Q.rear = 0;
}
1
2
3
4

---

2. 判空操作

 如上图所示，队空和队满时都由Q.front==Q.rear，为了区分是队空还是队满的情况，有三种处理方式：

• 牺牲一个单元来区分队空和队满，如上图d2所示，那么队满条件为(Q.rear+1)%MaxSize == Q.front，队空条件仍未Q.front == Q.front。队列中元素个数为(Q.rear-Q.front+MaxSize)%MaxSize。
• 增设表示元素个数的数据成员。这样队空的条件为Q.size == 0，队满的条件为Q.size == MaxSize。这两种情况都有Q.front == Q.rear。
• 类型中增设tag数据成员，tag等于0时，若因删除导致Q.front == Q.rear，则为队空；tag等于1时，若因插入导致Q.front == Q.rear，则为队满。

//判空操作，采用第一种方式
bool Empty(SqQueue Q){
    if(Q.rear==Q.front)return true;
    else return false;
}
1
2
3
4
5

---

3. 入队

//入队
void EnQueue(SqQueue &Q, int x){
    if((Q.rear+1)%MaxSize == Q.front)return; //队满
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear+1)%MaxSize;
}
1
2
3
4
5
6

---

4. 出队

//出队
void DeQueue(SqQueue &Q, int &x){
    if(Q.front==Q.rear)return;//空队
    x = Q.data[Q.front];
    Q.front = (Q.front+1)%MaxSize;
}
1
2
3
4
5
6

---

5. 读取队首元素

//读取队首元素
int GetElem(SqQueue Q){
    return Q.data[Q.front];
}
1
2
3
4

---

链式存储下队列的基本操作实现

---

1. 初始化

//初始化
void InitQueue(LinkQueue &Q){
    Q.front = (LinkNode*)malloc(sizeof(LinkNode)); //建立头结点
    Q.front->next = NULL; //初始为空
    Q.rear = Q.front;
}
1
2
3
4
5
6

---

2. 判空操作

//判空
bool Empty(LinkQueue Q){
    if(Q.front==Q.rear)  return true;
    else  return false;
}
1
2
3
4
5

---

3. 入队

//入队
void EnQueue(LinkQueue &Q, int x){
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    Q.rear->next = s;
    Q.rear = s;
}
1
2
3
4
5
6
7
8

---

4. 出队

void DeQueue(LinkQueue &Q, int &x){
    if(Q.front==Q.rear)return;//空队
    LinkNode *p = Q.front->next;
    x = p->data;
    Q.front->next = p->next;
    if(Q.rear==p){
        Q.rear = Q.front; //若原队列中只有一个结点，删除后变空
    }
    free(p);
}
1
2
3
4
5
6
7
8
9
10

---

5. 读取队首元素

//读取队首元素
int GetElem(LinkQueue Q){
    return Q.front->next->data;
}
1
2
3
4