devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

顺序队列和链队列（Queue模板）_定义队列类模板queue

作者：知新_RL | 2024-08-13 12:46:36

赞

踩

定义队列类模板queue

目录

模板：相关讲解

一、队列

1.定义：

2.储存方式：

3.基本操作:

二、判断顺序队列队满的三种方法

三、基本操作： 

1.声明

        2.初始化数据   

        3.入队 

        4.出队

        5.判断队满和队空

        6.获得栈顶元素

        7.清空队列

         8.显示队列数据

四、模板（自制） 

1.顺序队列

2.链队列

模板：相关讲解

一、队列

1.定义：

只允许在一端进行插入操作，而另一端进行删除 操作的线性表。

顺序队列

 链队列

  

2.储存方式：

顺序储存和链式储存

3.基本操作:

   1)   CirQueue(int m_size): 建立长度为size的队列
   2)  bool enQueue(T item): 入队
   3)  bool deQueue(T* item): 出队
   4)  bool getFront(T* item): 读取队头元素，但不删除
   5)  bool isEmpty(): 判断队列是否为空
   6)  bool isFull(): 判断队列是否为满(如果是链队列就不需要判断)
   7)  void clearQueue(): 清空队列
   8）void displayQueue() : 显示队列内容
   9）int queueLength(): 获取队列元素个数

二、判断顺序队列队满的三种方法

方法一：附设一个存储队列中元素个数的变量num，当num=0时队空，当num=QueueSize时为队满；（这也是我喜欢采用的方式，还可以记录队列个数，在获取队列元素个数时比较方便） 

方法二：修改队满条件，浪费一个元素空间，队满时数组中只有一个空闲单元；

方法三：设置标志flag，当front=rear且flag=0时为队空，当front=rear且flag=1时为队满。

三、基本操作： 

1.声明：

  顺序队列：

  1. const int Queuesize = 100;
  2. template <class T>
  3. class CirQueue
  4. {
  5. private ://顺序队列
  6. 	T* data;
  7. 	int front;
  8. 	int rear;
  9. 	int num ;
  10. 	int m_Size;
  11. public:
  12. 	CirQueue();                                  
  13. 	CirQueue(int m_size);//                      
  14. 	~CirQueue();                               
  15. 	bool enQueue(T item);				
  16. 	bool deQueue(T* item);            
  17. 	bool getFront(T* item);           
  18. 	bool isEmpty();                            
  19. 	bool isFull();                                 
  20. 	void clearQueue();                       
  21. 	void displayQueue();                   
  22. 	int queueLength();            
  23. };

  链队列：

  1. template <class T>
  2. struct Node//定义一个结构体含有 数据 和 指针
  3. {
  4. 	T data;
  5. 	struct Node* next;
  6. };
  7.  
  8. template <class T>
  9. class LinkQueue
  10. {
  11. private :
  12. 	int num;  //还是用来记录元素个数
  13. 	struct Node<T>* front;
  14. 	struct Node<T>* rear;
  15. public:
  16. 	LinkQueue();                                                       
  17. 	~LinkQueue();                               
  18. 	bool enQueue(T item);				
  19. 	bool deQueue(T* item);            
  20. 	bool getFront(T* item);           
  21. 	bool isEmpty();                                                         
  22. 	void clearQueue();                       
  23. 	void displayQueue();                   
  24. 	int queueLength();            
  25. };

 比较：其实变化不大，链队列不再设置队列长度，不用判断队列是否队满。

2.初始化数据   

顺序队列：

  1. template<class T>
  2. CirQueue<T>::CirQueue(int Size)
  3. {
  4. 	num = 0;
  5. 	front = rear = -1;
  6. 	data = new T[Size];
  7. 	m_Size = Size;
  8. }

链队列： 

  1. template<class T>
  2. LinkQueue<T>::LinkQueue()
  3. {
  4. 	num = 0;
  5. 	front = new Node<T>;
  6. 	front->next = NULL;
  7. 	rear = front;
  8. }

3.入队 

顺序队列：

  1. template<class T>
  2. bool CirQueue<T>::enQueue(T item)
  3. {
  4. 	if (isFull()) return 0;
  5. 	else
  6. 	{
  7. 		rear = (rear  + 1)%m_Size ;
  8. 		data[rear] = item;
  9. 		num++;
  10. 		return 1;
  11. 	}
  12. }

