数据结构——队列

1 队列是一种只允许在表的一端插入元素，在另一端删除元素的特殊的线性表。允许插入的一端成为队尾（rear），允许删除的一端成为队头（front）。当队列中没有任何元素时成为空队列。队列是一种先进先出的线性表，简称FIFO表。

2 与栈类似，队列也是一种操作受限的特殊的线性表，同样可以采用顺序存储结构和链式存储结构来表示队列。

3 队列的顺序存储表示——循环队列

队列的顺序存储表示同样是利用一维数组来实现。为了解决“假溢出”问题，可以将队列的数组看成是头尾相接的环状空间，当队尾元素放到数组的最后一个位置时，如需入队就把新元素接着存放在数组的0下表位置，这样的队列成为循环队列。循环队列的基本操作的实现如下：

#ifndef _SQQUEUE_
#define _SQQUEUE_
template<class T>
class SqQueue
{
public:
	SqQueue(int m = 100);
	~SqQueue();
	void Clear();
	bool Empty() const;
	int Length() const;
	T& GetHead() const;
	T& GetLast() const;
	void Append(const T&);
	void Remove();
private:
	T* m_base;
	int m_front;
	int m_rear;
	int m_size;
};

template<class T> SqQueue<T>::SqQueue(int m)
{
	m_front = m_rear = 0;
	m_size = m;
	m_base = new T[m];
}

template<class T> SqQueue<T>::~SqQueue()
{
	delete [] m_base;
}

template<class T> void SqQueue<T>::Clear()
{
	m_front = m_rear = 0;
}

template<class T> bool SqQueue<T>::Empty() const
{
	return m_front == m_rear;
}

template<class T> int SqQueue<T>::Length() const
{
	return (m_rear - m_front + m_size) % m_size;
}

template<class T> T& SqQueue<T>::GetHead() const
{
	if (!Empty())
	{
		return m_base[m_front];
	}
}

template<class T> T& SqQueue<T>::GetLast() const
{
	if (!Empty())
	{
		return m_base[(m_rear - 1 + m_size) % m_size];
	}
}

template<class T> void SqQueue<T>::Append(const T& e)
{
	int i,j;
	if (m_front == (m_rear + 1) % m_size)
	{
		T* newbase = new T[m_size + 10];
		for (i = m_front,j = 0; i < m_rear; i = (i + 1) % m_size, j++)
		{
			newbase[j] = m_base[i];
		}
		delete [] m_base;
		m_base = newbase;
		m_front = 0;
		m_rear = j;
		m_size += 10;
	}
	m_base[m_rear] = e;
	m_rear = (m_rear + 1) % m_size;
}

template<class T> void SqQueue<T>::Remove()
{
	if (!Empty())
	{
		m_front = (m_front + 1) % m_size;
	}
}
#endif

在循环队列中，上述基本操作的时间复杂度均为O(1)。

4 队列的链式存储表示——链队列

#ifndef _LINKQUEUE_
#define _LINKQUEUE_
template<class T>
class LinkQueue
{
public:
	LinkQueue();
	~LinkQueue();
	void Clear();
	bool Empty() const;
	int Length() const;
	T* GetHead() const;
	T* GetLast() const;
	void Append(const T&);
	void Remove();
private:
	LinkNode<T>* m_front;
	LinkNode<T>* m_rear;
};

template<class T> LinkQueue<T>::LinkQueue()
{
	m_front = m_rear = new LinkNode<T>;
	m_front->next = NULL;
}

template<class T> LinkQueue<T>::~LinkQueue()
{
	Clear();
	delete m_front;
}

template<class T> void LinkQueue<T>::Clear()
{
	LinkNode<T>* p;
	while (m_front->next != NULL)
	{
		p = m_front->next;
		m_front->next = p->next;
		delete p;
	}
	m_rear = m_front;
}

template<class T> bool LinkQueue<T>::Empty() const
{
	return m_front == m_rear;
}

template<class T> int LinkQueue<T>::Length() const
{
	int i = 0;
	LinkNode<T>* p = m_front;
	while (p->next != NULL)
	{
		i++;
		p = p->next;
	}
	return i;
}

template<class T> T& LinkQueue<T>::GetHead() const
{
	while(!Empty())
	{
		return m_front->next->data;
	}
}

template<class T> T& LinkQueue<T>::GetLast() const
{
	while(!Empty())
	{
		return m_rear->data;
	}
}

template<class T> void LinkQueue<T>::Append(const T& e)
{
	LinkNode<T>* p = new LinkNode<T>;
	p->data = e;
	p->next = NULL;
	m_rear->next = p;
	m_rear = p;
}

template<class T> void LinkQueue<T>::Remove()
{
	LinkNode<T>* p;
	if (!Empty())
	{
		p = m_front->next;
		m_front->next = p->next;
		if (p == m_rear)
		{
			m_rear = m_front;
		}
		delete p;
	}
}
#endif

链队列的队空条件为front = rear,或者front->next = NULL，而队满只在内不能无可用空间时才发生，所以链队列特别适合于队列元素个数变化比较大的情况。

在链队列的操作中，队列的销毁、清空和求长度操作的时间复杂度为O(n)，因为需要对链表的每个结点进行处理。队列的其余操作的时间复杂度为O(1)。

5 队列的应用

