抽象数据类型（ADT）---队列

发表于 分类于 阅读次数：

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

简介

  队列(queue)是具有特殊属性的列表。第一，新的项目只能被添加到列表结尾处；第二，项目只能从列表开始处被移除。可以将队列看成一群人排队买票，您在队尾加入，买完票从队首离开。队列是一种“先进先出（First in, First out）”的数据形式。

类型名称 队列
类型属性： 可保存一个项目序列
类型操作： 把队列初始化为空列队列
确定队列是否为空
确定队列是否已满
确定队列中项目的个数
向列表末尾添加项目
遍历队列中的每个项目
从队列首端删除和恢复项目
清空队列

定义接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/* queue.h -- 队列接口 */
#pragma c9x on  // 启用C99的特性
#ifndef _QUEUE_H    // 防止重复导入
#define _QUEUE_H
#include <stdbool.h>

// 插入 Item 定义
typedef int Item;   // 这里的Item表示一个整数值

#define MAXQUEUE 10  // 队列最大项目数

typedef struct node   // 节点 包含item，以及下一个节点的位置信息
{
    Item item;
    struct node * next;
} Node;

typedef struct queue   // 记录队列的头，尾，个数
{
    Node * front;   // 队首
    Node * rear;    // 队尾
    int items;
} Queue;

/* 初始化队列 */
void InitializeQueue(Queue * pq);

/* 判断队列是否已满 */
bool QueueIsFull(const Queue * pq);

/* 判断队列是否为空 */
bool QueueIsEmpty(const Queue * pq);

/* 返回项目个数 */
int QueueItemCount(const Queue * pq);

/* 队列添加项目 */
bool EnQueue(Item item, Queue * pq);

/* 队列删除项目 */
bool DeQueue(Item * pitem, Queue * pq);

/* 清空队列 */
void EmptyTheQueue(Queue * pq);

#endif

实现接口

添加项目

向队列中添加项目步骤：

  1. 创建新的节点
  2. 把项目复制到新节点
  3. 设置节点的next指针为NULL,表明该节点是列表中最后一个节点
  4. 设置当前尾节点的next指针指向新节点，从而将新节点链接到队列中。
  5. 把rear指针设置为指向新节点，以便找到最后的节点。
  6. 项目个数加一。

CopyToItem作为静态函数把项目复制到一个节点中

1
static void CopyToNode(Item item, Node * pn)

此外函数还需考虑两种情况。首先，队列为空，那么front就指向新节点。此时，新节点既是队首也是队尾。其次，如果新节点分配空间失败，需要执行一些操作。因此，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* 队列添加项目 */
bool EnQueue(Item item, Queue * pq)
{
    Node * pnew;    // 创建新的节点

    if(QueueIsFull(pq))    // 判断队列是否为空
        return false;
    pnew = (Node *)malloc(sizeof(Node));   // 为新节点分配空间
    if(pnew == NULL)
    {
        fprintf(stderr, "Unable to allocate memory!");
        exit(EXIT_FAILURE);
    }
    CopyToNode(item, pnew);   // 把项目复制到新节点上
    pnew->next = NULL;          // 新节点next置为空
    if(QueueIsEmpty(pq))
        pq->front = pnew;   // 队列为空，新节点就作为队首
    else
        pq->rear->next = pnew;    // 当前队尾的next指向新节点 
    pq->rear = pnew;       // 记录新节点为队尾
    pq->items++;        // 项目+1
    return true;
}

删除项目

从队列首端删除项目包括下列步骤：

  1. 把项目复制到一个给定变量中。
  2. 释放空闲节点使用的内存
  3. 重置首指针，使其指向队列中的下一项。
  4. 如果最后一项被删除，把首位均重置为NULL.
  5. 项目数减一。

CopyToItem()把一个节点项目复制到一个Item变量

1
static void CopyToItem(Node * pn, Item * pi)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* 队列删除项目 */
bool DeQueue(Item * pitem, Queue * pq)
{
    Node * pt; // 声明一个临时节点存放删除的队列首项

    if(QueueIsEmpty(pq))    // 判断队列是否为空
        return false;
    CopyToItem(pq->front, pitem);  // 把队首的项目复制到pitem
    pt = pq->front;            // 存放队首地址
    pq->front = pq->front->next;   // 更新当前队列的头
    free(pt);        // 释放删除的队首
    pq->items--;         // 项目-1
    if(pq->items == 0)   // 最后一项删除后，rear置为空
        pq->rear = NULL;
    return true;
}

