Hexo
0%

队列

Posted on Edited on In

前言:学习数据结构的队列

基本介绍

与栈相反，队列是一种先进先出的线性表。它只允许在表的一端进行插入，在另一端删除元素。(先进先出FIFO、后进后出LILO)

  • 队首(front):允许进行删除的一端称为队首
  • 队尾(rear):允许进行插入的一端为队尾

队列中没有元素时称为空队列

  • 在空队列中依次加入元素a1,a2，……，an之后，a1是队首元素，an是队尾元素。显然，退出队列的次序也只能是a1，a2，……，an，即队列的修改是依先进先出的原则进行

image-20240419140722386

队列的顺序存储表示

利用一组连续的存储单元(一维数组)依次存放从队首到队尾的各个元素，称为顺序队列

对于队列，和顺序栈相类似，也有动态和静态之分。

静态顺序队列的类型定义

1
2
3
4
5
6
#define MAXI_SIZE  100
typedef struct quene{
    ElemType array[MAX_SIZE];
    int front;
    int rear;
}SqQuene;
  • **队首指针(front)和队尾指针(rear)**，分别指向队首元素和队尾元素。

与栈类似，队列进行顺序存储时，也常空出一个数组元素空间！目的:

  1. 识别队列空和队列满2种状态；
  2. 规避队列数组下标越界[非法]的问题

image-20240421170034782

下面用代码呈现:

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
//初始化静态队列
SqQuene Init_CirQuene(){
    SqQuene Q;  //定义一个队列
    Q.front = Q.rear = 0;  //队头&队尾都指向0
    return(Q);  //返回队列Q
}
//将数据元素e插入到循环队列Q的队尾(空出a[n - 1]的队列)
Status Insert_CirQuene(SqQuene &Q,ElemType e){
    //队满，返回错误标志
    if((Q.rear + 1) % MAX_SIZE == Q.front){
        return ERROR;
    }
    //(a)e元素入队
    Q.array[Q.rear] = e;
    //(b)队尾指针向前移动
    Q.rear = (Q.rear + 1) % MAX_SIZE;
    return OK;  //(c)入队成功
}

//将循环队列Q的队首元素出队(空出a[n - 1]的队列)
Status Delete_CirQuene(SqQuene &Q,ElemType *x){
    //队空，返回错误标志
    if(Q.front == Q.rear){
        return ERROR;
    }
    
    //(a)取队首元素
    *x = Q.array[Q.front];
    
    //(b)队首指针向前移动
    Q.front = (Q.front + 1) % MAX_SIZE;
    
    return OK;
}
//打印输出"顺序队列"
void show(SqQuene &Q){
    //(a)顺序队列为NULL空
    if(Q.front == Q.rear){
        cout << "循环队列(长度 = 0，为空!)\n\n";
        return;
    }
    
    //(b)顺序队列的元素从头到尾逐个输出，格式:"队列(长度 = n):e1，e2……，en"
    cout << "循环队列(长度 = " << (Q.rear - Q.front + MAX_SIZE) % MAX_SIZE << "):";
    int idx = Q.front;
    while(idx != Q.rear){  //空出a[n - 1]的队列
        cout << Q.array[idx] <<",";  //输出当前队列元素[idx]
        
        //游标idx向前移动
        idx = (idx + 1) % MAX_SIZE;
    }
    cout << end1 << end1;  //换行输出
}
//创建程序
int main(){
    //初始化顺序队列
    SqQuene quene = Init_CirQuene();
    
    show(quene);  //显示quene的信息
    
    //进队列
    ElemType x = 123;
    ElemType y =34;
    
    //Insret_CirQuene(quene, 111);  //入队列111
    
    Status flagI1 = Insert_CirrQuene(quene, x);  //入队列x
    
    Status flagI2 = Insert_CirQuene(quene,y);  //入队列y
    
    show(quene);
    
    //出队列
    ElemType temp;
    //出队列第1个元素
    Status flag01 = Delete_CirQuene(quene, &temp);  //出队列元素存放于temp中
    if(flag01 == OK){
        cout << "[成功],出队列元素temp = " << tmep <<end1;
    }else{
        cout << "{出队列失败！}" << end1;
    }
    
    show(quene);  //显示quene的信息
    
    //出队列第二个元素
    Status flag02 = Delete_CirQuene(quene, &temp);  //出队列元素存放于temp中
    if(flag02 == OK){
        cout << "[成功]，出队列元素temp = " << temp << end1;
    }else{
        cout << "{出队列失败！}" << end1;
    }
    
    show(quene);  //显示quene的信息
    
    //出队列第三个元素
    Status flag03 = Delete_CirQuene(quene, &temp);  //出队列存放于temp中
    if(flag03 == OK){
        cout << "[成功]，出队列元素temp = " << temp <<end1;
    }else{
        cout << "{出队列失败！}" << end1;
    }
    
    show(quene);  //显示quene的信息
    
    //返回主函数执行状态
    return 0;
}