C++实现双端队列(数组模拟)【每一步详细深入讲解，代码清晰、简单、易懂】_c++双端队列

一、数组实现双端队列

0、一些共识

1）左右指针的位置

例如上图这样一个双端队列，刚开始队列为空的时候，左右指针指向同一个位置；

这时候，如果从左边入队1，右边入队2

发现，左边入队是正常，但，右边入队时入队的值覆盖了之前的值！那该怎么改？

解决思路：

发现，左右入队是都是填充值，后移动指针，而开始的时候左右指针指向同一处，写值会覆盖。

因此，有如下两种解决方法：

1、改进入队方法：左边依旧先写值，后移动，右边则先移动，后写值，结果如下

但是，这样怎么看怎么别扭，左边和右边都执行了入队，但左指针位置无元素，右指针位置却有，而且左右入队操作不同，不太符合通用原则。

2、改进指针位置：既然上述问题是由于左右指针指向同一个位置造成的，那么就可以让指针错位，初始时右指针在左指针右边一格

2）队空，队满的条件

经过上述讨论，可以看出，left + 1 == right时，队列是空的，那么，这是不是就是判断队列为空的条件呢？

在此之前，我们先来看看左指针和右指针在队列未满但到达边界时如何处理

问题和期望的结果：如左图，左指针已经到了左边界，但队列还没满按理说应该可以左入队，再次入队之后左指针应该到达最右边，这样才能实现继续入队，现在只要实现左指针到达左边界时再入队，指针移动到最右边的操作。

**数学依据：**模运算！！！经过思考，发现一个小于B的数A模B依然等于A，而如果A等于B，那A模B就等于0，-1+B模B等于B-1，而A加上任意个B 再模B依然等于A

**结论：**利用这个性质，左指针的移动可以改成(left - 1 + size) % size，当左指针没有达到左边界时，该操作只是向左移动一格，而到达左边界时就移动到最右边！

这时，右指针达到右边界依然可以利用模运算，公式为(right + 1) % size。
出队时左右指针的逻辑正好和入队相反

队空的条件:

队空有如下两种情况：

经过上面讨论，我们可以轻松得出这两种情况的表达式，而第一种情况也可以用第二个表达式表示，因此我们得到了队空的通用表示(left + 1) % size == right

队满的条件：

假设从右边一直入队直到队满

如果数组中填满元素，那么，右指针正好在左指针右边，这和队空的条件一样，会产生冲突！
解决方法很简单，只要空出一个格子，让队满的条件改为左右指针相等left == right

1、双端队列的定义

双端队列需要一个数组以及表示两端的指针，还有表示队列大小的变量；
需要左右入队、左右出队操作，而入队出队又需要判断队空和队满;
同时，构造和析构也不能少

class Deque {
private:
    int* deq;  // 数组
    std::size_t left;  // 左指针
    std::size_t right; // 右指针
    std::size_t size;
private:
    inline bool empty();
    inline bool full();
public:
    void lpush(int);
    void rpush(int);
    int lpop();
    int rpop();
    Deque(std::size_t);
    ~Deque();
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2、入队操作

• 判断队满与否
  • 满则输出错误信息
  • 未满则入队

// 左入队
void Deque::lpush(int val) {
	if (full()) {
		std::cerr << "Deque is full, lpush failed!" << std::endl;
	} else {
		deq[left] = val;
		left = (left - 1 + size) % size;
	}
}

// 右入队
void Deque::rpush(int val) {
	if (full()) {
		std::cerr << "Deque is full, rpush failed!" << std::endl;
	} else {
		deq[right] = val;
		right = (right + 1) % size;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

3、出队操作

• 判断队空与否
  • 空则输出错误信息
  • 不空则出队

// 左出队
int Deque::lpop() {
	if (empty()) {
		std::cerr << "Deque is empty, lpop failed!" << " ";
		return INT_MAX;
	} else {
		left = (left + 1) % size; // 只需移动指针，不需要改动值
		return deq[left];
	}
}

// 右出队
int Deque::rpop() {
	if (empty()) {
		std::cerr << "Deque is empty, rpop failed!" << " ";
		return INT_MAX;
	} else {
		right = (right - 1 + size) % size; // 只需移动指针，不需要改动值
		return deq[right];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

4、队空、队满操作

// 因为队空队满操作十分简单，因此，我让他们内联
// 队空
inline bool Deque::empty() {
    return (left + 1) % size == right;
}

// 队满
inline bool Deque::full() {
    return left == right;
}
1
2
3
4
5
6
7
8
9
10

5、完整代码

// Deque.h双端队列定义
#include <cstddef>

class Deque {
private:
	int* deq;  // 数组
	std::size_t left;  // 左指针
	std::size_t right; // 右指针
	std::size_t size;
private:
	inline bool empty();
	inline bool full();
public:
	void lpush(int);
	void rpush(int);
	int lpop();
	int rpop();
	inline Deque(std::size_t);
	inline ~Deque();
};

// 给数组开辟sz+1是为了给判断队满空出一格
Deque::Deque(std::size_t sz) 
	: deq(new int[sz + 1]()), left(0), right(1), size(sz+1) { }

Deque::~Deque() {
	delete[] deq;
}

// 因为队空队满操作十分简单，因此，我让他们内联
// 队空
inline bool Deque::empty() {
	return ((left + 1) % size == right);
}

// 队满
inline bool Deque::full() {
	return left == right;
}
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

// Deque.cpp双端队列函数实现
#include <iostream>
#include <cstddef>

#include "Deque.h"

// 左入队
void Deque::lpush(int val) {
	if (full()) {
		std::cerr << "Deque is full, lpush failed!" << std::endl;
	} else {
		deq[left] = val;
		left = (left - 1 + size) % size;
	}
}

// 右入队
void Deque::rpush(int val) {
	if (full()) {
		std::cerr << "Deque is full, rpush failed!" << std::endl;
	} else {
		deq[right] = val;
		right = (right + 1) % size;
	}
}

// 左出队
int Deque::lpop() {
	if (empty()) {
		std::cerr << "Deque is empty, lpop failed!" << " ";
		return INT_MAX;
	} else {
		left = (left + 1) % size; // 只需移动指针，不需要改动值
		return deq[left];
	}
}

// 右出队
int Deque::rpop() {
	if (empty()) {
		std::cerr << "Deque is empty, rpop failed!" << " ";
		return INT_MAX;
	} else {
		right = (right - 1 + size) % size; // 只需移动指针，不需要改动值
		return deq[right];
	}
}
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

// Deque_test.cpp双端队列测试文件
#include <iostream>

#include "Deque.h"

int main(int) {
	Deque que(5); // 定义大小为5的双端队列
	
	// 模拟栈的先入后出
	for (auto i = 0; i < 5; ++i)
		que.rpush(i);
	//测试队满入队
	que.lpush(0);
	for (auto i = 0; i < 5; ++i)
		std::cout << que.rpop() << " ";
	std::cout << std::endl;
	
	// 模拟队列的先入先出
	for (auto i = 0; i < 5; ++i)
		que.rpush(i);
	for (auto i = 0; i < 5; ++i)
		std::cout << que.lpop() << " ";
	std::cout << std::endl;
	
	/*
	* 期望输出：
	* Deque is full, lpush failed!
	* 4 3 2 1 0
	* 0 1 2 3 4
	*/

	return 0;
}
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