队列

队列是一种线性的数据结构，其特点为先入先出FIFO

注意：在C++的标准模板库(STL)中，queue 是一个容器适配器，它是基于底层容器实现的。默认情况下，queue 是通过 std::deque 来实现的，但也可以通过其他序列容器（如 std::list）来实现

一、队列的顺序实现

1.SqQueue.h

队列可实现自动扩容，当队列中内存不足时候，以原内存的2倍大小进行扩容

队列初始化：

  • 队列初始化大小为capacity = 4
  • 头指针front= 0，尾指针rear = 0，初始首尾指针均可以指向同一个位置
  • 队列为空：rear == front
  • 队列首部出队，首部指针后移：front = (front + 1) % capacity
  • 队列尾部入队，尾部指针后移：rear = (rear + 1) % capacity
  • 获取队列首部元素，返回：data[front]
  • 获取队列尾部部元素，返回：data[(rear - 1 + capacity) % capacity]

image-20240912101851252

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
#pragma once
#include "exception"

template<typename T>
class SqQueue
{
private:
    T *data;
    int front_,rear_, capacity;
public:
    SqQueue(int cap = 4)
    {
        // 实际有效存储元素的位置长度为cap-1
        // rear_指针指向的位置不存放元素
        data = new T[cap];
        if(data == nullptr)
            throw "内存分配失败";

        capacity = cap;
        front_ = rear_ = 0;
    }

    // 入队列
    bool push(T e)
    {
        // 队列满，进行2倍内存的扩容
        if((rear_ + 1) % capacity == front_)
        {
            T *p = new T[2*capacity];
            if(p == nullptr)
                throw "内存分配失败";

            for(int i = 0;i<capacity;i++)
            {
                p[i] = data[i];
            }
            delete data;
            data = p;
            capacity *= 2;
        }
        data[rear_] = e;
        // 尾指针后移
        rear_ = (rear_ + 1) % capacity;
    }

    // 队列首部弹出
    bool pop()
    {
        if(front_ == rear_)
            return false;
        // 首指针后移
        front_ = (front_ + 1) % capacity;
        return true;
    }

    // 获取首部元素
    T &front()
    {
        if(front_ == rear_)
            throw "队列为空";
        return data[front_];
    }

    // 获取尾元素
    T &rear()
    {
        if(rear_ == front_)
            throw "队列为空";

        // 尾指针指向的位置，没有存放元素
        // 对其进行如下操作，获取队列中尾部位置的元素
        int pos = (rear_ - 1 + capacity) % capacity;
        return data[pos];
    }

    // 获取队列长度
    int size()
    {
        return (rear_ - front_ + capacity) % capacity;
    }

    // 判空
    bool empty()
    {
        return front_ == rear_;
    }

    // 清空
    bool clear()
    {
        front_ = rear_ = 0;
    }
};

2.测试

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
#include <iostream>
#include "SqQeueu.h"
using namespace std;

int main() {
    SqQueue<int> Q;
    bool ret = Q.push(3);

    ret = Q.push(4);
    ret = Q.push(5);
    ret = Q.push(6);
    ret = Q.push(7);
    ret = Q.push(8);

    int r = Q.rear();
    cout << "队列尾部: " << r << endl;
    cout << "队列大小: " << Q.size() << endl;

    while(!Q.empty())
    {
        int f = Q.front();
        Q.pop();
        cout << f << " ";
    }
    cout << endl;


    return 0;
}
1
2
3
队列尾部: 8
队列大小: 6
3 4 5 6 7 8

二、队列的链式实现

链式实现，头指针指向实际的元素

尾指针指向队列的最后一个元素节点

1.LkQueue.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
#pragma once
#include "exception"

template <typename T>
class LkQueue{
private:
    struct Node{
        T data;
        Node *next;
    };
    Node *front_;
    Node *rear_;

public:
    LkQueue();
    bool push(T e);
    bool pop();
    T &front();
    bool empty();
};


template <typename T>
LkQueue<T>::LkQueue()
{
    // 初始头尾指针指向同一块内存
    front_ = rear_ = new Node();
    if(front_ == nullptr)
        throw "内存分配失败";
    front_->next = nullptr;
}

// 入队
template <typename T>
bool LkQueue<T>::push(T e)
{
    Node *newNode = new Node;
    if(newNode == nullptr) return false;
    newNode->data = e;
    newNode->next = nullptr;
    // 队列尾部入队
    rear_ -> next = newNode;
    // 尾指针指向新节点
    rear_ = newNode;
    return true;
}

// 出队
template <typename T>
bool LkQueue<T>::pop()
{
    // 队列为空
    if(front_ == rear_)
        return false;
    // 队列首部出队
    Node *p = front_->next;
    front_->next = p->next;
    // 当出队的节点为尾指针指向的节点
    if(rear_ == p)
        rear_ = front_;
    delete p;
    return true;
}

// 获取队列首部节点的元素
// 队列头指针不指向实际的值
template <typename T>
T& LkQueue<T>::front()
{
    if(front_ == rear_)
    {
        throw "空队列";
    }
    return front_->next->data;
}

