顺序队列和链式队列的实现（c++）

什么是队列

• 队列是一种受限的线性表，其特点是在一端进行插入操作，在另一端进行删除操作；把允许进行插入一端是队尾，允许删除操作的的一端成为队头。
• 先进先出，后进后出的特性
• 在STL标准库中，有queue（队列）和deque（双端队列）两种容器，双端队列是允许两端都可以进行入队列和出队列操作。
• 应用
  • 去营业系统办理业务使用的叫号系统
  • 排队购物
  • 多个人同时使用网络打印机打印文件

---

顺序队列

普通的顺序队列的编程实现

• 顺序队列与线性表几乎是一致的，不一一进行阐述。

• 缺点：

  

  • 从上面这张图可以判断该队列并没有完全存满，m_data[0]并没有存满，但是由于该队列只能在队尾插入元素，故m_data[0]就没办法插入，因此就引入循环队列的概念。

#include <iostream>


#ifdef _DEBUG   //只在Debug（调试）模式下
#ifndef DEBUG_NEW
#define DEBUG_NEW new(_NORMAL_BLOCK,__FILE__,__LINE__) //重新定义new运算符
#define new DEBUG_NEW
#endif
#endif

using namespace std;

namespace _nmsp1
{
	#define MaxSize 10
	

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

	public:
		bool EnQueue(const T& e);
		bool DeQueue(T& e);
		bool GetHead(T& e);
		void ClearQueue();

		void DispQueue();
		int QueueLength();

		bool IsEmpty();
		bool IsFull();
	private:
		T* m_data;
		int m_front;			//对头，删除的一端
		int m_rear;				//队尾，插入的一端
	};


	template<typename T>
	SeqQueue<T>::SeqQueue()
	{
		m_data = new T[MaxSize];//为一维动态数组分配内存
		m_front = 0;
		m_rear = 0;				//空队列，队头和队尾=0
	}
	template<typename T>
	SeqQueue<T>::~SeqQueue()
	{
		delete[] m_data;
	}


	//入队
	template<typename T>
	bool SeqQueue<T>::EnQueue(const T& e)
	{
		if (IsFull() == true)
		{
			cout << "该队列已满" << endl;
			return false;

		}
		m_data[m_rear] = e;
		m_rear++;		//入队列操作队尾指针往后走		
		return true;
	}

	template<typename T>
	bool SeqQueue<T>::DeQueue(T& e)
	{
		if (IsEmpty() == true)
		{
			cout << "该队列是空的" << endl;
			return false;

		}
		e = m_data[m_front];
		m_front++;		//出队列队首指针往后走
		return true;
	}

	//读取队头元素，但该元素并没有出队列而是依旧在队列中
	template <typename T>
	bool SeqQueue<T>::GetHead(T& e)
	{
		if (IsEmpty() == true)
		{
			cout << "当前顺序队列为空，不能读取队头元素!" << endl;
			return false;
		}

		e = m_data[m_front];  //队头元素返回到e中。
		return true;
	}

	//输出顺序队列中的所有元素，时间复杂度为O(n)
	template<class T>
	void SeqQueue<T>::DispQueue()
	{
		//按照从对头到队尾的顺序来显示数据
		//for (int i = m_front; i < m_rear ; ++i)
		for (int i = m_front; i != m_rear;)
		{
			cout << m_data[i] << " ";  //每个数据之间以空格分隔
			i = (i + 1) % MaxSize;
		}
		cout << endl; //换行
	}


	//获取顺序队列的长度（实际拥有的元素数量），时间复杂度为O(1)
	template<class T>
	int SeqQueue<T>::QueueLength()
	{
		return m_rear - m_front;
		
	}


	//判断顺序队列是否为空，时间复杂度为O(1)
	template<class T>
	bool SeqQueue<T>::IsEmpty()
	{
		if (m_front == m_rear)
		{
			return true;
		}
		return false;
	}

	//判断顺序队列是否已满，时间复杂度为O(1)
	template<class T>
	bool SeqQueue<T>::IsFull()
	{
		//if(m_rear >= MaxSize) //队尾指针和数组容量做比较
		if ((m_rear + 1) % MaxSize == m_front)
		{
			return true;
		}
		return false;
	}



	//将队列清空 记住这个特性
	template<class T>
	void SeqQueue<T>::ClearQueue()
	{
		m_front = m_rear = 0;
	}
}

