第6章：队列

本章目标

  1. 理解队列的定义及其基本运算

  2. 掌握顺序队列各种操作实现

本章内容

队列

  • 一种特殊的线性表
  • 允许在一端进行插入，另一端进行删除
  • 插入的一端称为队尾，删除的一端称为队头
  • 插入元素称为入队，删除元素称为出队
  • 若队列中没有任何元素，则称为空队列

例如：

超市排队交费

打印任务调度

队列的存储结构

  • 顺序存储结构
    • 称为“顺序队列”
    • 是运算受限的顺序表
    • 用一组连续的存储空间依次存放从队头到队尾的元素
    • 使用一维数组实现
  • 链式存储结构

顺序队列

在容量为5的顺序队列中将J1-J3依次入队，然后J1出队

顺序队列的基本操作

  • 队列的初始化
  • 判断队列的状态（空或满）
  • 入队
  • 出队
  • 查询队头对象
  • 查询队列的元素个数

初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/// <summary>
/// 初始化
/// </summary>
/// <param name="capacity"></param>
public MyQueue(int capacity)
{
    items = new T[capacity];

    count = 0;
    head = 0;
    tail = 0;
}

/// <summary>
/// 初始化
/// </summary>
public MyQueue() : this(10) { }

判断队列状态

1
2
3
4
5
6
7
8
9
/// <summary>
/// 是否空队
/// </summary>
public bool IsEmpty => count == 0;

/// <summary>
/// 是否满队
/// </summary>
public bool IsFull => count == items.Length;

入队

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/// <summary>
/// 入队
/// </summary>
/// <param name="item"></param>
/// <exception cref="InvalidOperationException"></exception>
public void Enqueue(T item)
{
    if (IsFull)
    {
        throw new InvalidOperationException("队列已满");
    }

    //将元素放入队尾
    items[tail++] = item;

    //更新数量
    count++;
}
1
2
3
4
5
6
7
8
9
10
11
private void button1_Click(object sender, EventArgs e)
{
    MyQueue<string> quee=new MyQueue<string>();

    //入队
    quee.Enqueue("张三");
    quee.Enqueue("李四");
    quee.Enqueue("王五");
    quee.Enqueue("赵六");
    quee.Enqueue("田七");
}