链队列：

  1. template<class T>
  2. bool LinkQueue<T>::enQueue(T item)
  3. {
  4. 	struct Node<T> *s = new struct Node<T>;
  5. 	s->data = item;
  6. 	s->next = NULL;
  7. 	rear->next = s;
  8. 	rear = s;
  9. 	num++;
  10. 	return 1;
  11. }

 4.出队

因为设定的是bool类型，所以要获得出队列的数据，需要通过一个指针，来去除出对的数据

顺序队列：

  1. template<class T>
  2. bool CirQueue<T>::deQueue(T* item)
  3. {
  4. 	if (isEmpty()) return 0;
  5. 	else
  6. 	{
  7. 		front = (front + 1) % m_Size;
  8. 		*item = data[front];
  9. 		num--;
  10. 		return 1;	
  11. 	}
  12. }

链队列：

 当时最后一个数据时

if (p->next == NULL)//只有一个元素（边界情况）
            rear = front;

  1. template<class T>
  2. bool LinkQueue<T>::deQueue(T* item)
  3. {
  4. 	if (isEmpty()) return 0;
  5. 	else
  6. 	{
  7. 		struct Node<T>* p;
  8. 		p = front->next;
  9. 		*item = p->data;
  10.         front->next = p->next;
  11. 		if (p->next == NULL)//只有一个元素（边界情况）
  12. 			rear = front;
  13. 		delete p;
  14. 		num--;
  15. 		return 1;	
  16. 	}
  17. }

5.判断队满和队空

 顺序队列：

    此时就用到初始定义其用的 num,如果num = 0,代表队列里没有数据，无法出队和获得队首数据。如果num = m_Size,说明队列满了，不能再进队了。

  1. template<class T>
  2. bool CirQueue<T>::isEmpty()
  3. {
  4. 	if (num == 0) return 1;
  5. 	else return 0;
  6. }
  7.  
  8. template<class T>
  9. bool CirQueue<T>::isFull()
  10. {
  11. 	if (num == m_Size) return 1;
  12. 	else return 0;
  13. }

链队列：

  1. template<class T>
  2. bool LinkQueue<T>::isEmpty()
  3. {
  4. 	if (num == 0) return 1;
  5. 	else return 0;
  6. }

 6.获得栈顶元素

顺序队列：

  1. template<class T>
  2. bool CirQueue<T>::getFront(T* item)
  3. {
  4. 	int i;
  5. 	if (isEmpty()) return 0;
  6. 	i = (front+1)%m_Size;
  7. 	*item = data[i];
  8. 	return 1;
  9. }

链队列： 

  1. template<class T>
  2. bool LinkQueue<T>::getFront(T* item)
  3. {
  4.  
  5. 	if (isEmpty()) return 0;
  6. 	*item = (front->next)->data;
  7. 	return 1;
  8. }

 7.清空队列

顺序队列：

  1. template<class T>
  2. void CirQueue<T>::clearQueue()
  3. {
  4. 	delete[]data;
  5. }

链队列：

  1. template<class T>
  2. void LinkQueue<T>::clearQueue()
  3. {
  4.  
  5. 	while (front!= NULL)
  6. 	{
  7. 		struct Node<T>* p = front->next;
  8. 		if (p->next == NULL)//只有一个元素（边界情况）
  9. 			{
  10.               rear = front;
  11.               break;
  12.              }
  13.         else
  14.             front->next = p->next;
  15. 		delete p;
  16. 		num--;
  17. 	}
  18. 	
  19. }

 8.显示队列数据

顺序链表：

  1. template<class T>
  2. void CirQueue<T>::displayQueue()
  3. {
  4. 	int i = (front + 1) % m_Size;
  5. 	cout << "队列从队首到队尾数据依次为：" << endl;
  6. 	for ( ; i < m_Size; i++)
  7. 	{
  8. 		cout << " " << data[i]<<" " << endl;
  9. 	}
  10. }

链队列：

  1. template<class T>
  2. void LinkQueue<T>::displayQueue()
  3. {
  4. 	struct Node<T>*p = front->next;
  5. 	cout << "队列从队首到队尾数据依次为：" << endl;
  6. 	while(p)
  7. 	{
  8. 		cout << " " << p->data <<" " << endl;
  9. 		p = p->next;
  10. 	}
  11. }

四、模板（自制） 

