利用链式队列（带头节点）解决银行业务队列简单模拟问题（c++）-- 数据结构...

我就是我 2021-12-14 09:11 349阅读 0赞

题目：

7-1 银行业务队列简单模拟 （30 分)

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

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

分析：
    
    经详读题目及例题可知，银行业务队列简单模拟问题可以简单看作 a和b 两个队列的问题：每当a队列输出两个元素后，b队列输出一个元素。

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

代码：

#include<iostream>
    #include <malloc.h> 
    #include<string>
    using namespace std;
    
    typedef int datatype; 
    
    
    //定义结点 
    typedef struct Q_node{
        datatype data;
        struct Q_node *next;
    }node;
    
    
    //定义队列的链表结构 
    typedef struct queue{
        node *front;//定义队首与队尾指针 
        node *rear;
    }queue;
    
    
    //初始化队列
    void initial(queue *qu)
    {
        qu->front = new node;//申请一个结点作为头节点 
        qu->front->next = NULL;
        qu->rear = qu->front;
    }
    
    
    //判断队列是否为空
    //0为空，1为非空 
    int empty(queue *qu)
    {
        if(qu->front == qu->rear){
            return 0;
        }else return 1; 
    }
    
    
    //删除链式队列中的结点 
    void dele(queue *qu, datatype *x)
    {
        if(empty(qu) == 0){
            //cout<<"队列为空！"<<endl; 
            return;
        }else{
            node *p = qu->front->next;
            qu->front->next = p->next;
            
            if(qu->rear == p){
           //除头节点外只有一个结点的情况 
                qu->rear = qu->front;//表示空链式队列 
            } 
            
            *x = p->data;
            free(p);//释放空间 
            p = NULL;    
        }
    }
     
     
     
    //输出链式队列中结点的值
    void display(queue *qu, int &flag)
    {
        datatype x;
        if(empty(qu) == 0){
          //  cout<<"The queue is empty!";
            flag = 0; //当队列为空时,状态flag=0； 
            return;
        }else{
            dele(qu, &x);//输出的值x由dele(queue *qu, datatype *x)函数返回
            flag = 1; 
            cout<<x;
            
        }
        
    } 
     
     
    //向链式队列中插入一个值为x的结点
    void enter(queue *qu, datatype x)
    {
        
        node *pNew;
        pNew = new node;
        if(pNew == NULL){
            cout<<"new pNew fail";
        }
        pNew->data = x; 
        pNew->next = NULL;
        qu->rear->next = pNew; 
        qu->rear = pNew; 
    } 
     
     
     
    int main(){
        int flag = 1;//用flag来标志元素出队时是否成功 
        int count=0;
        queue a,b;//定义队列a,b 
        initial(&a);//初始化队列a,b 
        initial(&b);
    
        int i,n,x;
        cin>>n;//输入个数 
        for(i=0; i<n; i++){
            cin>>x;
            if(x%2 == 0){
           //若x为偶数，入b队 
                enter(&b, x);
            }else enter(&a, x);//若x为奇数，入a队 
        }    
        
     /*每次display队列a或b中的元素后，判断队列 a或b是否为空
     若 a队列为空则直接display b队列，反之亦然 
     */   
        for(i=0; i<n;){
        
            if(empty(&a) == 0){
           //a队列为空
               while(empty(&b) != 0){
               i++; 
               display(&b, flag);
               if(b.front != b.rear)cout<<" ";
               }
            }else if(empty(&b) == 0){
           //b队列为空
               while(empty(&a) != 0){ 
               i++;
               display(&a, flag);
               if(a.front != a.rear)cout<<" ";
               }
            }
            
            if(count <= 1){
                display(&a, flag);
                if(flag == 1){
                  cout<<" ";
                  i++;    
                  count++;
                }    
            }else{
                display(&b, flag);
                if(flag == 1){
                  cout<<" ";
                  i++;    
                  count = 0;
                }
            }
            
            
        }
        
        return 0;    
    }

` `

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

编程中遇到的困难：
    
    1. 输出元素后判断是否需要输出空格的情况比较复杂：
           （1）当a队列空而b队列非空，b队列输出最后一个元素后，不输出空格
           （2）当a队列空而b队列非空，b队列输出最后一个元素后，不输出空格
           （3）当没有成功display时，不输出空格
       解决方法：定义一个flag变量，输出空格时flag = 1，不输出时flag = 0。通过flag值判断是否输出空格。
    
    
    2. a队列和b队列中元素个数的不同而导致多种情况（复杂算法可能造成运行超时）：
          （1） 仅有a队列中有元素
          （2） 仅有b队列中有元素
          （3） a队列中元素比b队列中元素多（即输入样例）
          （4） a队列中元素比b队列中元素少（该种情况需特别留意）
       解决方法：多方面考虑，找到一个通用的较好算法。

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

总结：
    
    1. 在入门者初学中，学习由链表搭建的数据结构都比较困难，但是学习的过程总需要走出安逸圈，选择一个不熟悉的知识点不断巩固，才能有效地为日后学习打下基础。
    
    2. 一个看似简单的问题（尤其是实际问题），往往有多种需要注意和考虑的情况

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

参考资料：
    https://blog.csdn.net/minamiximawa/article/details/81559066

转载于:https://www.cnblogs.com/yi2105/p/10618323.html