博客

1.介绍

双端队列，就是

两头都可操作

即出队和进队的一种数据结构。

个人理解，就是两个队列的操作作用于一个队列的结构。

假如，把一端的操作给去掉，则双端队列的结构将退化成栈。因此，栈所能做的操作双端队列也是可以的。

2.操作

其实大部分的操作其实和循环队列没什么不同，至少判空和判满函数是相同的。只是对于循环队列

多了两个函数出队和入队

。

只着重介绍和循环队列不同的地方。

对于循环队列，我们用head指向队首元素，tail指向队尾元素后一个位置。那么，对于双端队列的一端我们可以使用上面的指针。

另一端，其实就不需要再另外声明两个变量了，其实

(tail-1)%maxSize

和（

head-1）%maxSize

就分别是另一端的首尾指针了。

双端队列对于用链表实现可能更好一点，因为它不需要考虑队满的情况，也不需要考虑循环一些的问题。下面是顺序结构的总的代码。

#pragma once
template<typename T>
class DeQueue
{
	T* data;
	int head;
	int tail;
	int maxSize;
	void resize();
public:
	DeQueue();
	~DeQueue();
	bool isFull();
	bool isEmpty();
	void push1(const T& val);
	void push2(const T& val);
	bool pop1();
	bool pop2();
	const T& getFront1();
	const T& getFront2();
};
template<typename T>
void DeQueue<T>::resize()
{
	T* p = data;
	data = new T[maxSize * 2];
	//无论是tail>head还是tail<head都把他复制到新的内存，新的内存从0开始
	for (int i = head; ((i + maxSize) % maxSize) < tail; i++)
		data[i - head] = p[i];
	head = 0;
	tail = maxSize - 1;
	maxSize *= 2;
	delete[]p;
}
template<typename T>
DeQueue<T>::DeQueue()
{
	data = new T[10];
	head = tail = 0;
	maxSize = 10;
}
template<typename T>
DeQueue<T>::~DeQueue()
{
	delete[]data;
}
template<typename T>
bool DeQueue<T>::isFull()
{
	if ((tail + 1) % maxSize == head)
		return true;
	return false;
}
template<typename T>
bool DeQueue<T>::isEmpty()
{
	if (head == tail)
		return true;
	return false;
}
template<typename T>
void DeQueue<T>::push1(const T& val)
{
	if (isFull())
		resize();
	data[tail] = val;
	tail = (tail + 1) % maxSize;
}
template<typename T>
void DeQueue<T>::push2(const T& val)
{
	if (isFull())
		resize();
	head = (head - 1) % maxSize;
	data[head] = val;
}
template<typename T>
bool DeQueue<T>::pop1()
{
	if (isEmpty())
		return false;
	head = (head + 1) % maxSize;
	return true;
}
template<typename T>
bool DeQueue<T>::pop2()
{
	if (isEmpty())
		return false;
	tail = (tail - 1) % maxSize;
	return true;
}
template<typename T>
const T& DeQueue<T>::getFront1()
{
	if (isEmpty())
		throw("error");
	return data[head];
}
template<typename T>
const T& DeQueue<T>::getFront2()
{
	if (isEmpty())
		throw("error");
	return data[((tail-1)%maxSize)];
}