1.顺序队列

  1. #include<iostream>
  2. using namespace std;
  3. const int Queuesize = 100;
  4. template <class T>
  5. class CirQueue
  6. {
  7. private:
  8. 	T* data;
  9. 	int front;
  10. 	int rear;
  11. 	int num;
  12. 	int m_Size;
  13. public:
  14. 	CirQueue();
  15. 	CirQueue(int m_size);
  16. 	~CirQueue();
  17. 	bool enQueue(T item);
  18. 	bool deQueue(T* item);
  19. 	bool getFront(T* item);
  20. 	bool isEmpty();
  21. 	bool isFull();
  22. 	void clearQueue();
  23. 	void displayQueue();
  24. 	int queueLength();
  25. };
  26. template<class T>
  27. CirQueue<T>::CirQueue(int Size)
  28. {
  29. 	num = 0;
  30. 	front = rear = -1;
  31. 	data = new T[Size];
  32.  
  33. 	m_Size = Size;
  34. }
  35. template<class T>
  36. CirQueue<T>::~CirQueue()
  37. {
  38. 	clearQueue();
  39.     delete front;
  40. }
  41.  
  42. template<class T>
  43. bool CirQueue<T>::enQueue(T item)
  44. {
  45. 	if (isFull()) return 0;
  46. 	else
  47. 	{
  48. 		rear = (rear + 1) % m_Size;
  49. 		data[rear] = item;
  50. 		num++;
  51. 		return 1;
  52. 	}
  53. }
  54.  
  55. template<class T>
  56. bool CirQueue<T>::deQueue(T* item)
  57. {
  58. 	if (isEmpty()) return 0;
  59. 	else
  60. 	{
  61. 		front = (front + 1) % m_Size;
  62. 		*item = data[front];
  63. 		num--;
  64. 		return 1;
  65. 	}
  66. }
  67.  
  68. template<class T>
  69. bool CirQueue<T>::getFront(T* item)
  70. {
  71. 	int i;
  72. 	if (isEmpty()) return 0;
  73. 	i = (front + 1) % m_Size;
  74. 	*item = data[i];
  75. 	return 1;
  76. }
  77.  
  78. template<class T>
  79. bool CirQueue<T>::isEmpty()
  80. {
  81. 	if (num == 0) return 1;
  82. 	else return 0;
  83. }
  84.  
  85. template<class T>
  86. bool CirQueue<T>::isFull()
  87. {
  88. 	if (num == m_Size) return 1;
  89. 	else return 0;
  90. }
  91.  
  92. template<class T>
  93. void CirQueue<T>::clearQueue()
  94. {
  95. 	delete[]data;
  96. }
  97.  
  98. template<class T>
  99. void CirQueue<T>::displayQueue()
  100. {
  101. 	int i = (front + 1) % m_Size;
  102. 	cout << "队列从队首到队尾数据依次为：" << endl;
  103. 	for (; i <m_Size; i++)
  104. 	{
  105. 		cout << " " << data[i] << " " << endl;
  106. 	}
  107. }
  108. template<class T>
  109. int CirQueue<T>::queueLength()
  110. {
  111. 	return num;
  112. }
  113.  
  114. int main()
  115. {
  116. 	int n;
  117. 	int x = 0;
  118. 	int temp = 0;
  119. 	int count = 0;
  120. 	CirQueue<int> p1(9);
  121. 	int i = 0;
  122. 	for (; i < 9; i++)
  123. 	{
  124. 		p1.enQueue(i + 1);//入队
  125. 		//cout << "上一个数据是"<< x << endl;
  126. 	}
  127. 	n = p1.getFront(&temp);//获得队首元素
  128. 	cout << "队首数据是：" << temp << endl;
  129. 	n = p1.deQueue(&temp);//出队
  130. 	cout << "出对后的队列长度：" << p1.queueLength() << endl;//出对后的队列长度
  131. 	p1.displayQueue();//显示队列数据
  132. 	return 0;
  133. }

        结果：

  