int main()
{
	_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);//程序退出时检测内存泄漏并显示到“输出”窗口

	_nmsp1::SeqQueue<int> seqobj;
	seqobj.EnQueue(150);
	seqobj.EnQueue(200);
	seqobj.EnQueue(300);
	seqobj.EnQueue(400);
	seqobj.DispQueue();

	cout << "---------" << endl;
	int eval = 0;
	seqobj.DeQueue(eval);
	seqobj.DeQueue(eval);
	seqobj.DispQueue();

	cout << "---------" << endl;
	seqobj.EnQueue(500);
	seqobj.EnQueue(600);
	seqobj.EnQueue(700);
	seqobj.EnQueue(800);
	seqobj.EnQueue(900);
	seqobj.EnQueue(1000);
	seqobj.EnQueue(1100);

	//seqobj.EnQueue(1200);
	seqobj.DispQueue();
	seqobj.EnQueue(1100);
	seqobj.EnQueue(1100);
	seqobj.EnQueue(1100);

	return 0;
}

循环队列（顺序）(两种实现方法)

牺牲一个保存元素空间的方法

• 入队列的改进

//入队
	template<typename T>
	bool SeqQueue<T>::EnQueue(const T& e)
	{
		if (IsFull() == true)
		{
			cout << "该队列已满" << endl;
			return false;

		}
		m_data[m_rear] = e;
		//m_rear++;
		m_rear = (m_rear + 1) % MaxSize; //队尾指针加1并取余，这样m_data的下标就控制在了0到(MaxSize-1)之间了
		return true;
	}

• 出队列的改进

template<typename T>
	bool SeqQueue<T>::DeQueue(T& e)
	{
		if (IsEmpty() == true)
		{
			cout << "该队列是空的" << endl;
			return false;

		}
		e = m_data[m_front];
		//m_front++;
		m_front = (m_front + 1) % MaxSize;//引入这段代码
		return true;
	}

• 获取顺序队列的长度

//获取顺序队列的长度（实际拥有的元素数量），时间复杂度为O(1)
template<class T>
int SeqQueue<T>::QueueLength()
{
	//return m_rear - m_front;
	return (m_rear + MaxSize - m_front) % MaxSize;
}

