银行业务队列简单模拟

骑猪看日落 2022-02-27 16:14 686阅读 0赞

## PTA 03：银行业务队列简单模拟  ##

#### 一、题目 ####

设某银行有A、B两个业务窗口，且处理业务的速度不一样，其中A窗口处理速度是B窗口的2倍 —— 即当A窗口每处理完2个顾客时，B窗口处理完1个顾客。给定到达银行的顾客序列，请按业务完成的顺序输出顾客序列。假定不考虑顾客先后到达的时间间隔，并且当不同窗口同时处理完2个顾客时，A窗口顾客优先输出。

输入格式:  
输入为一行正整数，其中第1个数字N(≤1000)为顾客总数，后面跟着N位顾客的编号。编号为奇数的顾客需要到A窗口办理业务，为偶数的顾客则去B窗口。数字间以空格分隔。

输出格式:  
按业务处理完成的顺序输出顾客的编号。数字间以空格分隔，但最后一个编号后不能有多余的空格。

输入样例:  
8 2 1 3 9 4 11 13 15  
输出样例:  
1 3 2 9 11 4 13 15

--------------------

#### 二、代码 ####

<table> 
 <tbody> 
  <tr> 
   <td><font>1、循环队列（队列的顺序表示）</font></td> 
  </tr> 
 </tbody> 
</table>

#include<iostream>
    using namespace std;
    #define MAXSIZE 1000
    #define ERROR -2
    #define OK 0
    typedef int Qelemtype;
    typedef struct
    {
        
    	Qelemtype elem[MAXSIZE];
    	int front;
    	int rear;
     }SqQueue;
      void InitQueue(SqQueue &Q)
      {
        //初始化队列 
      	Q.front=0;
      	Q.rear=0;
       }
       int EnQueue(SqQueue &Q,Qelemtype &e)
      {
         //入队 
    		if((Q.rear+1)%MAXSIZE==Q.front) return ERROR;
    	    Q.elem[Q.rear]=e;
    	    Q.rear=(Q.rear+1)%MAXSIZE;
    	    return OK;
       }                               
      int DeQueue(SqQueue &Q,Qelemtype &e )
      {
         //出队 
      	if(Q.front==Q.rear)  return ERROR;  
         e=Q.elem[Q.front];
         Q.front=(Q.front+1)%MAXSIZE;
         return OK;
       } 
       void Print(int arr[],int n)
        {
        
        cout<<arr[0];
        for(int i=1;i<n;i++)
            cout<<" "<<arr[i];
        }
       int main()
      {
         int e; 
      	SqQueue A,B;
        InitQueue(A);//初始化两个队列 
        InitQueue(B);
       	int n,number,i=0;
    	   cin >> n;
    	int result[n]; 
      	for(int i=0;i<n;i++)
      	{
         //分别将奇数的值入A，偶数的值入B； 
      		cin>>number;
      		if(number%2!=0)
      		   EnQueue(A,number);
            else
               EnQueue(B,number);
      		    
    	  }
     
    		while((A.front!=A.rear)&&(B.front!=B.rear))
        {
        
            DeQueue(A,e);
            result[i++]=e;
            DeQueue(A,e);
            result[i++]=e;
            DeQueue(B,e);
            result[i++]=e;
        }
        while(A.front!=A.rear)
        {
        
            DeQueue(A,e);
            result[i++]=e;
        }
        while(B.front!=B.rear)
        {
        
            DeQueue(B,e);
            result[i++]=e;
        }
        Print(result,n);
    }