2.链队列

  1. #include<iostream>
  2. using namespace std;
  3. //const int Queuesize = 100;
  4. template <class T>
  5. struct Node
  6. {
  7. 	T data;
  8. 	struct Node* next;
  9. };
  10.  
  11. template <class T>
  12. class LinkQueue
  13. {
  14. private :
  15. 	int num;
  16. 	struct Node<T>* front;
  17. 	struct Node<T>* rear;
  18. public:
  19. 	LinkQueue();                                                       
  20. 	~LinkQueue();                               
  21. 	bool enQueue(T item);				
  22. 	bool deQueue(T* item);            
  23. 	bool getFront(T* item);           
  24. 	bool isEmpty();                                                         
  25. 	void clearQueue();                       
  26. 	void displayQueue();                   
  27. 	int queueLength();            
  28. };
  29. template<class T>
  30. LinkQueue<T>::LinkQueue()
  31. {
  32. 	num = 0;
  33. 	front = new Node<T>;
  34. 	front->next = NULL;
  35. 	rear = front;
  36. }
  37. template<class T>
  38. LinkQueue<T>::~LinkQueue()
  39. {
  40. 	clearQueue();
  41. }
  42.  
  43. template<class T>
  44. bool LinkQueue<T>::enQueue(T item)
  45. {
  46. 	struct Node<T> *p = new struct Node<T>;
  47. 	p->data = item;
  48. 	p->next = NULL;
  49. 	rear->next = p;
  50. 	rear = p;
  51. 	num++;
  52. 	return 1;
  53. }
  54.  
  55. template<class T>
  56. bool LinkQueue<T>::deQueue(T* item)
  57. {
  58. 	if (isEmpty()) return 0;
  59. 	else
  60. 	{
  61. 		struct Node<T>* p;
  62. 		p = front->next;
  63. 		*item = p->data;
  64. 		if (p->next == NULL)//只有一个元素（边界情况）
  65. 			rear = front;
  66. 		else
  67. 		{
  68. 			front->next = p->next;
  69. 		}
  70. 		delete p;
  71. 		num--;
  72. 		return 1;	
  73. 	}
  74. }
  75.  
  76. template<class T>
  77. bool LinkQueue<T>::getFront(T* item)
  78. {
  79.  
  80. 	if (isEmpty()) return 0;
  81. 	*item = (front->next)->data;
  82. 	return 1;
  83. }
  84.  
  85. template<class T>
  86. bool LinkQueue<T>::isEmpty()
  87. {
  88. 	if (num == 0) return 1;
  89. 	else return 0;
  90. }
  91.  
  92.  
  93. template<class T>
  94. void LinkQueue<T>::clearQueue()
  95. {
  96.  
  97. 	while (front!= NULL)
  98. 	{
  99. 		struct Node<T>* p = front->next;
  100. 		if (p->next == NULL)//只有一个元素（边界情况）
  101. 			{
  102.               rear = front;
  103.               break;
  104.              }
  105.         else
  106.             front->next = p->next;
  107. 		delete p;
  108. 		num--;
  109. 	}
  110. 	
  111. }
  112.  
  113. template<class T>
  114. void LinkQueue<T>::displayQueue()
  115. {
  116. 	struct Node<T>*p = front->next;
  117. 	cout << "队列从队首到队尾数据依次为：" << endl;
  118. 	while(p)
  119. 	{
  120. 		cout << " " << p->data <<" " << endl;
  121. 		p = p->next;
  122. 	}
  123. }
  124. template<class T>
  125. int LinkQueue<T>::queueLength()
  126. {
  127. 	return num;
  128. }
  129.  
  130. int main()
  131. {
  132. 	int n;
  133. 	int x = 0;
  134. 	int temp = 0;
  135. 	int count = 0;
  136. 	LinkQueue<int> p1;
  137. 	int i = 3;
  138. 	for (; i < 9; i++)
  139. 	{
  140. 		p1.enQueue(i + 1);//入队
  141. 		//cout << "上一个数据是"<< x << endl;
  142. 	}
  143. 	n = p1.getFront(&temp);//获得队首元素
  144. 	cout << "队首数据是：" << temp << endl;
  145. 	n = p1.deQueue(&temp);//出队
  146. 	cout << "出对后的队列长度：" << p1.queueLength() << endl;//出对后的队列长度
  147. 	p1.displayQueue();//显示队列数据
  148. 	return 0;
  149. }

 结果：

思考:

约瑟夫问题 

约瑟夫问题：有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下的猴子再接着从1开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的编号。

（文章创作不易，转载请声明，谢谢。文章仅仅是个人总结，如有错误，还请大佬指出，如果有什么不恰当的地方，也欢迎在评论区讨论）

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/975020
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号