数据结构之队列

简介

今天讲另一种常用的数据结构——队列。队列存储数据的结构类型和栈相同（如果不了解栈可以去看我另一篇专讲栈的文章），不同的是栈只在栈顶插入（压栈）和删除（出栈）数据，而队列在队首删除（出队）数据，在队尾插入（入队）数据。所以队列的入队和出队的顺序相同（这一点和栈相反），它是一种先进先出FIFO（First In First Out)的数据结构。如下图所示。

由图可知，要想实现队列的各项操作需要两个指针（或游标），队首和队尾指针（或游标）。队列和栈一样也有顺序和链式两种形式。顺序队列用一个定长数组存储数据，链队列用链表存储数据，长度不受限制。下面详细介绍两种队列。

顺序队列：

如图所示是一个容量MAXSIZE=10的顺序队列：

• 顺序队列初始化时为空队列，此时front=rear=0；
• 入队时将游标rear指向的元素赋值，然后将游标rear+1；
• 出队时将游标front+1；

有两个地方需要注意：

1. 当front=rear时，队列为空，但不一定front=rear=0，当front与rear在任何地方相等时队列都为空。
2. 当rear=MAXSIZE-1时入队，此时rear指向的元素赋值，然后rear+1，但此时游标rear已经到达数组最后一个元素，如果rear+1就会发生溢出，然而此时游标front的前面可能会有空位，所以此时的溢出其实是假溢出。如何解决呢？我们这样定义，当rear=MAXSIZE-1时入队，数据正常赋值，然后将rear重新从头部开始，此时不再是rear+1，而是(rear+1)%MAXSIZE，同样出队的操作变为(front+1)%MAXSIZE。从逻辑上我们其实将队列的尾部和头部相接，此时队列变成了一个 循环队列，如下图所示
   
   循环队列下，当front=rear时队列空；当(rear+1)%MAXSIZE=front时队列满。

链队列

链队列采用链式存储，其实就是线性的单链表，每一个节点包括一个存储数据的元素和一个指向后继节点的指针。为了操作方便，我们引入头结点。

初始化时头指针和尾指针都指向头结点。

入队时，新分配一个节点，赋值并将它添加到尾指针rear指向节点的后继节点，然后将尾指针rear指向它。

出队时，先将队头节点（头节点的后继节点）与头节点断开，然后将队队头节点的后继节点与头节点相连，最后删除队头节点。

链节点下，指针front=rear时链队列为空。队容量没有限制。

循环队列代码实现

采用模版，实现多种数据类型处理

#pragma once
#include <cstdlib>
#define MAXSIZE 10  //循环队列容量
using namespace std;

template <typename T>
class queue
{
public:
	queue() :_front(0), _rear(0), _size(0) {};	//默认构造函数
	~queue() {}; //默认析构函数

	T back()const;	 //返回最后一个元素
	bool empty()const;	 //如果队列空则返回真
	T front()const;		//返回第一个元素
	void pop();		//删除第一个元素
	void push(T value);		//在末尾加入一个元素
	int size()const;	//返回队列中元素的个数

private:
	T data[MAXSIZE];	//队列数组
	int _front;	//队头游标
	int _rear;	//队尾游标
	unsigned int _size;	//队列元素数目
	const unsigned int capacity = MAXSIZE;	//队列容量=MAXSIZE-1
};

template<typename T>
inline T queue<T>::back() const
{
	if (_front == _rear)
		return 0;
	return data[(_rear-1+MAXSIZE)%MAXSIZE];
}

template<typename T>
inline bool queue<T>::empty() const
{
	if (_front == _rear)
		return true;
	return false;
	
}

template<typename T>
inline T queue<T>::front() const
{
	if (_front == _rear)
		return 0;
	return data[_front];
}

template<typename T>
inline void queue<T>::pop()
{
	if (_front == _rear)
		return;
	_front = (_front + 1) % MAXSIZE;
	_size--;
}

template<typename T>
inline void queue<T>::push(T value)
{
	if ((_rear + 1) % MAXSIZE == _front)
		return;
	data[_rear] = value;
	_rear = (_rear + 1) % MAXSIZE;
	_size++;
}

template<typename T>
inline int queue<T>::size() const
{
	return _size;
}

测试

入列：1 2 3 4 5 6
队元素数量：6
队头：1； 队尾：6
出队：1 2 3 4 5 6

链队列代码实现

采用模版，实现多种数据类型处理

#pragma once
#include <cstdlib>

template<typename T>
struct ListNode {
	T m_nValue;  //储存数据
	struct ListNode *m_pNext;  //指向后继
};

template<typename T>
class Lqueue
{
public:
	Lqueue();
	~Lqueue() {};

	T back()const;	 //返回最后一个元素
	bool empty()const;	 //如果队列空则返回真
	T front()const;		//返回第一个元素
	void pop();		//删除第一个元素
	void push(T value);		//在末尾加入一个元素
	int size()const;	//返回队列中元素的个数
private:
	ListNode<T>* pFront;   //头指针，一直指向头结点，它的后继节点若存在则为队头
	ListNode<T>* pRear;   //尾指针，若不指向头结点则指向队尾
	int _size;   //队长度
};

template<typename T>
inline Lqueue<T>::Lqueue()
{
	pFront = pRear = (ListNode<T>*)new ListNode<T>;	//初始化空队列，头指针和尾指针都指向头结点
	_size = 0;	//长度为0
}

template<typename T>
inline T Lqueue<T>::back() const
{
	if (pFront == pRear)
		return 0;
	return pRear->m_nValue;
}

template<typename T>
inline bool Lqueue<T>::empty() const
{
	if (pFront == pRear)
		return true;
	return false;
}

template<typename T>
inline T Lqueue<T>::front() const
{
	if (pFront == pRear)
		return 0;
	return pFront->m_pNext->m_nValue;
}

template<typename T>
inline void Lqueue<T>::pop()
{
	if (pFront == pRear)
		return;
	ListNode<T>* r = pFront->m_pNext;//暂存队头节点
	pFront->m_pNext = pFront->m_pNext->m_pNext;//将原队头节点后继节点赋为队头
	if (r == pRear) //若队头也是队尾则将头指针与尾指针指向头结点
		pRear = pFront;
	delete r; //删除队头
	_size--;
}

template<typename T>
inline void Lqueue<T>::push(T value)
{
	pRear->m_pNext = (ListNode<T>*)new ListNode<T>;//新分配节点
	pRear = pRear->m_pNext;//将新分配节点设为新队尾
	pRear->m_nValue = value;
	pRear->m_pNext = nullptr;//新队尾指向空
	_size++;
}

template<typename T>
inline int Lqueue<T>::size() const
{
	return _size;
}

测试

入列：1 2 3 4 5 6
队元素数量：6
队头：1； 队尾：6
出队：1 2 3 4 5 6