数据结构与算法详解——队列篇（附c++实现代码）

• • 队列的概念
  • 队列的实现
  • • 顺序队列与链式队列
    • 循环队列
  • 循环队列的代码实现

  队列的概念比较好理解，和我们现实中的排队比较相似，先进先出。栈和队列有点相似，栈有入栈出栈两种基本操作，队列相对应也有入队出队两种基本操作，不过栈只能从栈顶入，从栈顶出；而队列从队尾入，从队头出，所以队列也是一种操作受限的线性表。

  和栈一样，用数组实现的队列叫顺序队列，用链表实现的队列叫链式队列。
  前面说了，队列从队尾入，从队头出，因此我们需要维护队头head和队尾tail，顺序队列的入队和出队的代码大致是：

template
void enqueue(T data){
	if(tail==capacity)	//队列已经满了，无法再入队
		throw "queue is full";
	array[tail]=data;
	++tail;
}

template
T dequeue(){
	if(head==tail)		//队列已经空了，无法出队
		throw "queue is emptyn";
	T ret=array[head];
	++head;
	return ret;
}

  这样子会有一个问题：head和tail都是不断变大的，随着若干次入队和出队，tail达到了数组的尾端也就是tail==capacity，而head可能在数组的中间位置，这时候队列的元素在[head,tail]上，数组[0,head)的空间却闲置了，但是此时无法入队。
  针对这个问题，我们可以在入队时当tail==capacity时也判断head!=0，都成立的话做一次数据的前移，将[head,tail]上的元素移到[0,tail-head]上，就可以将空间腾出来，这里就不展示完整代码了。
  链式队列的话就不需要考虑移数据或者动态扩容的问题，同样也是维护head和tail指针，入队出队的伪代码：

template
void enqueue(T data){
	if(tail == nullptr)
		tail = new Node(data);
	else{
		Node *newNode = new Node(data)
		tail->next = newNode;
		tail = newNode;
	}		
}

template
T dequeue(){
	if(head==nullptr)
		throw "queue is emptyn";
	T ret=head->data;
	Node *oldNode=head;
	head=oldNode->next;
	delete oldNode;
	return ret;
}

  解决上面顺序队列说到的数据移动的另一种解决方案就是循环队列。循环队列可以将直线的数组空间想象成环形的，tail==capacity后会跳到0开始循环，这里就用到了取余操作%。
  这里需要注意的是队满和队空的条件判定：

1. 队满：(tail+1)%capacity==head
2. 队空：tail==head

  这样判定队满的条件会浪费数组空间的一个位置。

#ifndef CIRCULARQUEUE_H
#define CIRCULARQUEUE_H

#include 

template 
class circularQueue {
private:
	T* array = nullptr;
	size_t _head = 0;
	size_t _tail = 0;
	size_t _capacity = 32;
public:
	circularQueue();
	circularQueue(size_t capacity);
	circularQueue(const circularQueue& cq);
	~circularQueue();
	circularQueue& operator=(const circularQueue& cq);
	void enqueue(T data);
	T dequeue();
	T head();
};

template 
circularQueue::circularQueue() {
	array = new T[_capacity];
}

template 
circularQueue::circularQueue(size_t capacity) {
	array = new T[capacity];
	_capacity = capacity;
}

template 
circularQueue::circularQueue(const circularQueue& cq) {
	_capacity = cq._capacity;
	array = new T[_capacity];
	for (size_t i = cq._head; i != cq._tail; i++) {
		enqueue(cq.array[i]);
	}
	_head = cq._head;
	_tail = cq._tail;
}

template 
circularQueue::~circularQueue() {
	if (array != nullptr) {
		delete[] array;
		array = nullptr;
	}
}

template 
circularQueue& circularQueue::operator=(const circularQueue& cq) {
	delete[] array;
	_capacity = cq._capacity;
	array = new T[_capacity];
	for (size_t i = cq._head; i != cq._tail; i++) {
		enqueue(cq.array[i]);
	}
	_head = cq._head;
	_tail = cq._tail;
	return *this;
}

template 
void circularQueue::enqueue(T data) {
	if ((_tail + 1) % _capacity == _head) {
		std::cout << "circular queue is fulln";
		return;
	}
	array[_tail] = data;
	_tail = (_tail + 1) % _capacity;
}

template 
T circularQueue::dequeue() {
	if ( _tail  == _head) 
		throw "circular queue is emptyn";

	T item = array[_head];
	_head = (_head + 1) % _capacity;
	return item;
}

template 
T circularQueue::head() {
	if (_tail == _head) 
		throw "circular queue is emptyn";
	
	return array[_head];
}

#endif