PTA数据结构(C++版)——7-1 队列的实现及基本操作（链栈实现，无上限）
1.编译运行
2.题目：
给定一个初始为空的队列和一系列入队、出队操作，请编写程序输出每次出队的元素。队列的元素值均为整数。
- 输入格式：
输入第1行为1个正整数n，表示操作个数；接下来n行，每行表示一个操作，格式为1 d或0。1 d表示将整数d入队，0表示出队。n不超过20000。
- 输出格式：
按顺序输出每次出队的元素，每个元素一行。若某出队操作不合法（如在队列空时出队），则对该操作输出invalid。
- 输入样例:
在这里给出一组输入。例如：
7
1 1
1 2
0
0
0
1 3
0
- 输出样例:
1
2
invalid
3
3.代码块
考虑到动态，所以选择链式存储结构，链队
- 队列的链式存储结构
typedefstructQNode{ QElemTypedata; structQNode*next; }QNode,*QueuePtr; typedefstruct { QueuePtrfront; //队头指针 QueuePtrrear; //队尾指针 }LinkQueue;
- 链队的初始化
StatusInitQueue(LinkQueue&Q){ //生成新结点作为头结点，队头和队尾指针指向此结点 Q.front=Q.rear=newQNode; //头结点的指针域为空 Q.front->next=NULL; returnOk; }
- 链队的入队
StatusEnQueue(LinkQueue&Q,QElemTypee){ //插入元素e为Q的新的队尾元素//为入队元素分配结点空间，用指针P指向 QNode*p=newQNode; //新结点的数据域为e p->data=e; //将新结点插入到队尾 p->next=NULL; //修改队尾指针 Q.rear->next=p; Q.rear=p; returnOk; }
- 链队的出队
StatusDeQueue(LinkQueue&Q,QElemType&e){ //删除Q的队头元素，用e返回其值//若队列为空，则返回Error if(Q.front==Q.rear) returnError; //p指向队头元素 QNode*p=Q.front->next; //e保存队头元素的值 e=p->data; //修改头结点的指针域 Q.front->next=p->next; //最后一个元素被删，队尾指针指向头结点 if(Q.rear==p) Q.rear=Q.front; //释放原队头元素的空间 deletep; returnOk; }
- 取链队的头元素
SElemTypeGetHead(LinkQueueQ){ //返回Q的队头元素，不修改指针//队列非空 if(Q.front!=Q.rear){ //返回队头元素的值，队头指针不变 returnQ.front->next->data; } }
4.源码
#include<iostream>usingnamespacestd; typedefintQElemType; typedefintSElemType; typedefintStatus; #defineOk1#defineError0//队列的链式存储结构 typedefstructQNode{ QElemTypedata; structQNode*next; }QNode,*QueuePtr; typedefstruct { QueuePtrfront; //队头指针 QueuePtrrear; //队尾指针 }LinkQueue; //链队的初始化 StatusInitQueue(LinkQueue&Q){ //生成新结点作为头结点，队头和队尾指针指向此结点 Q.front=Q.rear=newQNode; //头结点的指针域为空 Q.front->next=NULL; returnOk; } //链队的入队StatusEnQueue(LinkQueue&Q,QElemTypee){ //插入元素e为Q的新的队尾元素//为入队元素分配结点空间，用指针P指向 QNode*p=newQNode; //新结点的数据域为e p->data=e; //将新结点插入到队尾 p->next=NULL; //修改队尾指针 Q.rear->next=p; Q.rear=p; returnOk; } //链队的出队StatusDeQueue(LinkQueue&Q,QElemType&e){ //删除Q的队头元素，用e返回其值//若队列为空，则返回Error if(Q.front==Q.rear) returnError; //p指向队头元素 QNode*p=Q.front->next; //e保存队头元素的值 e=p->data; //修改头结点的指针域 Q.front->next=p->next; //最后一个元素被删，队尾指针指向头结点 if(Q.rear==p) Q.rear=Q.front; //释放原队头元素的空间 deletep; returnOk; } //取链队的头元素SElemTypeGetHead(LinkQueueQ){ //返回Q的队头元素，不修改指针//队列非空 if(Q.front!=Q.rear){ //返回队头元素的值，队头指针不变 returnQ.front->next->data; } } intmain(){ QElemTypee; LinkQueueQ; InitQueue(Q); intn,b; cin>>n; while(n-->0){ cin>>b; if(b==1){ cin>>b; EnQueue(Q,b); } if(b==0){ if(Q.front==Q.rear) cout<<"invalid"<<endl; else{ DeQueue(Q,b); cout<<b<<endl; } } } return0; }
