【数据结构】队列的基本操作——基本实现 | 初始化 | 出入队列

目录：

• 队列
  • 1. 循环数组实现
  • 2. 队列的指针实现
  • 3. 队列的初始化
  • 4. 入队列
  • 5. 出队列

队列

队列的特性是先进后出，即先进入队列的元素，最后出队列。
队列的实现方式有两种，一种是循环数组实现，另一种是指针实现。

1. 循环数组实现

循环数组实现队列，需要一个首位置，一个末位置，还有一个数组。
以下是一循环数组创建的队列示例：

#define maxlength 100
typedef struct{
    int front;
    int rear;
    int data[maxlength];
}Queue;
1
2
3
4
5
6

2. 队列的指针实现

队列的指针实现，需要一个队列节点，还需要一个队列型。

队列与其他数据结构有一点不同，例如在栈的指针实现过程中，只需要一个栈顶指针，而在队列的指针实现中，需要两个指针，一个指向队列的头，一个指向队列的尾。所以队列需要单独定义一个结构体，而栈只需要一个结构体指针即可。

以下是一个队列节点的示例：

struct celltype{
    int data;
    struct celltype *next;
}
1
2
3
4

在这个节点中有两个域，一个域为数据域，另一个域为指向下一个节点的指针。

以下是一个队列的示例：

struct QUEUE{
    struct celltype *front;
    struct celltype *rear;
}
1
2
3
4

在队列中，front指向队列的头，rear指向队列的尾。

3. 队列的初始化

void Init(QUEUE *Q)
{
    (*Q).front = (struct celltype *)malloc(sizeof(struct celltype));
    (*Q).front->next=NULL; //创建一个空节点，并将其作为队列的头
    (*Q).rear = (*Q).front; //将尾指针指向头指针
}
1
2
3
4
5
6

队列的初始化即为队列分配存储空间，并初始化front和rear。

4. 入队列

下面将介绍队列中两个比较重要的操作，一个是入队列，一个是出队列。(下文中的队列均指指针实现队列)
其中实现的方式为，先从队列的末尾插入元素，即先创建一个节点，然后将其插入到队列的末尾。当需要出队列的时候，从队列的头开始出队列。

下面是入队列的示例：

void push(QUEUE *Q, int x)
{
    struct celltype *p;
    p = (struct celltype *)malloc(sizeof(struct celltype)); // 创建新的节点，使其位于队列的末尾
    p->data = x; // 将数据赋值给新节点
    p->next = NULL; // 将新节点的指针域置空
    (*Q).rear->next = p; // 将新节点插入到队列的末尾
    (*Q).rear = p; // 将尾后指针指向新节点
}

1
2
3
4
5
6
7
8
9
10

这里对

    (*Q).rear->next = p; // 将新节点插入到队列的末尾
    (*Q).rear = p; // 将尾后指针指向新节点
1
2

这两行代码做解释，解答为什么不能只写最后一行，而需要两行都写：

第一行是将新节点插入到队列的末尾，但是此时尾后指针并没有指向新节点，所以需要将尾后指针指向新节点。
第二行是将尾后指针指向新节点，此时新节点已经插入到队列的末尾，所以需要将尾后指针指向新节点。也就是说，Q->rear只是一个标志，他的存在就是为了得到最后一个节点的位置，而并不是固定的某个元素

5. 出队列

下面是出队列的示例：

void pop(QUEUE *Q,int *x)
{
    struct celltype *p;
    p=(*Q).front->next; //将队列的头节点的指针赋值给p
    *x=p->data; //将p节点的数据赋值给x
    (*Q).front->next=p->next; //将p节点的指针域赋值给队列的头节点的指针域
    free(p); //释放p节点
}

1
2
3
4
5
6
7
8
9