目录
模板：相关讲解
一、队列
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.声明：
? 顺序队列：
const int Queuesize = 100;
template <class T>
class CirQueue
{
private ://顺序队列
T* data;
int front;
int rear;
int num ;
int m_Size;
public:
CirQueue();
CirQueue(int m_size);//
~CirQueue();
bool enQueue(T item);
bool deQueue(T* item);
bool getFront(T* item);
bool isEmpty();
bool isFull();
void clearQueue();
void displayQueue();
int queueLength();
};? 链队列：
template <class T>
struct Node//定义一个结构体含有 数据 和 指针
{
T data;
struct Node* next;
};
template <class T>
class LinkQueue
{
private :
int num; //还是用来记录元素个数
struct Node<T>* front;
struct Node<T>* rear;
public:
LinkQueue();
~LinkQueue();
bool enQueue(T item);
bool deQueue(T* item);
bool getFront(T* item);
bool isEmpty();
void clearQueue();
void displayQueue();
int queueLength();
};?比较：其实变化不大，链队列不再设置队列长度，不用判断队列是否队满。
2.初始化数据? ?
顺序队列：
template<class T>
CirQueue<T>::CirQueue(int Size)
{
num = 0;
front = rear = -1;
data = new T[Size];
m_Size = Size;
}链队列：?
template<class T>
LinkQueue<T>::LinkQueue()
{
num = 0;
front = new Node<T>;
front->next = NULL;
rear = front;
}3.入队?
顺序队列：
template<class T>
bool CirQueue<T>::enQueue(T item)
{
if (isFull()) return 0;
else
{
rear = (rear + 1)%m_Size ;
data[rear] = item;
num++;
return 1;
}
}链队列：
template<class T>
bool LinkQueue<T>::enQueue(T item)
{
struct Node<T> *s = new struct Node<T>;
s->data = item;
s->next = NULL;
rear->next = s;
rear = s;
num++;
return 1;
}?4.出队
因为设定的是bool类型，所以要获得出队列的数据，需要通过一个指针，来去除出对的数据
顺序队列：
template<class T>
bool CirQueue<T>::deQueue(T* item)
{
if (isEmpty()) return 0;
else
{
front = (front + 1) % m_Size;
*item = data[front];
num--;
return 1;
}
}链队列：
?当时最后一个数据时
if (p->next == NULL)//只有一个元素（边界情况）
?? ??? ??? ?rear = front;
template<class T>
bool LinkQueue<T>::deQueue(T* item)
{
if (isEmpty()) return 0;
else
{
struct Node<T>* p;
p = front->next;
*item = p->data;
front->next = p->next;
if (p->next == NULL)//只有一个元素（边界情况）
rear = front;
delete p;
num--;
return 1;
}
}5.判断队满和队空
?顺序队列：
? ? 此时就用到初始定义其用的 num,如果num = 0,代表队列里没有数据，无法出队和获得队首数据。如果num = m_Size,说明队列满了，不能再进队了。
template<class T>
bool CirQueue<T>::isEmpty()
{
if (num == 0) return 1;
else return 0;
}
template<class T>
bool CirQueue<T>::isFull()
{
if (num == m_Size) return 1;
else return 0;
}链队列：
template<class T>
bool LinkQueue<T>::isEmpty()
{
if (num == 0) return 1;
else return 0;
}?6.获得栈顶元素
顺序队列：
template<class T>
bool CirQueue<T>::getFront(T* item)
{
int i;
if (isEmpty()) return 0;
i = (front+1)%m_Size;
*item = data[i];
return 1;
}
链队列：?
template<class T>
bool LinkQueue<T>::getFront(T* item)
{
if (isEmpty()) return 0;
*item = (front->next)->data;
return 1;
}?7.清空队列
顺序队列：
template<class T>
void CirQueue<T>::clearQueue()
{
delete[]data;
}链队列：
template<class T>
void LinkQueue<T>::clearQueue()
{
while (front!= NULL)
{
struct Node<T>* p = front->next;
front->next = p->next;
if (p->next == NULL)//只有一个元素（边界情况）
rear = front;
delete p;
num--;
}
}?8.显示队列数据
顺序链表：
template<class T>
void CirQueue<T>::displayQueue()
{
int i = (front + 1) % m_Size;
cout << "队列从队首到队尾数据依次为：" << endl;
for ( ; i < m_Size; i++)
{
cout << " " << data[i]<<" " << endl;
}
}链队列：
template<class T>
void LinkQueue<T>::displayQueue()
{
struct Node<T>*p = front->next;
cout << "队列从队首到队尾数据依次为：" << endl;
while(p)
{
cout << " " << p->data <<" " << endl;
p = p->next;
}
}四、模板（自制）?
1.顺序队列
#include<iostream>
using namespace std;
const int Queuesize = 100;
template <class T>
class CirQueue
{
private:
T* data;
int front;
int rear;
int num;
int m_Size;
public:
CirQueue();
CirQueue(int m_size);
~CirQueue();
bool enQueue(T item);
bool deQueue(T* item);
bool getFront(T* item);
bool isEmpty();
bool isFull();
void clearQueue();
void displayQueue();
int queueLength();
};
template<class T>
CirQueue<T>::CirQueue(int Size)
{
num = 0;
front = rear = -1;
data = new T[Size];
m_Size = Size;
}
template<class T>
CirQueue<T>::~CirQueue()
{
clearQueue();
delete front;
}
template<class T>
bool CirQueue<T>::enQueue(T item)
{
if (isFull()) return 0;
else
{
rear = (rear + 1) % m_Size;
data[rear] = item;
num++;
return 1;
}
}
template<class T>
bool CirQueue<T>::deQueue(T* item)
{
if (isEmpty()) return 0;
else
{
front = (front + 1) % m_Size;
*item = data[front];
num--;
return 1;
}
}
template<class T>
bool CirQueue<T>::getFront(T* item)
{
int i;
if (isEmpty()) return 0;
i = (front + 1) % m_Size;
*item = data[i];
return 1;
}
template<class T>
bool CirQueue<T>::isEmpty()
{
if (num == 0) return 1;
else return 0;
}
template<class T>
bool CirQueue<T>::isFull()
{
if (num == m_Size) return 1;
else return 0;
}
template<class T>
void CirQueue<T>::clearQueue()
{
delete[]data;
}
template<class T>
void CirQueue<T>::displayQueue()
{
int i = (front + 1) % m_Size;
cout << "队列从队首到队尾数据依次为：" << endl;
for (; i <m_Size; i++)
{
cout << " " << data[i] << " " << endl;
}
}
template<class T>
int CirQueue<T>::queueLength()
{
return num;
}
int main()
{
int n;
int x = 0;
int temp = 0;
int count = 0;
CirQueue<int> p1(9);
int i = 0;
for (; i < 9; i++)
{
p1.enQueue(i + 1);//入队
//cout << "上一个数据是"<< x << endl;
}
n = p1.getFront(&temp);//获得队首元素
cout << "队首数据是：" << temp << endl;
n = p1.deQueue(&temp);//出队
cout << "出对后的队列长度：" << p1.queueLength() << endl;//出对后的队列长度
p1.displayQueue();//显示队列数据
return 0;
}
? ? ? ? 结果：
??
2.链队列
#include<iostream>
using namespace std;
//const int Queuesize = 100;
template <class T>
struct Node
{
T data;
struct Node* next;
};
template <class T>
class LinkQueue
{
private :
int num;
struct Node<T>* front;
struct Node<T>* rear;
public:
LinkQueue();
~LinkQueue();
bool enQueue(T item);
bool deQueue(T* item);
bool getFront(T* item);
bool isEmpty();
void clearQueue();
void displayQueue();
int queueLength();
};
template<class T>
LinkQueue<T>::LinkQueue()
{
num = 0;
front = new Node<T>;
front->next = NULL;
rear = front;
}
template<class T>
LinkQueue<T>::~LinkQueue()
{
clearQueue();
}
template<class T>
bool LinkQueue<T>::enQueue(T item)
{
struct Node<T> *p = new struct Node<T>;
p->data = item;
p->next = NULL;
rear->next = p;
rear = p;
num++;
return 1;
}
template<class T>
bool LinkQueue<T>::deQueue(T* item)
{
if (isEmpty()) return 0;
else
{
struct Node<T>* p;
p = front->next;
*item = p->data;
if (p->next == NULL)//只有一个元素（边界情况）
rear = front;
else
{
front->next = p->next;
}
delete p;
num--;
return 1;
}
}
template<class T>
bool LinkQueue<T>::getFront(T* item)
{
if (isEmpty()) return 0;
*item = (front->next)->data;
return 1;
}
template<class T>
bool LinkQueue<T>::isEmpty()
{
if (num == 0) return 1;
else return 0;
}
template<class T>
void LinkQueue<T>::clearQueue()
{
while (front!= NULL)
{
struct Node<T>* p = front->next;
front->next = p->next;
if (p->next == NULL)//只有一个元素（边界情况）
rear = front;
delete p;
num--;
}
}
template<class T>
void LinkQueue<T>::displayQueue()
{
struct Node<T>*p = front->next;
cout << "队列从队首到队尾数据依次为：" << endl;
while(p)
{
cout << " " << p->data <<" " << endl;
p = p->next;
}
}
template<class T>
int LinkQueue<T>::queueLength()
{
return num;
}
int main()
{
int n;
int x = 0;
int temp = 0;
int count = 0;
LinkQueue<int> p1;
int i = 3;
for (; i < 9; i++)
{
p1.enQueue(i + 1);//入队
//cout << "上一个数据是"<< x << endl;
}
n = p1.getFront(&temp);//获得队首元素
cout << "队首数据是：" << temp << endl;
n = p1.deQueue(&temp);//出队
cout << "出对后的队列长度：" << p1.queueLength() << endl;//出对后的队列长度
p1.displayQueue();//显示队列数据
return 0;
}
?结果：
思考:
约瑟夫问题?
约瑟夫问题：有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下的猴子再接着从1开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的编号。
（文章创作不易，转载请声明，谢谢。文章仅仅是个人总结，如有错误，还请大佬指出，如果有什么不恰当的地方，也欢迎在评论区讨论）