●图示（以顺序队列为例）
●队列类型定义
●顺序队列
1.顺序队列存储结构的定义
typedef struct { qelemtype* base; int front; //头指针 int rear; //尾指针 }SqQueue;
实例如下：
typedef struct { string name; }qelemtype; typedef struct { qelemtype* base; int front; int rear; }SqQueue;
●链式队列
1.链式队列存储结构的定义
typedef struct Qnode { QElemType data; //数据域 struct Qnode* next; //指向下一结点的指针域 }Qnode, * QueneP; typedef struct { QueneP front; //头指针 QueneP rear; //尾指针 }LinkQueue;
实例如下：
typedef struct { string name; }QElemType; typedef struct Qnode { QElemType data; //数据域 struct Qnode* next; //指向下一结点的指针域 }Qnode, * QueneP; typedef struct { QueneP front; //头指针 QueneP rear; //尾指针 }LinkQueue;
●常用的基本操作
●顺序队列
1.队列的初始化
void Initqueue(SqQueue& Q) { Q.base = new qelemtype[MAXQSIZE]; if (!Q.base) exit; Q.front = Q.rear = 0; }
2. 求队列的长度
int QueueLength(SqQueue& Q) { return ((Q.rear - Q.front + MAXQSIZE) % MAXQSIZE); }
3. 队列入队
int EnQueue(SqQueue& Q, qelemtype e) { if ((Q.rear + 1) % MAXQSIZE == Q.front) { return 0; //判断队满 } Q.base[Q.rear] = e; //新元素加入队尾 Q.rear = (Q.rear + 1) % MAXQSIZE;//队尾指针加1 return 1; }
4. 队列出队
int DeQueue(SqQueue& Q, qelemtype& e) { if (Q.front == Q.rear) { return 0; //判断队空 } e = Q.base[Q.front]; //保存队头元素 Q.front = (Q.front + 1) % MAXQSIZE; //队头指针加1 return 1; }
5. 取队头元素
qelemtype GetHead(SqQueue &Q) { if (Q.front != Q.rear) return Q.base[Q.front]; }
6.清空队列
void clearQueue(SqQueue& Q) { Q.front = 0; Q.rear = 0; }
●链式队列
1.链队列初始化
int InitQueue(LinkQueue& Q) { Q.front = Q.rear = new Qnode; if (!Q.front) { exit(0); } Q.front->next = NULL; return 1; }
2. 链队列入队
int EnQueue(LinkQueue& Q, QElemType e) { Qnode* p; p = new Qnode; if (!p) exit(OVERFLOW); p->data = e; p->next = NULL; Q.rear->next = p; Q.rear = p; return 1; }
3. 链队列出队
int DeQueue(LinkQueue& Q, QElemType e) { Qnode* p; if (Q.front == Q.rear) { return 0; } p = Q.front->next; e = p->data; Q.front->next = p->next; if (Q.rear == p) Q.rear = Q.front; delete p; return 1; }
4.求链队列的队头元素
void GetHead(LinkQueue Q) { QElemType e; e = Q.front->next->data; cout << e.name << endl; }
●简单案例
1.顺序队列（这里实现用顺序队列依次入队5个学生，并查看此时队列人数，在进行出队操作，再查看此时队列人数。若进行其他操作，对代码进行简单修改即可）
#include<iostream> #include<string> #define MAXQSIZE 100 using namespace std; //数据准备 typedef struct { string name; }qelemtype; typedef struct { qelemtype* base; int front; int rear; }SqQueue; //队列的初始化 void Initqueue(SqQueue& Q) { Q.base = new qelemtype[MAXQSIZE]; if (!Q.base) exit; Q.front = Q.rear = 0; } //求队列的长度 int QueueLength(SqQueue& Q) { return ((Q.rear - Q.front + MAXQSIZE) % MAXQSIZE); } //队列入队 int EnQueue(SqQueue& Q, qelemtype e) { if ((Q.rear + 1) % MAXQSIZE == Q.front) { return 0; //判断队满 } Q.base[Q.rear] = e; //新元素加入队尾 Q.rear = (Q.rear + 1) % MAXQSIZE;//队尾指针加1 return 1; } //队列出队 int DeQueue(SqQueue& Q, qelemtype& e) { if (Q.front == Q.rear) { return 0; //判断队空 } e = Q.base[Q.front]; //保存队头元素 Q.front = (Q.front + 1) % MAXQSIZE; //队头指针加1 return 1; } //取队头元素 qelemtype GetHead(SqQueue &Q) { if (Q.front != Q.rear) return Q.base[Q.front]; } //清空队列 void clearQueue(SqQueue& Q) { Q.front = 0; Q.rear = 0; } void showfunc() { cout << "1.队列的初始化" << endl; cout << "2.求队列的长度" << endl; cout << "3.队列入队" << endl; cout << "4.队列出队" << endl; cout << "5.取队头元素" << endl; cout << "6.清空队列" << endl; } void text() { SqQueue Q; qelemtype q; while (1) { showfunc(); cout << "#要执行的操作#" << endl; int n; cin >> n; switch (n) { case 1: Initqueue(Q); cout << "初始化成功" << endl; break; case 2: int len; len=QueueLength(Q); cout << "此时队列长度为" << len << endl; break; case 3: cout << "请输入要入队的学生人数" << endl; int num; cin >> num; for (int i = 1; i <= num; i++) { cin >> q.name; EnQueue(Q, q); } cout << "入队成功" << endl; break; case 4: DeQueue(Q, q); cout << "出队成功" << endl; break; } system("pause"); system("cls"); } } int main() { text(); }
2.链式队列 （这里实现用链式队列依次入队5个学生，并查看此时队头；进行二次出队操作后，再查看此时队头；若进行其他操作，对代码进行简单修改即可）
#include<iostream> #include<string> #define maxqsize 100 using namespace std; //数据准备 typedef struct { string name; }QElemType; typedef struct Qnode { QElemType data; //数据域 struct Qnode* next; //指向下一结点的指针域 }Qnode, * QueneP; typedef struct { QueneP front; //头指针 QueneP rear; //尾指针 }LinkQueue; //链队列初始化s int InitQueue(LinkQueue& Q) { Q.front = Q.rear = new Qnode; if (!Q.front) { exit(0); } Q.front->next = NULL; return 1; } //链队列入队 int EnQueue(LinkQueue& Q, QElemType e) { Qnode* p; p = new Qnode; if (!p) exit(OVERFLOW); p->data = e; p->next = NULL; Q.rear->next = p; Q.rear = p; return 1; } //链队列出队 int DeQueue(LinkQueue& Q, QElemType e) { Qnode* p; if (Q.front == Q.rear) { return 0; } p = Q.front->next; e = p->data; Q.front->next = p->next; if (Q.rear == p) Q.rear = Q.front; delete p; return 1; } //求链队列的队头元素 void GetHead(LinkQueue Q) { QElemType e; e = Q.front->next->data; cout << e.name << endl; } void text() { LinkQueue Q; QElemType d; InitQueue(Q); cout << "#初始化成功#" << endl; cout << "请输入入队人数:" << endl; int num; cin >> num; for (int i = 1; i <= num; i++) { cin >> d.name; EnQueue(Q,d); } cout << "#入队成功#" << endl; cout << "此刻队头元素为:" << endl; GetHead(Q); DeQueue(Q, d); cout << "#出队成功#" << endl; cout << "此刻队头元素为:" << endl; GetHead(Q); DeQueue(Q, d); cout << "#出队成功#" << endl; cout << "此刻队头元素为:" << endl; GetHead(Q); } int main() { text(); }