// 判空
template <typename T>
bool LkQueue<T>::empty()
{
    return front_ == rear_;
}

2.测试

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
#include <iostream>
#include "LkQueue.h"
using namespace std;

int main() {
    LkQueue<int> q;

    q.push(10);
    q.push(3);
    q.push(5);

    cout << q.front() << endl;
    q.pop();
    cout << q.front() << endl;

    q.push(30);
    q.push(50);

    while(!q.empty())
    {
        cout << q.front() <<endl;
        q.pop();
    }


    return 0;
}
1
2
3
4
5
6
10
3
3
5
30
50

三、循环队列的实现

循环队列：使用连续的内存空间存储元素

  • 当超出下标，在回到起始下标

  • 入队：rear = (rear + 1) % MAXSIZE

  • 出队：front= (front+ 1) % MAXSIZE

  • 数据元素的个数：(rear - front + MAXSIZE) % MAXSIZE

    image-20240913093555947

  • 空队列：rear == front

  • 满队列：(rear + 1) % MAXSIZE == front

image-20240913093914107

1.CircleQueue.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
113
114
115
116
117
118
#pragma once
#include "exception"

template <typename T>
class CircleQueue{
private:
    T *data;
    int front;
    int rear;
    int capacity;
public:
    CircleQueue(int cap);
    bool push(T e);
    bool pop();
    T& Front();
    T& Rear();
    int Size();
    bool isEmpty();
    bool isFull();
    void clear();
};

// 连续的内存空间实现循环队列
// 构造函数传入参数cap,实际的连续内存大小应该+1
// 因为rear指针指向的位置不存储实际的值
template <typename T>
CircleQueue<T>::CircleQueue(int cap)
{
    data = new T[cap+1];
    if(data == nullptr)
        throw  "内存分配失败";
    front = rear = 0;
    capacity = cap+1;
}

// 入队
template <typename T>
bool CircleQueue<T>::push(T e)
{
    // 判断队列是否满
    if((rear + 1) % capacity == front)
    {
        return false;
    }

    data[rear] = e;
    // 尾指针后移
    rear = (rear + 1) % capacity;
    return true;
}

// 出队
template <typename T>
bool CircleQueue<T>::pop()
{
    // 判断队列是否为空
    if(front == rear)
        return false;
    // 首指针后移
    front = (front + 1) % capacity;
    return true;
}

// 获取队列首部元素
template <typename T>
T & CircleQueue<T>::Front()
{
    // 判断队列是否为空
    if(front == rear)
        throw "队列为空";

    return data[front];
}

// 获取队列尾部元素
template <typename T>
T & CircleQueue<T>::Rear()
{
    // 判断队列是否为空
    if(front == rear)
        throw "队列为空";

    int pos = (rear - 1 + capacity) % capacity;
    return data[pos];
}

// 获取队列中元素个数
template <typename T>
int CircleQueue<T>::Size()
{
    int size = (rear - front + capacity) % capacity;
    return size;
}

// 判断队列是否空
template <typename T>
bool CircleQueue<T>::isEmpty()
{
    if(front == rear)
        return true;
    return false;
}

// 判断队列是否满
template <typename T>
bool CircleQueue<T>::isFull()
{
    if((rear + 1) % capacity == front)
        return true;
    return false;
}

// 清空
template <typename T>
void CircleQueue<T>::clear()
{
    front = rear = 0;
}

2.测试

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
#include <iostream>
#include "CircleQueue.h"
using namespace std;

int main() {
    CircleQueue<int> circleQueue(4);

    cout << "队列是否为空： " << circleQueue.isEmpty() << endl;

    circleQueue.push(1);
    circleQueue.push(2);
    circleQueue.push(3);
    circleQueue.push(4);

    cout << "队列是否满： " << circleQueue.isFull() << endl;
    cout << "队列中元素数量: " << circleQueue.Size() << endl;

    for(int i = 0;i<4;i++)
    {
        cout << "---------"<<endl;
        cout << "队列首部元素: " << circleQueue.Front() <<endl;
        cout << "队列尾部元素: " << circleQueue.Rear() << endl;
        cout << "队列元素数量: " << circleQueue.Size() << endl;
        circleQueue.pop();
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
队列是否为空： 1
队列是否满： 1
队列中元素数量: 4
---------
队列首部元素: 1
队列尾部元素: 4
队列元素数量: 4
---------
队列首部元素: 2
队列尾部元素: 4
队列元素数量: 3
---------
队列首部元素: 3
队列尾部元素: 4
队列元素数量: 2
---------
队列首部元素: 4
队列尾部元素: 4
队列元素数量: 1

四、扩展应用

1.农夫过河问题

image-20240913101541073

思路：

  • 农夫带羊过河，之后单独回来
  • 农夫带狼过河，之后将羊带回来
  • 农夫带白菜过河，之后单独回来
  • 农夫带羊过河，如此全部东西都在河的对岸了

求解：将农夫，白菜，狼，羊视作四位二进制

  • 如果某个事物过河了，则其状态为1，否则围殴0，则题目变为：
  • image-20240913102407032
  • image-20240913110921005