出队

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/// <summary>
/// 出队
/// </summary>
/// <returns></returns>
/// <exception cref="InvalidOperationException"></exception>
public T Dequeue()
{
    if (IsEmpty)
    {
        throw new InvalidOperationException("队列为空.");
    }
    //队头元素
    T result = items[head];
    items[head] = default(T);

    //更新队头索引
    head++;

    //更新元素数量
    count--;

    //返回结果
    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
private void button2_Click(object sender, EventArgs e)
{
    MyQueue<string> quee = new MyQueue<string>();

    //入队
    quee.Enqueue("张三");
    quee.Enqueue("李四");
    quee.Enqueue("王五");
    quee.Enqueue("赵六");
    quee.Enqueue("田七");

    //出队
    string name = quee.Dequeue();
}

查询队头

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/// <summary>
/// 获取队头
/// </summary>
/// <returns></returns>
/// <exception cref="InvalidOperationException"></exception>
public T Peek()
{
    if (IsEmpty)
    {
        throw new InvalidOperationException("队列为空.");
    }

    return items[head];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
private void button3_Click(object sender, EventArgs e)
{
    MyQueue<string> quee = new MyQueue<string>();

    //入队
    quee.Enqueue("张三");
    quee.Enqueue("李四");
    quee.Enqueue("王五");
    quee.Enqueue("赵六");
    quee.Enqueue("田七");

    //获取队头
    string name = quee.Peek();
}

查询队列的元素个数

1
2
3
4
/// <summary>
/// 数量
/// </summary>
public int Count => count;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
private void button4_Click(object sender, EventArgs e)
{
    MyQueue<string> quee = new MyQueue<string>();

    //入队
    quee.Enqueue("张三");
    quee.Enqueue("李四");
    quee.Enqueue("王五");
    quee.Enqueue("赵六");
    quee.Enqueue("田七");

    //元素 个数
    int count = quee.Count;
}

完整代码

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CH06Demo
{
    /// <summary>
    /// 顺序队列
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class MyQueue<T>
    {
        /// <summary>
        /// 数据容器
        /// </summary>
        private T[] items;

        /// <summary>
        /// 元素数量
        /// </summary>
        private int count;

        /// <summary>
        /// 队头索引
        /// </summary>
        private int head;

        /// <summary>
        /// 队尾索引
        /// </summary>
        private int tail;

        /// <summary>
        /// 初始化
        /// </summary>
        /// <param name="capacity"></param>
        public MyQueue(int capacity)
        {
            items = new T[capacity];

            count = 0;
            head = 0;
            tail = 0;
        }

        /// <summary>
        /// 初始化
        /// </summary>
        public MyQueue() : this(10) { } 

        /// <summary>
        /// 数量
        /// </summary>
        public int Count => count;

        /// <summary>
        /// 是否空队
        /// </summary>
        public bool IsEmpty => count == 0;

        /// <summary>
        /// 是否满队
        /// </summary>
        public bool IsFull => count == items.Length;

        /// <summary>
        /// 入队
        /// </summary>
        /// <param name="item"></param>
        /// <exception cref="InvalidOperationException"></exception>
        public void Enqueue(T item)
        {
            if (IsFull)
            {
                throw new InvalidOperationException("队列已满");
            }

            //将元素放入队尾
            items[tail++] = item;

            //更新数量
            count++;
        }

        /// <summary>
        /// 出队
        /// </summary>
        /// <returns></returns>
        /// <exception cref="InvalidOperationException"></exception>
        public T Dequeue()
        {
            if (IsEmpty)
            {
                throw new InvalidOperationException("队列为空.");
            }
            //队头元素
            T result = items[head];
            items[head] = default(T);

            //更新队头索引
            head++;

            //更新元素数量
            count--;

            //返回结果
            return result;
        }

        /// <summary>
        /// 获取队头
        /// </summary>
        /// <returns></returns>
        /// <exception cref="InvalidOperationException"></exception>
        public T Peek()
        {
            if (IsEmpty)
            {
                throw new InvalidOperationException("队列为空.");
            }

            return items[head];
        }
    }
}

顺序队列溢出

在容量为6的顺序队列中将J1-J6依次入队，然后J1、J2出队。此时，J7能否成功入队？

  • head=0,tail=maxSize，元素入队发生溢出(真溢出)
  • head!=0,tail=maxSize，元素入队发生溢出(假溢出)
  • 采用循环队列解决“假溢出”问题

循环队列

  • 将为队列分配的空间看成是一个首尾相接的圆环
  • 循环队列中队空和队满时，头尾指针均相等

入队

实现思路：

  • 判断队列状态，如果队列已满，返回false, 不允许入队
  • 若队列不满，将新元素obj 插入tail所指的位置，作为新的队尾元素
  • tail=(tail+1)%maxSize
  • 操作成功返回true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/// <summary>
/// 入队
/// </summary>
/// <param name="item"></param>
/// <exception cref="InvalidOperationException"></exception>
public void Enqueue(T item)
{
    if (IsFull)
    {
        throw new InvalidOperationException("队列已满");
    }

    //将元素放入队尾
    items[tail] = item;

    //计算队尾索引
    tail = (tail + 1) % items.Length;

    //更新数量
    count++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private void button5_Click(object sender, EventArgs e)
{
    MyQueue2<string> quee = new MyQueue2<string>(5);

    //入队
    quee.Enqueue("张三");
    quee.Enqueue("李四");
    quee.Enqueue("王五");
    quee.Enqueue("赵六");
    quee.Enqueue("田七");

    //出队
    quee.Dequeue();
    quee.Dequeue();

    //入队
    quee.Enqueue("孙悟空"); //tail：0
    quee.Enqueue("猪八戒"); //tail：1
}

出队

实现思路：

  • 判断队列状态，如果队列已空，不允许出队
  • 若队列不空，取走front位置上的队头元素
  • head= (head+ 1) % maxSize
  • 返回出队数据
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/// <summary>
/// 出队
/// </summary>
/// <returns></returns>
/// <exception cref="InvalidOperationException"></exception>
public T Dequeue()
{
    if (IsEmpty)
    {
        throw new InvalidOperationException("队列为空.");
    }
    //队头元素
    T result = items[head];
    items[head] = default(T);

    //更新队头索引
    head = (head + 1) % items.Length;

    //更新元素数量
    count--;

    //返回结果
    return result;
}

完整代码

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CH06Demo
{
    /// <summary>
    /// 循环队列
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class MyQueue2<T>
    {
        /// <summary>
        /// 数据容器
        /// </summary>
        private T[] items;

        /// <summary>
        /// 元素数量
        /// </summary>
        private int count;

        /// <summary>
        /// 队头索引
        /// </summary>
        private int head;

        /// <summary>
        /// 队尾索引
        /// </summary>
        private int tail;

        /// <summary>
        /// 初始化
        /// </summary>
        /// <param name="capacity"></param>
        public MyQueue2(int capacity)
        {
            items = new T[capacity];

            count = 0;
            head = 0;
            tail = 0;
        }

        /// <summary>
        /// 初始化
        /// </summary>
        public MyQueue2() : this(10) { } 

        /// <summary>
        /// 数量
        /// </summary>
        public int Count => count;

        /// <summary>
        /// 是否空队
        /// </summary>
        public bool IsEmpty => count == 0;

        /// <summary>
        /// 是否满队
        /// </summary>
        public bool IsFull => count == items.Length;

        /// <summary>
        /// 入队
        /// </summary>
        /// <param name="item"></param>
        /// <exception cref="InvalidOperationException"></exception>
        public void Enqueue(T item)
        {
            if (IsFull)
            {
                throw new InvalidOperationException("队列已满");
            }

            //将元素放入队尾
            items[tail] = item;

            //计算队尾索引
            tail = (tail + 1) % items.Length;

            //更新数量
            count++;
        }

        /// <summary>
        /// 出队
        /// </summary>
        /// <returns></returns>
        /// <exception cref="InvalidOperationException"></exception>
        public T Dequeue()
        {
            if (IsEmpty)
            {
                throw new InvalidOperationException("队列为空.");
            }
            //队头元素
            T result = items[head];
            items[head] = default(T);

            //更新队头索引
            head = (head + 1) % items.Length;

            //更新元素数量
            count--;

            //返回结果
            return result;
        }

        /// <summary>
        /// 获取队头
        /// </summary>
        /// <returns></returns>
        /// <exception cref="InvalidOperationException"></exception>
        public T Peek()
        {
            if (IsEmpty)
            {
                throw new InvalidOperationException("队列为空.");
            }

            return items[head];
        }
    }
}

本章总结

  • 简述术语：队列、顺序队列、循环队列
  • 如何判断循环队列是否队满？
  • 简述栈和队列的区别

课后作业

略