队列

发表于 | 分类于
字数统计: 1.5k

队列学习笔记

队列及其抽象数据类型

基本概念

队列是一种只允许在表的一端进行插入操作，而在另一端进行删除操作的线性表（先进先出表）。允许进行删除的这一段叫做队列的头，允许进行插入的这一端叫做队列的尾。当队列中没有任何元素时，称为空队列。队列的插入操作通常称为进队列或入队列，队列的删除操作通常称为退队列或出队列。

抽象数据类型

1
2
3
4
5
6
7
8
9
10
11
ADT Queue is
    operations
    Queue createEmptyQueue(void)/*创建一个空队列*/
    int isEmptyQueue(Queue qu)/*判断队列qu是否为空队列*/
    void enQueue(Queue qu,DataType x)
    /*往队列qu尾部插入一个值为x的元素*/
    void deQueue(Queue qu)
    /*往队列qu头部删除一个元素*/
    DataType frontQueue(Queue qu)
    /*求队列qu头部元素的值*/
end ADT Queue

队列的顺序表示

存储结构

1
2
3
4
5
6
7
struct SeqQueue{/*顺序队列类型定义*/
    int MAXNUM;	/*队列中最大元素个数*/
    int f,r;	/*f指出实际队头元素所在的位置，r指出实际队尾元素所在位置的下一个位置*/
    DataType *q;
}
typedef struct SeqQueue * PSeqQueue;
/*顺序队列类型的指针类型*/

假设paqu是PSeqQueue类型的变量,则：

  1. paqu->f存放即将要被删除的元素的下标
  2. paqu->r存放即将要被插入的元素的下标
  3. paqu->q[paqu->f]表示当前队列头部的元素
  4. paqu->q[paqu->r]表示当前队列尾部的（即将插入的）的元素
  5. 初始时paqu->f=paqu->r=0
  6. 当前队列中元素个数为paqu->r-paqu->f
  7. 当paqu->r=paqu->f时，元素的个数为0，即为空队列。

队列溢出

在队列中，由于数组是静态结构，而队列是动态结构，可能出现队列溢出问题。当队列满时，再作进队操作，这种现象称为上溢，当对空时，作删除操作，这种现象称为下溢。

由于队列中经常要执行插入和删除运算，而每运行一次插入或删除，paqu->r或paqu->f就增加1，使得队列中的元素被删除后，其空间就永远使用不到了，当paqu->r=MAXNUM时，再作插入运算就会产生溢出，而实际上这时队列的前端可能还有许多可用的位置，因此，这种现象称为假溢出。

环形队列

解决假溢出通常采用的方法是：把数组paqu->q[MAXNUM]从逻辑上看成一个环，这种队列也成为环形队列。当表中已有MAXNUM-1个节点时，如果还要插入，paqu->r和paqu->f就会重合，这与空队列的情形相同，为了区分空队列与满队列两种情况的环形队列，一般是牺牲队列中的一个节点，当的队列中已有MAXNUM-1个节点时就称为满，再要插入就发生溢出。

基本运算的实现

创建一个空队列
1
2
3
4
5
6
7
8
9
/*创建一个空队列*/
PSeqQueue  createEmptyQueue_seq( void ) {  
    PSeqQueue paqu = (PSeqQueue)malloc(sizeof(struct SeqQueue));
    if (paqu==NULL)
        printf("Out of space!! \n");
    else
        paqu->f = paqu->r = 0;
    return paqu;
}
判断队列是否为空
1
2
3
4
/*判队列是否为空队列*/
int  isEmptyQueue_seq( PSeqQueue paqu ) {
    return paqu->f == paqu->r;
}
进队运算
1
2
3
4
5
6
7
8
9
10
11
void enQueue_seq(PSeqQueue paqu, DataType x)
{
    /*再队尾插入元素x*/
    if((paqu->r + 1)%MAXNUM == paqu->f)
        printf("Full Queue!\n");
    else
    {
        paqu->q[paqu->r] = x;
        paqu->r = (paqu->r+1)%MAXNUM;
    }
}
出队运算
1
2
3
4
5
6
7
8
9
10
void deQueue_seq(PSeqQueue paqu)
{
    /*删除队列头部元素*/
    if(paqu->f == paqu->r)
        printf("Empty Queue.\n");
    else
    {
        paqu->f = (paqu->f+1)%MAXNUM;
    }
}
取队列头部元素运算
1
2
3
4
5
6
7
DataType fromtQueue_seq(PSeqQueue paqu)
{
    if(paqu->f == paqu->r)
        printf("Empty Queue.\n");
    else
        return (paqu->q[paqu->f]);
}

队列的链接表示

存储结构

队列的链接表示就是用一个单链表来表示队列，队列中的每个元素对应链表中的一个结点，结点的结构与单链表中结点的结构一样。为了强调队头和队尾都是队列的属性，对队列增加了一层封裝，引入 LinkQueue结构的定义。这样存储的队列简称链接队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
struct Node;
typedef struct Node * PNode;
struct Node{/*节点结构*/
    DataType info;
    PNode link;
};
struct LinkQueue{/*链接队列类型定义*/
	PNode f;	/*头指针*/
	PNode r;	/*尾指针*/

};
typedef struct LinkQueue * PLinkQueue;
/*链接队列类型的指针类型*/

假设plqu是PLinkQueue类型的变量，则：

  1. plqu->f为队列的头指针，指向队列中第一个节点
  2. plqu->r是队列的尾指针，指向队列中最后一个节点
  3. 当plqu->f或plqu->r为NULL时队列为空

基本运算的实现

创建空队列
1
2
3
4
5
6
7
8
9
10
11
PLinkQueue createEmptyQueue_link(void){
    PLinkQueue plqu;
    plqu = (PLinkQueue)malloc(sizeof(struct LinkQueue));
    if (plqu != NULL){
        plqu->f = NULL;
        plqu->r = NULL;
    }
    else 
        printf("Out of Space!!\n");
    return plqu;
}
判断队列是否为空
1
2
3
int isEmptyQueue_link(PLinkQueue plqu){
    return (plqu->f == NULL);
}
进队列运算
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void enQueue_link(PLinkQueue plqu,DataType x){
    PNode p;
    p = (PNode)malloc(sizeof(struct Node));
    /*申请新节点空间*/
    if(p == NULL)/*申请新节点失败*/
        printf("out of space!");
    else
    {
        p->info = x;
        p->link = NULL;/*填写新节点信息*/
        if(plqu->f == NULL)/*插入前是空队列*/
            plqu->f = p;
        else
            plqu->r->link = p /*将新节点插入*/
        plqu->r = p;/*修改队尾指针*/
    }
}
出队列运算
1
2
3
4
5
6
7
8
9
10
11
void deQueue_link(PLinkQueue plqu){
    PNode p;
    if(plqu->f==NULL)/*队列已空*/
        printf("Empty queue.\n");
    else
    {
        p = plqu->f;
        plqu->f = p->link;/*修改对头指针*/
        free(p);/*释放已经删除节点空间*/
    }
}
取队列头部元素的值
1
2
3
4
5
6
DataType frontQueue_link(PLinkQueue plqu){
    if (plqu->f == NULL)/*队列已空*/
       	printf("Empty queue\n");
    else
        return (plqu->f->info);
}