• 如何判断队列为空，队列已满

  • if(m_front == m_rear)判断为空
  • 队列已满：常用的方法是通过牺牲一个保存元素空间的来判断：假设存储10个元素，但是实际只能村上9个元素就已经判断该队列处于已满的状态，相当于第10个元素用来作为判断的条件。

  //判断顺序队列是否已满，时间复杂度为O(1)
  	template<class T>
  	bool SeqQueue<T>::IsFull()
  	{
  		//if(m_rear >= MaxSize) //队尾指针和数组容量做比较
  		if ((m_rear + 1) % MaxSize == m_front)
  		{
  			return true;
  		}
  		return false;
  	}

  全部代码

  #include <iostream>
  
  
  #ifdef _DEBUG   //只在Debug（调试）模式下
  #ifndef DEBUG_NEW
  #define DEBUG_NEW new(_NORMAL_BLOCK,__FILE__,__LINE__) //重新定义new运算符
  #define new DEBUG_NEW
  #endif
  #endif
  
  using namespace std;
  
  namespace _nmsp1
  {
  	#define MaxSize 10
  	
  
  	template <typename T>
  	class SeqQueue
  	{
  	public:
  		SeqQueue();
  		~SeqQueue();
  
  	public:
  		bool EnQueue(const T& e);
  		bool DeQueue(T& e);
  		bool GetHead(T& e);
  		void ClearQueue();
  
  		void DispQueue();
  		int QueueLength();
  
  		bool IsEmpty();
  		bool IsFull();
  	private:
  		T* m_data;
  		int m_front;			//对头，删除的一端
  		int m_rear;				//队尾，插入的一端
  	};
  
  
  	template<typename T>
  	SeqQueue<T>::SeqQueue()
  	{
  		m_data = new T[MaxSize];
  		m_front = 0;
  		m_rear = 0;				//空队列，队头和队尾=0
  	}
  	template<typename T>
  	SeqQueue<T>::~SeqQueue()
  	{
  		delete[] m_data;
  	}
  
  
  	//入队
  	template<typename T>
  	bool SeqQueue<T>::EnQueue(const T& e)
  	{
  		if (IsFull() == true)
  		{
  			cout << "该队列已满" << endl;
  			return false;
  
  		}
  		m_data[m_rear] = e;
  		//m_rear++;
  		m_rear = (m_rear + 1) % MaxSize; //队尾指针加1并取余，这样m_data的下标就控制在了0到(MaxSize-1)之间了
  		return true;
  	}
  
  	template<typename T>
  	bool SeqQueue<T>::DeQueue(T& e)
  	{
  		if (IsEmpty() == true)
  		{
  			cout << "该队列是空的" << endl;
  			return false;
  
  		}
  		e = m_data[m_front];
  		//m_front++;
  		m_front = (m_front + 1) % MaxSize;
  		return true;
  	}
  
  	//读取队头元素，但该元素并没有出队列而是依旧在队列中
  	template <typename T>
  	bool SeqQueue<T>::GetHead(T& e)
  	{
  		if (IsEmpty() == true)
  		{
  			cout << "当前顺序队列为空，不能读取队头元素!" << endl;
  			return false;
  		}
  
  		e = m_data[m_front];  //队头元素返回到e中。
  		return true;
  	}
  
  	//输出顺序队列中的所有元素，时间复杂度为O(n)
  	template<class T>
  	void SeqQueue<T>::DispQueue()
  	{
  		//按照从对头到队尾的顺序来显示数据
  		//for (int i = m_front; i < m_rear ; ++i)
  		for (int i = m_front; i != m_rear;)
  		{
  			cout << m_data[i] << " ";  //每个数据之间以空格分隔
  			i = (i + 1) % MaxSize;
  		}
  		cout << endl; //换行
  	}
  
  
  	//获取顺序队列的长度（实际拥有的元素数量），时间复杂度为O(1)
  	template<class T>
  	int SeqQueue<T>::QueueLength()
  	{
  		//return m_rear - m_front;
  		return (m_rear + MaxSize - m_front) % MaxSize;
  	}
  
  
  	//判断顺序队列是否为空，时间复杂度为O(1)
  	template<class T>
  	bool SeqQueue<T>::IsEmpty()
  	{
  		if (m_front == m_rear)
  		{
  			return true;
  		}
  		return false;
  	}
  
  	//判断顺序队列是否已满，时间复杂度为O(1)
  	template<class T>
  	bool SeqQueue<T>::IsFull()
  	{
  		//if(m_rear >= MaxSize) //队尾指针和数组容量做比较
  		if ((m_rear + 1) % MaxSize == m_front)
  		{
  			return true;
  		}
  		return false;
  	}
  
  
  
  	//将队列清空 记住这个特性
  	template<class T>
  	void SeqQueue<T>::ClearQueue()
  	{
  		m_front = m_rear = 0;
  	}
  }
  
  int main()
  {
  	_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);//程序退出时检测内存泄漏并显示到“输出”窗口
  
  	_nmsp1::SeqQueue<int> seqobj;
  	seqobj.EnQueue(150);
  	seqobj.EnQueue(200);
  	seqobj.EnQueue(300);
  	seqobj.EnQueue(400);
  	seqobj.DispQueue();
  
  	cout << "---------" << endl;
  	int eval = 0;
  	seqobj.DeQueue(eval);
  	seqobj.DeQueue(eval);
  	seqobj.DispQueue();
  
  	cout << "---------" << endl;
  	seqobj.EnQueue(500);
  	seqobj.EnQueue(600);
  	seqobj.EnQueue(700);
  	seqobj.EnQueue(800);
  	seqobj.EnQueue(900);
  	seqobj.EnQueue(1000);
  	seqobj.EnQueue(1100);
  
  	//seqobj.EnQueue(1200);
  	seqobj.DispQueue();
  	seqobj.EnQueue(1100);
  	seqobj.EnQueue(1100);
  	seqobj.EnQueue(1100);
  
  	return 0;
  }

---

引入一个变量标记

• 引入一个char类型的成员变量m_tag,初始值为0，当执行出队列操作时，把该变量的设置为0，当执行入队列操作时，把该变量的值设置为1，这样就可以显示最近执行的时删除操作和插入操作

• 只有出队列操作才会导致队列为空，只有入队列才会导致队列变满

  入队操作的编程实现

template <typename T>
bool SeqQueue<T>::EnQueue(const T& e)
{
    if(IsFull == true)
    {
        cout<<"该队列已满"<<endl;
        return false;
    }
    
    m_tag = 1;
    m_data[m_rear] = e;
	//m_rear++;
	m_rear = (m_rear + 1) % MaxSize; //队尾指针加1并取余，这样m_data的下标就控制在了0到(MaxSize-1)之间了
	return true;
}

判断是否已满操作

//判断顺序队列是否已满，时间复杂度为O(1)
	template<class T>
	bool SeqQueue<T>::IsFull()
	{
		
		if (m_front == m_rear && m_tag == 1 )
		{
			return true;
		}
		return false;
	}

出队列操作

template<typename T>
	bool SeqQueue<T>::DeQueue(T& e)
	{
		if (IsEmpty() == true)
		{
			cout << "该队列是空的" << endl;
			return false;

		}
        m_tag = 0;  //出队标记
		e = m_data[m_front];
		m_front = (m_front + 1) % MaxSize;
		return true;
	}

