100 lines
3.1 KiB
C++
100 lines
3.1 KiB
C++
template<class DT>
|
||
struct SqQueue
|
||
{
|
||
DT* base; // 存储空间基地址
|
||
int front; // 队头指针，指向队首元素
|
||
int rear; // 队尾指针，指向队尾元素的后面
|
||
int queuesize; // 队列容量
|
||
};
|
||
|
||
template<class DT> // 算法3.14 初始化队列
|
||
bool InitQueue(SqQueue<DT>& Q, int m) // 创建容量为m的空队列
|
||
{
|
||
Q.base = new DT[m]; // 1. 申请一组连续的内存空间
|
||
if (!Q.base) exit(1); // 申请失败，退出
|
||
Q.front = Q.rear = 0; // 2. 申请成功，为队列属性赋值
|
||
Q.queuesize = m;
|
||
return true; // 3. 返回true
|
||
}
|
||
|
||
template<class DT> // 算法3.15 销毁队列
|
||
void DestroyQueue(SqQueue<DT>& Q) // 销毁循环队列
|
||
{
|
||
delete[] Q.base; // 1. 释放循环队列占用的内存空间
|
||
Q.front = Q.rear = 0; // 2. 为队列属性赋值
|
||
Q.queuesize = 0;
|
||
}
|
||
|
||
template<class DT> // 算法3.16 入队
|
||
bool EnQueue(SqQueue<DT>& Q, DT e) // 在队尾插入一个新元素
|
||
{
|
||
if ((Q.rear + 1) % Q.queuesize == Q.front) // 1. 队满的情况
|
||
return false; // 无法入队，返回false
|
||
Q.base[Q.rear] = e; // 2. 元素e放在队尾指针处
|
||
Q.rear = (Q.rear + 1) % Q.queuesize; // 队尾指针增1
|
||
return true; // 3. 返回true
|
||
}
|
||
|
||
template<class DT> // 算法3.17 出队
|
||
bool DeQueue(SqQueue<DT>& Q, DT& e) // 删除队头元素
|
||
{
|
||
if (Q.front == Q.rear) // 1. 队空的情况
|
||
return false; // 无法出队，返回false
|
||
e = Q.base[Q.front]; // 2. 取队头元素，赋值给e
|
||
Q.front = (Q.front + 1) % Q.queuesize; // 队头指针加1
|
||
return true; // 3. 返回true
|
||
}
|
||
|
||
template<class DT> // 算法3.18 取队头元素
|
||
bool GetHead(SqQueue<DT> Q, DT& e) // 取队头元素
|
||
{
|
||
if (Q.front == Q.rear) // 1. 队空的情况
|
||
return false; // 无队头元素，返回false
|
||
e = Q.base[Q.front]; // 2. 取队头元素，赋值给e
|
||
return true; // 3. 返回true
|
||
}
|
||
|
||
template<class DT>
|
||
bool GetTail(SqQueue<DT> Q, DT& e) // 取队尾元素
|
||
{
|
||
if (Q.front == Q.rear) // 1. 队空的情况
|
||
return false; // 无队尾元素，返回false
|
||
e = Q.base[(Q.rear - 1 + Q.queuesize) % Q.queuesize]; // 2. 取队尾元素，赋值给e
|
||
return true; // 3. 返回true
|
||
}
|
||
|
||
template<class DT>
|
||
int QueueLength(SqQueue<DT> Q) // 测表长
|
||
{
|
||
return (Q.rear - Q.front + Q.queuesize) % Q.queuesize;
|
||
}
|
||
|
||
template<class DT>
|
||
bool QueueEmpty(SqQueue<DT> Q) // 判队空
|
||
{
|
||
return Q.front == Q.rear;
|
||
}
|
||
|
||
template<class DT>
|
||
bool QueueFull(SqQueue<DT> Q) // 判队满
|
||
{
|
||
return (Q.rear + 1) % Q.queuesize == Q.front;
|
||
}
|
||
|
||
template<class DT>
|
||
void ClearQueue(SqQueue<DT>& Q) // 清空队
|
||
{
|
||
Q.front = Q.rear = 0;
|
||
}
|
||
|
||
template<class DT>
|
||
void DispQueue(SqQueue<DT> Q) // 显示队
|
||
{
|
||
int i = Q.front;
|
||
while (i != Q.rear)
|
||
{
|
||
cout << Q.base[i] << " ";
|
||
i = (i + 1) % Q.queuesize;
|
||
}
|
||
cout << endl;
|
||
} |