队列

发表于 | 更新于 | 分类于 | 阅读次数： | 字数： 1,770 | 阅读时长： 9

队列的基本概念：

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

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

链队列：

用链表表示的队列简称为链队列。

链队列的表示与实现：

queue.h

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
//queue.h
//单链队列的表示与实现

//------------队列的链式存储结构----------------
typedef struct QNode{
    QElemType date;
    struct QNode *next;
}QNode, *QueuePtr;

typedef struct {
    QueuePtr front; //队列指针
    QueuePtr rear; //队尾指针
    int len;
}LinkQueue;

//-----------基本操作的函数原型说明---------------

//构造一个空队列Q
Status InitQueue(LinkQueue &Q){
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    if(!Q.front)
        exit(OVERFLOW);
    Q.front->next = NULL;
    Q.len = 0;
    return OK;

}//InitQueue

//销毁队列Q
Status DestoryQueue(LinkQueue &Q){
    while(Q.front){
        Q.rear = Q.front->next;
        free(Q.front);
        Q.front = Q.rear;
    }
    cout<<"队列销毁成功！"<<endl;
    return OK;
}//DestoryQueue

//清空队列Q
Status ClearQueue(LinkQueue &Q){
    Q.front = Q.rear;
    Q.front->next = NULL;
    return OK;
}//ClearQueue

//判空
Status QueueEmpty(LinkQueue Q){
    if(Q.front == Q.rear){
        return TRUE;
    }else{
        return FALSE;
    }

}//QueueEmpty

//返回Q的元素的个数
int QueueLength(LinkQueue Q){
    return Q.len;
}//QueueLength

//若队列不为空，用e返回队列的头元素，并返回OK，否则返回ERROR
Status GetHead(LinkQueue Q, QElemType &e){
    if(!QueueEmpty(Q)){
        e = Q.front->next->date;
        return OK;
    }else{
        return ERROR;
    }
}//GetHead

//插入元素e为Q的新的队尾元素
Status EnQueue(LinkQueue &Q, QElemType e){
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    if(!p)
        exit(OVERFLOW);
    p->date = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
    Q.len++;
    return OK;
}//EnQueue

//若队列不为空，则删除Q的队头元素，用e返回其值
//并返回OK，否则返回ERROR
Status DeQueue(LinkQueue &Q, QElemType &e){
    if(Q.front == Q.rear)
        return ERROR;
    QueuePtr p = Q.front->next;
    e = p->date;
    Q.front->next = p->next;
    if(Q.rear == p)
        Q.rear = Q.front;
    free(p);
    Q.len--;
    return OK;
}//DeQueue

//队列的遍历
Status QueueTraverse(LinkQueue Q){
    if(!QueueEmpty(Q)){
        QueuePtr p = Q.front->next;
        while(p){
            cout<<p->date<<"  ";
            p = p->next;
        }
        cout<<endl;
    }else{
        cout<<"这个队列没有元素！"<<endl;
    }
}//QueueTraverse

baes.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//base.h
//-----公用的常量和类型----------
#include<iostream>
#include<stdlib.h>
#include<time.h>
using namespace std;
#include<malloc.h>
#include<string.h>

//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int Status;
typedef int QElemType;

text.cpp

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
//text.cpp
//测试队列基本操作

#include "base.h"
#include "queue.h"

int main(){
    LinkQueue Q;
    QElemType e;
    InitQueue(Q);
    cout<<"队列遍历：";
    QueueTraverse(Q);
    for(e = 0; e < 10; e++){
        EnQueue(Q, e);
    }
    cout<<"队列遍历：";
    QueueTraverse(Q);
    cout<<"队列内元素个数为："<<QueueLength(Q)<<endl;
    DeQueue(Q, e);
    cout<<"删除的队列元素为："<<e<<endl;
    cout<<"删除元素后队列的遍历：";
    QueueTraverse(Q);
    EnQueue(Q, 15);
    cout<<"插入15后队列的遍历：";
    QueueTraverse(Q);
    GetHead(Q, e);
    cout<<"获得队列的对头元素："<<e<<endl;
    if(QueueEmpty(Q))
        cout<<"判空：队列为空！"<<endl;
    else
        cout<<"判空：队列不为空！"<<endl;
    ClearQueue(Q);
    cout<<"请空队列后的遍历：";
    QueueTraverse(Q);
    DestoryQueue(Q);
    return OK;
}

链队列程序测试结果：

链队列

图：链队列测试结果

循环队列：

循环队列使用顺序表的存储结构。

