循环队列与链队列

队列 (Queue)

是一种操作受限的线性表。它只允许在线性表的一端进行插入操作，在另一端进行删除操作。允许插入的一端称作队尾 (rear)，允许删除的一端称作队头 (front)，在队尾进行插入的操作称为入队，在对头进行删除的操作称作出队。不包含任何数据的队列称为空队。

队列基本运算如下（循环队列）：

const int QueueSize = 1000; // 循环队列最大长度
template<class T>
class CircleQueue {
	public:
		CircleQueue() { front = rear = 0;} // 构造函数
		void EnQueue(T x); // 入队
		T DeQueue(); // 出队
		T GetFront(); // 获取队头数据
		T GetRear(); // 获取队尾数据
		int GetLength(); // 队列长度
		bool Empty() { return front == rear; } // 判断是否为空队列
	private:
		int front,rear;
		T data[QueueSize];
};

循环队列

类似于顺序表，队列也可以采用顺序储存结构进行储存。即使用数组储存元素。由于队列操作是在队列两段进行的，因此一般需要设置队头和队尾两个指针。对于空队列，队头和队尾均为 -1。随着元素的入队，队尾不断后移，出队时，队头指针也后移。为了方便操作，队列需要腾出一个元素不使用，这里队列的第一个元素为 front 指针所指的下一个。在这里我们规定队头指针所指的位置永远不储存队列元素。

下面是循环队列：

/*************************************************************************
    > File Name: CircleQueue.cpp
    > Author: Netcan
    > Mail: 1469709759@qq.com
    > Created Time: Sat 25 Apr 2015 21:08:27 CST
 ************************************************************************/

#include<iostream>
using namespace std;

const int QueueSize = 1000; // 循环队列最大长度 
template<class T>
class CircleQueue {
	public:
		CircleQueue() { front = rear = 0;} // 构造函数 
		void EnQueue(T x); // 入队 
		T DeQueue(); // 出队 
		T GetFront(); // 获取队头数据 
		T GetRear(); // 获取队尾数据 
		int GetLength(); // 队列长度 
		bool Empty() { return front == rear; } // 判断是否为空队列 
	private:
		int front,rear;
		T data[QueueSize];
};

template<class T>
void CircleQueue<T>::EnQueue(T x) {
	if((rear+1)%QueueSize == front) throw "上溢！";
	rear = (rear + 1) % QueueSize;
	data[rear] = x;
	return;
}

template<class T>
T CircleQueue<T>::DeQueue() {
	if(Empty()) throw "空队列！";
	front = (front + 1) % QueueSize;
	return data[front];
}

template<class T>
T CircleQueue<T>::GetFront() {
	if(Empty()) throw "空队列！";
	return data[(front+1)%QueueSize];
}

template<class T>
T CircleQueue<T>::GetRear() {
	if(Empty()) throw "空队列！";
	return data[rear];
}

template<class T>
int CircleQueue<T>::GetLength() {
	return (rear - front + QueueSize) % QueueSize;
}

int main() {
	CircleQueue<int> queue;
	cout << "长度:" << queue.GetLength() << endl;
	for(int i=1; i<=10; ++i) {
		queue.EnQueue(i);
		cout << "队首元素:" << queue.GetFront() << "队尾元素:" << queue.GetRear() << "长度:" << queue.GetLength() << endl;
	}
	cout << "-----------------------------" << endl;
	for(int i=1; i<=10; ++i)  {
		cout << "队首元素:" << queue.GetFront() << "队尾元素:" << queue.GetRear() << "长度:" << queue.GetLength() << endl;
		queue.DeQueue();
	}
	cout << "长度:" << queue.GetLength() << endl;
	return 0;
}

链队列

队列的链式储存称为链队列，因此链队列可看成仅在表头删除和表尾插入的单链表。在这里我们规定队头指针所指的位置永远不储存队列元素。

下面是链队列：

/*************************************************************************
    > File Name: LinkQueue.cpp
    > Author: Netcan
    > Mail: 1469709759@qq.com
    > Created Time: Sat 25 Apr 2015 21:08:27 CST
 ************************************************************************/

#include<iostream>
using namespace std;

template<class T>
struct Node {
	T data;
	Node *next;
};

template<class T>
class LinkQueue {
	public:
		LinkQueue() {
			front = rear = new Node<T>;
			rear->next = NULL;
		}
		~LinkQueue();
		void EnQueue(T x);
		T DeQueue();
		T GetFront();
		T GetRear();
		int GetLength();
		bool Empty() { return front == rear; }
	private:
		Node<T> * front;
		Node<T> * rear;
};

template<class T>
void LinkQueue<T>::EnQueue(T x) {
	rear->next = new Node<T>;
	rear = rear->next;
	rear->data = x;
	rear->next = NULL;
	return;
}

template<class T>
T LinkQueue<T>::DeQueue() {
	if(Empty()) throw "空队列！";
	Node<T> *p = front->next;
	T x = p->data;
	front->next = p->next;
	delete p;
	if(!front->next) rear = front;
	return x;
}

template<class T>
T LinkQueue<T>::GetFront() {
	if(Empty()) throw "空队列！";
	return front->next->data;
}

template<class T>
T LinkQueue<T>::GetRear() {
	if(Empty()) throw "空队列！";
	return rear->data;
}

template<class T>
int LinkQueue<T>::GetLength() {
	Node<T> *p = front->next;
	int len = 0;
	while(p) {
		p = p->next;
		++len;
	}
	return len;
}
template<class T>
LinkQueue<T>::~LinkQueue() {
	while(front) {
		rear = front->next;
		delete front;
		front = rear;
	}
}



int main() {
	LinkQueue<int> queue;
		cout << "长度:" << queue.GetLength() << endl;
	for(int i=1; i<=10; ++i) {
		queue.EnQueue(i);
		cout << "队首元素:" << queue.GetFront() << "队尾元素:" << queue.GetRear() << "长度:" << queue.GetLength() << endl;
	}
	cout << "-----------------------------" << endl;
	for(int i=1; i<=10; ++i)  {
		cout << "队首元素:" << queue.GetFront() << "队尾元素:" << queue.GetRear() << "长度:" << queue.GetLength() << endl;
		queue.DeQueue();
	}
	cout << "长度:" << queue.GetLength() << endl;
	return 0;
}

运行结果如下：

 长度: 0
队首元素: 1 队尾元素: 1 长度: 1
队首元素: 1 队尾元素: 2 长度: 2
队首元素: 1 队尾元素: 3 长度: 3
队首元素: 1 队尾元素: 4 长度: 4
队首元素: 1 队尾元素: 5 长度: 5
队首元素: 1 队尾元素: 6 长度: 6
队首元素: 1 队尾元素: 7 长度: 7
队首元素: 1 队尾元素: 8 长度: 8
队首元素: 1 队尾元素: 9 长度: 9
队首元素: 1 队尾元素: 10 长度: 10
-----------------------------
队首元素: 1 队尾元素: 10 长度: 10
队首元素: 2 队尾元素: 10 长度: 9
队首元素: 3 队尾元素: 10 长度: 8
队首元素: 4 队尾元素: 10 长度: 7
队首元素: 5 队尾元素: 10 长度: 6
队首元素: 6 队尾元素: 10 长度: 5
队首元素: 7 队尾元素: 10 长度: 4
队首元素: 8 队尾元素: 10 长度: 3
队首元素: 9 队尾元素: 10 长度: 2
队首元素: 10 队尾元素: 10 长度: 1
长度: 0