注意:
- 队首指针 Q.front 指向的不是第一个数据元素结点 Q.front->next 才是。
- 队尾指针 Q.rear 始终指向最后一个结点。
- Q.length 始终是当前队列的长度
#include <iostream>
using namespace std;
typedef struct QNode{
int data;
struct QNode *next;
} QNode, *QNodePtr;
typedef struct{
QNodePtr front; // 队首指针
QNodePtr rear; // 队尾指针
int length;
} LinkQueue;
bool QueueInit(LinkQueue &Q)
{
Q.front = Q.rear = new QNode; // 生成新节点作为头结点, 队首和队尾指针指向它
Q.rear->next = NULL; // 头结点的指针域置为空
Q.length = 0; // 初始长度为0
return true;
}
bool QueuePush(LinkQueue &Q, int e) // 插入元素e为Q的新队尾元素
{
QNodePtr p = new QNode; // 先申请节点
p->data = e; // 设置数据域
p->next = NULL; // 指针域
Q.rear->next = p; // 新节点插入到队尾
Q.rear = p; // 修改队尾指针
Q.length ++; // 长度加一
return true;
}
bool QueuePop(LinkQueue &Q)
{
if(Q.front == Q.rear)
return false; // 队空,不能删除
QNodePtr p = Q.front->next; // 临时指针指向队首结点
Q.front->next = p->next; // 队首指针指向首节点的下一个节点
if(p == Q.rear) // 如果最后一个结点被删
Q.rear = Q.front; //
delete p;
Q.length --; // 长度减一
return true;
}
int QueueTop(const LinkQueue &Q)
{
if(Q.front == Q.rear)
{
cout << "Error" << endl;
return 0;
}
return Q.front->next->data;
}
int QueueSize(const LinkQueue &Q)
{
return Q.length;
}
int main()
{
LinkQueue Q;
QueueInit(Q);
QueuePush(Q, 1);
QueuePush(Q, 2);
QueuePush(Q, 3);
cout << QueueTop(Q) << endl;
cout << QueueSize(Q) << endl;
QueuePop(Q);
cout << QueueTop(Q) << endl;
cout << QueueSize(Q) << endl;
return 0;
}