5.1 舞伴问题

假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。

#include <iostream>
#include <fstream>
#include "SqQueue.h"
using namespace std;

struct Dancer
{
	char name[20];
	char sex;
};

void main(int argc, char* argv[])
{
	ifstream input("input.txt");
	SqQueue<Dancer> M(50), F(50);
	Dancer d;
	input>>d.name>>d.sex;
	while (d.sex != '#')
	{
		if (d.sex == 'M' || d.sex == 'm')
		{
			M.Append(d);
		}
		else if (d.sex == 'F' || d.sex == 'f')
		{
			F.Append(d);
		}
		input>>d.name>>d.sex;
	}

	while (!M.Empty() && !F.Empty())
	{
		Dancer d = M.GetHead();
		M.Remove();
		cout<<d.name<<" ";
		Dancer d2 = F.GetHead();
		F.Remove();
		cout<<d2.name<<endl;
	}

	if (!M.Empty())
	{
		cout<<"依然还有"<<M.Length()<<"男舞者在等待"<<endl;
		cout<<M.GetHead().name<<"最先获得舞伴"<<endl;
	}
	else if (!F.Empty())
	{
		cout<<"依然还有"<<F.Length()<<"女舞者在等待"<<endl;
		cout<<F.GetHead().name<<"最先获得舞伴"<<endl;
	}
	else
	{
		cout<<"没有等待的舞者！"<<endl;
	}
	system("pause");
}

5.2 火车车厢重排问题
一列货运列车共有 n 节车厢，每节车厢将停放在不同的车站。假定 n 个车站的编号分别为 1 ~ n ，即货运列车按照第 n 站至第 1 站的次序经过这些车站。为了便于从列车上卸掉相应的车厢，车厢的编号应与车站的编号相同，这样，在每个车站只需卸掉最后一节车厢。所以，给定任意次序的车厢，必须重新排列他们。
车厢的重排工作可以通过转轨站完成。在转轨站中有一个入轨、一个出轨和 k 个缓冲轨，缓冲轨位于入轨和出轨之间。假定 缓冲轨按先进先出的方式运作，设计算法解决火车车厢重排问题。
TrackStation.h

#include "SqQueue.h"
#pragma once
class CTrackStation
{
public:
	CTrackStation(int trackCount);
	~CTrackStation(void);
	bool Realign(int* A, int n);
private:
	bool HoldIn(int car);
	bool HoldOut(int car);

	SqQueue<int>* m_pTracks;
	int m_trackCount;
};

TrackStation.cpp<pre name="code" class="cpp">#include "TrackStation.h"
#include <iostream>

CTrackStation::CTrackStation(int trackCount):m_trackCount(trackCount)
{
	m_pTracks = new SqQueue<int>[m_trackCount];
}


CTrackStation::~CTrackStation(void)
{
	delete [] m_pTracks;
}

bool CTrackStation::HoldIn(int car)
{
	int bestTrack = -1;
	int bestLast = -1;
	int i;
	for (i = 0; i < m_trackCount; i++)
	{
		if (!m_pTracks[i].Empty())
		{
			int last = m_pTracks[i].GetLast();
			if (car > last && last > bestLast)
			{
				bestTrack = i;
				bestLast = last;
			}
		}
	}

	if (bestTrack == -1)
	{
		for (i = 0; i < m_trackCount; i++)
		{
			if (m_pTracks[i].Empty())
			{
				bestTrack = i;
				break;
			}
		}
	}

	if (bestTrack == -1)
	{
		return false;
	}
	m_pTracks[bestTrack].Append(car);
	std::cout<<car<<"号车厢进入"<<bestTrack<<"号缓冲轨"<<std::endl;
	return true;
}

bool CTrackStation::HoldOut(int car)
{
	for (int i = 0; i < m_trackCount; i++)
	{
		if (!m_pTracks[i].Empty())
		{
			int headCar = m_pTracks[i].GetHead();
			if (headCar == car)
			{
				headCar =m_pTracks[i].GetHead();
				m_pTracks[i].Remove();
				std::cout<<headCar<<"号车厢从"<<i<<"号缓冲轨出站"<<std::endl;
				return true;
			}
		}
	}
	return false;
}

bool CTrackStation::Realign(int* A, int n)
{
	int nowOut = 1, i = 0;
	while (nowOut <= n)
	{
		if (HoldOut(nowOut))
		{
			nowOut++;
			continue;
		}
		if (i >= n || !HoldIn(A[i]))
		{
			return false;
		}
		i++;
	}
	return true;
}

Main.cpp<pre name="code" class="cpp">#include <iostream>
#include <fstream>
#include "TrackStation.h"
using namespace std;

void main(int argc, char* argv[])
{
	int k;
	cout<<"请输入缓冲轨数目：";
	ifstream input("input.txt");
	input>>k;
	CTrackStation trackStation(k);
	cout<<"请依次输入入轨的车厢次序，以0结束：";
	int car, n = 0, A[100];
	input>>car;
	while(car > 0 && n < 100)
	{
		A[n++] = car;
		input>>car;
	}
	if (!trackStation.Realign(A,n))
	{
		cout<<"车厢无法重排!"<<endl;
	}
	system("pause");
}

转载：http://blog.csdn.net/foreverling/article/details/43153389