#include<iostream>
    using namespace std;
    #define ERROR 1
    typedef int QElemType;
    typedef struct QNode{
        
    	QElemType data;
    	struct QNode *next;
    }QNode , *QueuePtr;
    
    typedef struct {
        
    	QueuePtr front;
    //	队头指针 
    	QueuePtr rear;
    //	队尾指针 
    }LinkQueue; 
    
    //初始化函数：构造一个空队列 
    void InitQueue(LinkQueue &Q){
        
    	Q.front = Q.rear = new QNode;
    	Q.front->next = NULL; 
    }
    
    //入队函数 
    void EnQueue(LinkQueue &Q , QElemType e ){
        
    	QueuePtr p;
    	p = new QNode;
    	p->data = e;
    	p->next = NULL;
    	Q.rear->next = p;
    //	将新结点插入到队尾
        Q.rear = p;
    //	修改队尾指针
    }
    
    //出队函数 
    int DeQueue(LinkQueue &Q , QElemType &e ){
        
    	QueuePtr p;
    	if(Q.front == Q.rear)
    	{
        
    		return ERROR;
    	}
    	p = Q.front->next;
    	e = p->data;
        
    	
    //	题目要求了最后一个元素后面不能带有空格，但是为什么不在这里直接讨论并输出？
    //  因为如果在这里分情况，程序会在队列A和队列B中分别进行判断，造成混乱 
    	Q.front->next = p->next;
    //	修改头结点的指针域
        if(Q.rear == p){
        
        	Q.rear = Q.front;
    	} 
    	delete p;
    //	释放原队头元素的空间
    } 
    
    void print(int c[], int n){
        
    	cout<<c[0];
        for(int i=1;i<n;i++)
        cout<<" "<<c[i];
    }
    
    int main(){
        
    	int a[1000] , n;
    	int j = 0;
    	QElemType e;
    	cin>>n;
    	int c[n];
    //	一定要注意！！这里的c[n]要摆放在输入n值之后 
    	
    //	输入n个顾客的编号 
    	for(int i=0 ; i<n ; i++){
        
    		cin>>a[i];
    	}
    	
    //	定义A、B两条链队并进行初始化 
        LinkQueue A , B;
    	InitQueue(A);
    	InitQueue(B);
    	
    //	分别将编号为奇、偶的顾客分配到A、B两条队列中 
        int i = 0 ;
        while(i<n){
        
        	e = a[i];
        	if(e % 2 != 0){
        
        		EnQueue(A , e);
    		}
    		else{
        
    		    EnQueue(B , e);
    		}
    		i++;
    	}
    	
    //	分别将A、B两队列的元素按要求进行输出
        while( A.rear != A.front && B.rear != B.front){
        
        	DeQueue(A , e );
            c[j++] = e;
        	DeQueue(A , e );
        	c[j++] = e;
        	DeQueue(B , e );
        	c[j++] = e;
    	}
    	
    		while( A.rear != A.front){
        
    		DeQueue(A , e );
    		c[j++] = e;
    		}
    	
    
    		while( B.rear != B.front){
        
    		DeQueue(B , e );
    		c[j++] = e;
    		}
        print(c,n);
    	return 0;
    	}

--------------------

#### 三、经验总结 ####

对于这一题我的思路是先让编号分别为奇数和偶数的顾客入好队，奇数入A，偶数入B，按照题目的要求A队每入完2人，B队入1人，但需要考虑好A窗口人多和B窗口人多的特殊情况怎么处理。  
这题有一个需要注意的点，由于题目对格式又有要求，即最后一个元素后面不带空格，可是如果我们放在出队函数里面进行判断输出就会出现混乱，如下所示：![在这里插入图片描述][20190328092940565.PNG]  
为什么中间某一个元素后面会没有空格？因为你出队是分别从A、B两个队出的，其中一个队到达最后一个元素后面就没有括号了，但这种情况可能不是整个输出的最后一个元素  
为此我想的办法是，让出队的元素再进入一个数组，然后我把数组里面的元素进行输出。  
我还犯了一个错误，当时明明样例也通过了，但PTA上确是这样的结果，让人很绝望：![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lva29fdGFkemlv_size_16_color_FFFFFF_t_70]  
我的朋友检查了又检查之后发现，错就错在我的存储出队元素的数组c\[n\]的定义应该放在输入n值之后……  
这也提醒大家一定要仔细呀！我也是，嘿嘿，加油！

[20190328092940565.PNG]: /images/20220227/af2d50bc00334286aec4cbfbb3d14b41.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lva29fdGFkemlv_size_16_color_FFFFFF_t_70]: /images/20220227/d9ea9eff95b748a3aa97ed168523e46c.png