银行业务队列简单模拟（队列）

谁借莪１个温暖的怀抱￠ 2022-05-08 07:10 334阅读 0赞

# 7-1 银行业务队列简单模拟 （25 分） #

设某银行有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

# 解法： #

### 解法一： ###

// 第一种方法为一大佬所写，比较简洁/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* --银行业务队列简单模拟（队列的模拟）-- \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/  
/\*  
该方法并没有直接的使用队列，而是用两个数组来代表队列的两个指针，一个记录奇数，一个记录偶数  
id记录偶数什么时候输出，flag控制控制空格的输出，先第一个数，然后空格加数字。  
方法的确是挺简单的，看行数就能看出来。。  
\*/

#include <bits/stdc++.h>
    using namespace std;
    const int maxn = 1000 + 100;
    
    int a[maxn], b[maxn];
    int topA, botA, topB, botB;
    
    int main()
    {
        int n, x;
        scanf("%d", &n);
    
        topA = botA = topB = botB = 0;
    
        for (int i = 1; i <= n; i++)
            scanf("%d", &x), (x%2)? a[++topA] = x : b[++topB] = x;
    
        int id = 0, flag = 0;
        while(botA < topA || botB < topB)
        {
            if (botA < topA)
            {
                if (flag++) printf(" ");
                printf("%d", a[++botA]);
            }
            if (++id % 2 == 0 && botB < topB)
            {
                if (flag++) printf(" ");
                printf("%d", b[++botB]);
            }
        }
    
    }

### 解法二： ###

// 以下为个人所写，虽然有点复杂，但个人感觉比较好理解 \*  
/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* --银行业务队列简单模拟（队列）-- \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/  
/\* 首先，创建队列，将所有的数字都入队，再创建一个偶数队列，专门用来存储偶数；  
然后，遍历队列front->rear；并记录奇数的个数，每两个奇数输出后，再输出一个偶数；  
这样遍历结束，可能会有偶数多余，再判断偶数数列是否为空；如果不为空，则输出剩余的偶数；  
注意：空格的多余  
代码实现起来有点复杂，没有经过细细的改进  
\*/

#include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -2
    
    typedef int QElemType;
    typedef int Status;
    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 = (QueuePtr)malloc(sizeof(QNode));
        if(!Q.front) exit(OVERFLOW);
        Q.front->next = NULL;
        return OK;
    }
    Status DestroyQueue(LinkQueue &Q)
    {
        while(Q.front)
        {
            Q.rear =Q.front->next;
            free(Q.front);
            Q.front = Q.rear;
        }
        return OK;
    }
    Status EnQueue(LinkQueue &Q,QElemType e){
        QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
        if(!p) exit(OVERFLOW);
        p->data = e;
        p->next = NULL;
        Q.rear->next = p;
        Q.rear = p;
        return OK;
    }
    /*
    Status DeQueue(LinkQueue &Q)
    {
        if(Q.front == Q.rear) return ERROR;
        QueuePtr p = Q.front->next;
        //e = p->data;
        Q.front->next = p->next;
        if(Q.rear == p)Q.rear = Q.front;
        free(p);
        return OK;
    }
    */
    bool EmptyQueue(LinkQueue &Q)
    {
        return Q.front == Q.rear;
    }
    int main()
    {
        LinkQueue Q,Q_even;
        InitQueue(Q);
        InitQueue(Q_even);
        QueuePtr q = (QueuePtr)malloc(sizeof(QNode));
        if(!q) exit(OVERFLOW);
        q->next = NULL;
        int num,i,e1;
        int count,odd = 0,even = 0;
        scanf("%d",&count);
        for(i = 0; i < count; i++)
        {
            scanf("%d",&num);
            EnQueue(Q,num);
           // printf("%d\n",Q.front->next->data);
        }
        //printf("%d\n",Q.rear->data);
        q = Q.front->next;
        while(q)
        {
            //printf("q = %d\n",q->data);
            if(q->data % 2 == 0)
            {
                int e = q->data;
                EnQueue(Q_even,e);
                even++;
            }
            else
            {
                odd++;
                if(q != Q.rear || (q == Q.rear && !EmptyQueue(Q_even)))
                {
                if(odd % 2 == 0 && even)
                {
                    int e;
                    //if(Q_even.front->next)
                    printf("%d ",q->data);
                    printf("%d ",Q_even.front->next->data);
                    DeQueue(Q_even);
                    even--;
                }
                else
                printf("%d ",q->data);
                }
                if(q == Q.rear && EmptyQueue(Q_even))
                {
                if(odd % 2 == 0 && even)
                {
                    //if(Q_even.front->next)
                    printf("%d",q->data);
                    printf("%d",Q_even.front->next->data);
                    DeQueue(Q_even);
                    even--;
                }
                else
                printf("%d",q->data);
                }
            }
            q = q->next;
        }
            while(!EmptyQueue(Q_even))
            {
                if(Q_even.front->next != Q_even.rear)
                    printf("%d ",Q_even.front->next->data);
                else
                    printf("%d",Q_even.front->next->data);
                DeQueue(Q_even);
            }
        return 0;
    }