判断是否为空操作

//判断顺序队列是否为空，时间复杂度为O(1)
	template<class T>
	bool SeqQueue<T>::IsEmpty()
	{
		if (m_front == m_rear&& m_tag == 0)
		{
			return true;
		}
		return false;
	}

---

链式队列

• 所谓的链式队列，就是一个操作受限的单链表，只允许在尾部插入元素（队尾），在头部删除元素（对头）。
• 一定要及时更新队尾指针
• 和单链表几乎一致的代码，不一一说明

#include<iostream>
#ifdef _DEBUG   //只在Debug（调试）模式下
#ifndef DEBUG_NEW
#define DEBUG_NEW new(_NORMAL_BLOCK,__FILE__,__LINE__) //重新定义new运算符
#define new DEBUG_NEW
#endif
#endif  
using namespace std;

namespace _nmsp1
{
	template<typename T>
	struct QueueNode
	{
		T data;
		QueueNode* next;
	};

	template<typename T>
	class LinkQueue
	{
	public:
		LinkQueue();
		~LinkQueue();
	public:
		bool EnQueue(const T& s);
		bool DeQueue(T& e);
		bool GetHead(T& e);

		void DispQueue();
		int QueueLength();
		bool IsEmpty();

	private:
		QueueNode<T>* m_front;
		QueueNode<T>* m_rear;
		int m_length;
	};

	//构造函数
	template<typename T>
	LinkQueue<T>::LinkQueue()
	{
		m_front = new QueueNode<T>;
		m_front->next = nullptr;
		m_rear = m_front;
		m_length;
	}

	template<typename T>
	LinkQueue<T>::~LinkQueue()
	{
		QueueNode<T>* pnode = m_front->next;	//首先删除的头结点之后的第一个元素
		QueueNode<T>* ptmp;
		while (pnode != nullptr)
		{
			ptmp = pnode;
			pnode = pnode->next;
			delete ptmp;

		}
		delete m_front;							//删除头结点
		m_front = m_rear = nullptr;				
		m_length = 0;
	}

	//入队列操作
	template<typename T>
	bool LinkQueue<T>::EnQueue(const T& e)
	{
		QueueNode<T>* node = new QueueNode<T>;
		node->data = e;
		node->next = nullptr;				//只能在队尾插入
		m_rear->next = node;
		m_rear = node;						//更新尾指针
		m_length++;
		return true;
	}


	//出队列操作
	template<typename T>
	bool LinkQueue<T>::DeQueue(T& e)
	{
		if (IsEmpty() == true)
		{
			cout << "该队列为空" << endl;
			return false;
		}

		QueueNode<T>* p_willdel = m_front->next;		//出的是头结点之后第一个元素，不是头结点
		e = p_willdel->data;
		m_front->next = p_willdel->next;
		if (m_rear == p_willdel)
		{
			m_rear = m_front;			//当队列只有一个头结点和一个元素结点，删除后就更新尾指针
		}
		delete p_willdel;
		m_length--;
		return true;
	}

	//读取队头元素，但该元素并没有出队列而是依旧在队列中
	template <typename T>
	bool LinkQueue<T>::GetHead(T& e)
	{
		if (IsEmpty() == true)
		{
			cout << "当前链式队列为空，不能读取队头元素!" << endl;
			return false;
		}

		e = m_front->next->data;
		return true;
	}
	
	//输出链式队列中的所有元素，时间复杂度为O(n)
	template<class T>
	void LinkQueue<T>::DispQueue()
	{
		QueueNode<T>* p = m_front->next;
		while (p != nullptr)
		{
			cout << p->data << " ";  //每个数据之间以空格分隔
			p = p->next;
		}
		cout << endl; //换行
	}

	//获取链式队列的长度（实际拥有的元素数量），时间复杂度为O(1)
	template<class T>
	int LinkQueue<T>::QueueLength()
	{
		return m_length;
	}

	//判断链式队列是否为空，时间复杂度为O(1)
	template<class T>
	bool LinkQueue<T>::IsEmpty()
	{
		if (m_front == m_rear) //当然，换一种判断方式也行：if(m_front->next == nullptr) return true;
		{
			return true;
		}
		return false;
	}



}


int main()
{
	_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);//程序退出时检测内存泄漏并显示到“输出”窗口

	_nmsp1::LinkQueue<int> lnobj;
	lnobj.EnQueue(150);

	int eval = 0;
	lnobj.DeQueue(eval);
	lnobj.EnQueue(200);
	lnobj.EnQueue(700);
	lnobj.DispQueue();

	return 0;
}