这里需要注意的是，虽然没有front指针没有置为null，但其实在删除最后一项时，已经把front指针设置为被删除节点的next指针，因为最后一项节点的next为空，所以front也会置为空。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/* 队列类型的实现 */
#include <stdio.h>
#include <stdlib.h>
#include "queue.h"

// 局部函数
static void CopyToNode(Item item, Node * pn);
static void CopyToItem(Node * pn, Item * pi);

/* 初始化队列 */
void InitializeQueue(Queue * pq)
{
    pq->front = pq->rear = NULL;   //头尾置为空
    pq->items = 0;       // 项目数量为0
}

/* 判断队列是否已满 true/false */
bool QueueIsFull(const Queue * pq)
{
    return pq->items == MAXQUEUE;
}

/* 判断队列是否为空 */
bool QueueIsEmpty(const Queue * pq)
{
    return pq->items == 0;
}

/* 返回项目个数 */
int QueueItemCount(const Queue * pq)
{
    return pq->items;
}

/* 队列添加项目 */
bool EnQueue(Item item, Queue * pq)
{
    Node * pnew;

    if(QueueIsFull(pq))
        return false;
    pnew = (Node *)malloc(sizeof(Node));
    if(pnew == NULL)
    {
        fprintf(stderr, "Unable to allocate memory!");
        exit(EXIT_FAILURE);
    }
    CopyToNode(item, pnew);   // 把项目复制到新节点上
    pnew->next = NULL;
    if(QueueIsEmpty(pq))
        pq->front = pnew;   // 队列为空，新节点就作为队首
    else
        pq->rear->next = pnew;    // 当前队尾的next指向新节点 
    pq->rear = pnew;       // 记录新节点为队尾
    pq->items++;
    return true;
}

/* 队列删除项目 */
bool DeQueue(Item * pitem, Queue * pq)
{
    Node * pt;

    if(QueueIsEmpty(pq))
        return false;
    CopyToItem(pq->front, pitem);  // 把队首的项目复制到pitem
    pt = pq->front;
    pq->front = pq->front->next;   // 更新当前队列的头
    free(pt);
    pq->items--;
    if(pq->items == 0)
        pq->rear = NULL;
    return true;
}

/* 清空队列 */
void EmptyTheQueue(Queue * pq)
{
    Item dummy;
    while(!QueueIsEmpty(pq))
        DeQueue(&dummy, pq);
}

/* 局部函数 */

static void CopyToNode(Item item, Node * pn)
{
    pn->item = item;
}

static void CopyToItem(Node * pn, Item * pi)
{
    *pi = pn->item;
}

使用接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/* use_q.c -- 测试Queue的接口驱动程序 */
/* cpmile with Queue */
#include <stdio.h>
#include "queue.h"

int main(void)
{
    Queue line;
    Item temp;
    char ch;

    InitializeQueue(&line);
    puts("Testing the Queue interface. Type a to add a value, ");
    puts("type d to delete a value, and type q to quit");
    while((ch = getchar()) != 'q')
    {
        if(ch != 'a' && ch != 'd')
            continue;
        if(ch == 'a')
        {
            printf("Integer to add: ");
            scanf("%d", &temp);
            if(!QueueIsFull(&line))
            {
                printf("Putting %d into queue\n", temp);
                EnQueue(temp, &line);
            }
            else
                puts("Queue is full!");
        }
        else
        {
            if(QueueIsEmpty(&line))
                puts("Nothing to delete!");
            else
            {
                DeQueue(&temp, &line);
                printf("Removing %d from queue\n", temp);
            }
        }
        printf("%d items in queue\n", QueueItemCount(&line));
        puts("Type a to add, d to delete, q to quit: ");
    }
    EmptyTheQueue(&line);
    puts("Bye!");
    return 0;
}

程序运行：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Testing the Queue interface. Type a to add a value,
type d to delete a value, and type q to quit
a
Integer to add: 40
Putting 40 into queue
1 items in queue
Type a to add, d to delete, q to quit:
a
Integer to add: 55
Putting 55 into queue
2 items in queue
Type a to add, d to delete, q to quit:
a
Integer to add: 24
Putting 24 into queue
3 items in queue
Type a to add, d to delete, q to quit:
d
Removing 40 from queue
2 items in queue
Type a to add, d to delete, q to quit:
d
Removing 55 from queue
1 items in queue
Type a to add, d to delete, q to quit:
d
Removing 24 from queue
0 items in queue
Type a to add, d to delete, q to quit:
q
Bye!