队列

Word count: 1.1kReading time: 5 min

 2022/05/02 

队列

CLZ 的银行普通队列

问题描述

CLZ 银行只有两个接待窗口，VIPVIP 窗口和普通窗口，VIPVIP 用户进入 VIPVIP 窗口排队，剩下的进入普通窗口排队。现有 MM 次操作，操作有四种类型，如下：

IN name V：表示一名叫 name 的用户到 VIPVIP 窗口排队
OUT V：表示 VIPVIP 窗口队头的用户离开排队
IN name N：表示一名叫 name 的用户到普通窗口排队
OUT N：表示普通窗口队头的用户离开排队
求 MM 次操作结束后 VIPVIP 窗口队列和普通窗口队列中的姓名。

输入描述

第一行是一个整数 M（1\leq M \leq 1000）M（1≤M≤1000），表示一共有 MM 次操作。

第二行到第 M+1M+1 行输入操作，格式如下：

IN name V
OUT V
IN name N
OUT N

输出描述

输出 MM 次操作后 VIPVIP 窗口队列和普通窗口队列中的姓名（从头到尾），先输出 VIPVIP 窗口队列后输出普通窗口队列。

C++解法

string Vqueue[1000];//创建队列
int vhead=0;//队头
int vtail=0;//队尾

string Nqueue[1000];
int nhead=0;
int ntail=0;

void in(string name,string type){//进队
    if(type=="V"){
        Vqueue[vtail]=name;//进队
        vtail++;//队尾后移
    }
    else{
        Nqueue[ntail]=name;
        ntail++;
    }
}

bool out(string type){//布尔类型
    if(type=="V"){
        if(vhead==vtail){//判断是否为空队列
            return false;
        }
        else{
            vhead++;
            return true;
        }
    }

    else{
        if(nhead==ntail){//相同为"=="
            return false;
        }
        else{
            nhead++;
            return true;
        }
    }
}

string gethead(string type){//从队头开始出列
    if(type=="V"){
       return Vqueue[vhead];
    }

    else{
        return Nqueue[nhead];
    }
}

int main(){
    int M;
    cin>>M;
    for(int i=1;i<=M;i++){//也可以写成while(M--),只要循环M次
        string op,name,type;
        cin>>op;
        if(op=="IN"){
            cin>>name>>type;
            in(name,type);
        }
        else{
           cin>>type;
           out(type);
        }
    }
    string s=gethead("V");
    while(out("V")){
        cout<<s<<endl;
        s=gethead("V");
    }
    s=gethead("N");//注意加";"
    while(out("N")){
        cout<<s<<endl;
        s=gethead("N");
    }
    return 0;
}

java解法

import java.util.Scanner;

public class Main {

  static String Vqueue[] = new String[1000]; // V队列
  static int Vhead = 0; // 首指针
  static int Vtail = 0; // 尾指针

  static String Nqueue[] = new String[1000]; // N队列
  static int Nhead = 0; // 首指针
  static int Ntail = 0; // 尾指针

  static void in(String name, String type) {
      if (type.contains( "V")) {
          Vqueue[Vtail] = name;
          Vtail++;
      } else {
          Nqueue[Ntail] = name;
          Ntail++;
      }
  }

  static boolean out(String type) {

      if (type.contains( "V")) {
          if (Vhead == Vtail) {
              // 队伍没有人不能在出队了。
              return false;
          } else {
              Vhead++;// head前的数据都是无效数据，无需删除，逻辑明确即可。
              return true;
          }

      } else {
          if (Nhead == Ntail) {
              // 队伍没有人不能在出队了。
              return false;
          } else {
              Nhead++;// head前的数据都是无效数据，无需删除，逻辑明确即可。
              return true;
          }
      }
  }

  static String getHead(String type) {

      if (type.contains( "V")) {
          return Vqueue[Vhead];
      } else {
          return Nqueue[Nhead];
      }
  }

  public static void main(String[] args) {
      int M;
      Scanner in=new Scanner(System.in);
      M=in.nextInt();
      while(M>0) //
      {
          M--;
          String op,name,type;
          op=in.next();
          // System.out.println("op"+op);
          if(op.contains("IN"))
          {
              name=in.next();
              type=in.next();
              in(name,type);
              // System.out.println("name:"+name+"type:"+type);

              // System.out.println(Vqueue);
          }
          else
          {
              type=in.next();
              out(type);
              // System.out.println("type"+type);
          }
      }
      // System.out.println(Nhead);
      String s=getHead("V");
      while(out("V"))
      {
          System.out.println(s);
          s=getHead("V");
      }
      s=getHead("N");
      while(out("N"))
      {
          System.out.println(s);
          s=getHead("N");
      }
  }

}

Python解法

Vqueue = []
Vhead = 0
Vtail = 0
Nqueue = []
Nhead = 0
Ntail = 0


def inque(name, type):
  global Vhead, Vtail, Nhead, Ntail,Vqueue ,Nqueue
  if (type == 'V'):
      Vqueue.append(name)
      Vtail += 1
  else:
      Nqueue.append(name)
      Ntail += 1
      # print(Vqueue)

def getHead(type):
  global Vhead, Vtail, Nhead, Ntail,Vqueue ,Nqueue

  if (type == 'V'):
      # print(Vhead)
      return Vqueue[Vhead]
  else:
      # print(Nhead)
      return Nqueue[Nhead]

def outque(type):
  global Vhead, Vtail, Nhead, Ntail,Vqueue ,Nqueue
  if (type == 'V'):

      if (Vhead == Vtail):
          return None
      else:

          s = getHead(type)
          Vhead += 1
          return s

  else:

      if (Nhead == Ntail):
          return None
      else:
          s= getHead(type)
          Nhead += 1
          return  s


if __name__ == '__main__':

  M = 0
  M = int(input())
  while M > 0:
      M -= 1
      op = input().split()

      # print(op[0])

      if op[0] == 'IN':


          inque(op[1], op[2])
          # print('in')
      else:

          outque(op[1])
          # print('out')
      # print("VVVVV",Vqueue)
      # print("NNNN",Nqueue)
      # print(M)

  s = outque('V')
  while s!=None:
      print(s)
      s = outque('V')

  s = outque('N')
  while s != None:
      print(s)
      s = outque('N')