PTA——7-1 队列的实现及基本操作

ゞ浴缸里的玫瑰 2022-11-16 10:38 15阅读 0赞

给定一个初始为空的队列和一系列入队、出队操作，请编写程序输出每次出队的元素。队列的元素值均为整数。

# 输入格式 #

输入第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

# 代码示例 #

#include<iostream>
    using namespace std;
    typedef int QElemType;
    typedef int SElemType;
    typedef int Status;
    #define Ok 1
    #define Error 0 
    //队列的链式存储结构 
    typedef struct QNode{ 
    	QElemType data;
    	struct QNode *next;
    }QNode,*QueuePtr;
    
    typedef struct { 
    	QueuePtr front;	//队头指针 
    	QueuePtr rear;	//队尾指针 
    }LinkQueue;
    
     //链队的初始化 
    Status InitQueue(LinkQueue &Q){ 
    	//生成新结点作为头结点，队头和队尾指针指向此结点 
    	Q.front = Q.rear=new QNode;
    	//头结点的指针域为空 
    	Q.front->next = NULL;
    	return Ok;
    }
    
    //链队的入队
    Status EnQueue(LinkQueue &Q,QElemType e){ 
    	//插入元素e为Q的新的队尾元素
    	//为入队元素分配结点空间，用指针P指向 
    	QNode *p=new QNode;
    	//新结点的数据域为e 
    	p->data = e;
    	//将新结点插入到队尾 
    	p->next = NULL;
    	//修改队尾指针 
    	Q.rear->next = p;
    	Q.rear = p;
    	return Ok;
    } 
    
    //链队的出队
    Status DeQueue(LinkQueue &Q,QElemType &e){ 
    	//删除Q的队头元素，用e返回其值
    	//若队列为空，则返回Error 
    	if(Q.front==Q.rear) return Error;
    	//p指向队头元素 
    	QNode *p=Q.front->next;
    	//e保存队头元素的值 
    	e=p->data;
    	//修改头结点的指针域 
    	Q.front->next = p->next;
    	//最后一个元素被删，队尾指针指向头结点 
    	if(Q.rear == p) Q.rear =Q.front;
    	//释放原队头元素的空间 
    	delete p;
    	return Ok; 
    } 
    
    //取链队的头元素
    SElemType GetHead(LinkQueue Q){ 
    	//返回Q的队头元素，不修改指针
    	//队列非空 
    	if(Q.front!=Q.rear){ 
    		//返回队头元素的值，队头指针不变 
    		return Q.front->next->data;
    	} 
    } 
     int main(){ 
     	QElemType e;
     	LinkQueue Q; 
     	InitQueue(Q);
     	int n,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;
     			}			
     		}			
     	}
     	return 0;
     }