循环队列的代码实现：

sqQueu.h

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
95
//sqQueue.h
//循环队列的基本操作

//-----循环队列---队列的顺序存储结构------
#define MAXQSIZE 100 //最大队列长度

typedef struct{
    QElemType *base; //初始化的动态分配存储空间
    int front; //头指针，若队列不空，指向队列对头元素
    int rear; //尾指针，若队列不空，指向队列队尾的下一个元素
}SqQueue;

//------循环队列的基本操作的算法描述-------

//构造一个空队列Q
Status InitQueue_Sq(SqQueue &Q){
    Q.base = (QElemType *)malloc(MAXQSIZE * sizeof(QElemType));
    if(!Q.base)
        exit(OVERFLOW);
    Q.front = Q.rear = 0;
    return OK;
}//InitQueue_Sq

//销毁队列Q
Status DestoryQueue_Sq(SqQueue &Q){
   free(Q.base);
   Q.front = Q.rear = 0;
   cout<<"队列销毁成功！"<<endl;
   return OK;
}//DestoryQueue_Sq

//清空队列Q
Status ClearQueue_Sq(SqQueue &Q){
    Q.front = Q.rear = 0;
    return OK;
}//ClearQueue_Sq

//判空
Status QueueEmpty_Sq(SqQueue Q){
    if(Q.front == Q.rear){
        return TRUE;
    }else{
        return FALSE;
    }

}//QueueEmpty_Sq

//返回Q的元素的个数
int QueueLength_Sq(SqQueue Q){
    return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}//QueueLength_Sq

//若队列不为空，用e返回队列的头元素，并返回OK，否则返回ERROR
Status GetHead_Sq(SqQueue Q, QElemType &e){
    if(!QueueEmpty_Sq(Q)){
        e = Q.base[Q.front];
        return OK;
    }else{
        return ERROR;
    }
}//GetHead_Sq

//插入元素e为Q的新的队尾元素
Status EnQueue_Sq(SqQueue &Q, QElemType e){
    if((Q.rear + 1) % MAXQSIZE == Q.front)
        return ERROR;  //队列满
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MAXQSIZE;
    return OK;
}//EnQueue_Sq

//若队列不为空，则删除Q的队头元素，用e返回其值
//并返回OK，否则返回ERROR
Status DeQueue_Sq(SqQueue &Q, QElemType &e){
    if(Q.front == Q.rear)
        return ERROR; //队列空
    e = Q.base[Q.front];
    Q.front = (Q.front + 1) % MAXQSIZE;
    return OK;
}//DeQueue_Sq

//队列的遍历
Status QueueTraverse_Sq(SqQueue Q){
    if(!QueueEmpty_Sq(Q)){
        int p = Q.front;
        while((p % MAXQSIZE) != Q.rear){
            cout<<Q.base[p++]<<"  ";
        }
        cout<<endl;
        return OK;
    }else{
        cout<<"这个队列没有元素！"<<endl;
        return ERROR;
    }
}//QueueTraverse_Sq

####text.cpp

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
//text.cpp
//测试队列基本操作

#include "base.h"
#include "sqQueue.h"

int main(){
  	QElemType e;
    SqQueue SQ;
    InitQueue_Sq(SQ);
    cout<<"队列遍历：";
    QueueTraverse_Sq(SQ);
    for(e = 0; e < 10; e++){
        EnQueue_Sq(SQ, e);
    }
    cout<<"队列遍历：";
    QueueTraverse_Sq(SQ);
    cout<<"队列内元素个数为："<<QueueLength_Sq(SQ)<<endl;
    DeQueue_Sq(SQ, e);
    cout<<"删除的队列元素为："<<e<<endl;
    cout<<"删除元素后队列的遍历：";
    QueueTraverse_Sq(SQ);
    EnQueue_Sq(SQ, 13);
    cout<<"插入13后队列的遍历：";
    QueueTraverse_Sq(SQ);
    GetHead_Sq(SQ, e);
    cout<<"获得队列的对头元素："<<e<<endl;
    if(QueueEmpty_Sq(SQ))
        cout<<"判空：队列为空！"<<endl;
    else
        cout<<"判空：队列不为空！"<<endl;
    ClearQueue_Sq(SQ);
    cout<<"清空队列后的遍历：";
    QueueTraverse_Sq(SQ);
    DestoryQueue_Sq(SQ);
    return OK;
}

循环队列测试结果：

循环队列

图：循环队列测试结果

坚持原创技术分享，您的支持将鼓励我继续创作！