yuyu博客

循环队列

Word count: 1.4kReading time: 6 min
2022/05/02

循环队列

循环队列说明

逻辑上是首尾相连的数组，可是在数组中其实不存在这样的数组，所以在物理实现上是不存在的，那么我们需要怎么做呢？

其实对于不存在物理上实现的循环结构，我们可以用软件方法实现（采用求模方式）:

  • tail=（tail＋1）% MAXSIZE

  • head=(head+1) % MAZSIZE

出现了几个关于循环队列所必须解决的问题：

  1. 如何判断循环队列队为空？

队空：head == tail 跟之前一样。

  1. 如何判断循环队列队为满

队满：(tail+1) mod QueueSize==head

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

C++解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
const int queuesize=1000;//要加const 定义常数***

string vqueue[queuesize];
int vhead=0;
int vtail=0;

string nqueue[queuesize];
int nhead=0;
int ntail=0;

bool in(string name,string type){//进队
    if(type=="V"){
        if((vtail+1)%queuesize==vhead){//队列满了，循环，重点,数学
           return false; 
        }
        else{
            vqueue[vtail]=name;
            vtail++;
            return true;
        }
    }

    else{
        if((ntail+1)%queuesize==nhead){//队列满了，循环，重点
           return false; 
        }
        else{
            nqueue[ntail]=name;
            ntail++;
            return true;
        }
    }
}

bool out(string type){//出队判断
    if(type=="V"){
        if(vhead==vtail){//空队
            return false;
        }

        else{
            vhead=(vhead+1)%queuesize;//因为是循环队列，所以到数组末尾也要调到开头；普通队列为vhead=vhead+1;
            return true;
        }
    }

    else{
        if(nhead==ntail){
            return false;
        }

        else{
            nhead=(nhead+1)%queuesize;
            return true;
        }
    }
}

string gethead(string type){//输出队头
    if(type=="V"){
        if(vhead==vtail){
            return "";
        }
        else{
            return vqueue[vhead];  
        }
        
    }
    else{
        if(nhead==ntail){
            return "";
        }
        else{
            return nqueue[nhead];  
        }
    }
}

int main(){
    int M;
    cin>>M;

    while(M--){
        string op,name,type;
        cin>>op;
        if(op=="IN"){//java中用op.equals("IN")
            cin>>name>>type;
            in(name,type);
        }
        else{//出队头
            cin>>type;
            out(type);
        }
    }

    while(gethead("V")!=""){//也可以和普通队列一样，只要把gethead()中的if判断删除就可以
        cout<<gethead("V")<<endl;
        out("V");
    }

    while(gethead("N")!=""){
        cout<<gethead("N")<<endl;
        out("N");
    }
    return 0;
}

java解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
import java.util.Scanner;

public class Main {


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

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

   static boolean in(String name, String type) {

       if(type.contains("V")){
           if ((Vtail+1) % QueueSize ==Vhead) return false;
               //队列以达到容量上限满了，所以不能再插入了返回错误；
           else{
               Vtail=(Vtail+1) % QueueSize;
               Vqueue[Vtail]=name;
               return true;
           }
       }
       else
       {
           if ((Ntail+1) % QueueSize ==Nhead) return false;
               //队列以达到容量上限满了，所以不能再插入了返回错误；
           else{
               Ntail=(Ntail+1) % QueueSize;
               Nqueue[Ntail]=name;
               return true;
           }
       }
   }

   static boolean out(String type) {

       if(type.contains("V")){
           if (Vtail==Vhead) return false;
               //空队列不能出队列了

           else {
               Vhead=(Vhead+1) % QueueSize;
               //不是空队列，但是因为是循环的，如果到了数组末尾也要调整到前面去。
               return true;
           }

       }
       else
       {
           if (Ntail==Nhead) return false;
               //空队列不能出队列了

           else {
               Nhead=(Nhead+1) % QueueSize;
               //不是空队列，但是因为是循环的，如果到了数组末尾也要调整到前面去。
               return true;
           }

       }
   }

   static String getHead(String type) {

       if(type.contains("V")){
           if (Vtail==Vhead) return "";//空队列返回空
           else {
               return Vqueue[Vhead+1];
           }
       }
       else
       {
           if (Ntail==Nhead) return "";//空队列返回空
           else {
               return Nqueue[Nhead+1];
           }
       }
   }

   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解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
Vqueue = []
Nqueue = []

def inque(name, type):
  global Vqueue ,Nqueue
  if (type == 'V'):
      Vqueue.append(name)
  else:
      Nqueue.append(name)


def outque(type):
  global Vqueue ,Nqueue
  if (type == 'V'):

      if(len(Vqueue)==0):
          return None
      else:
          s=Vqueue[0]
          Vqueue.remove(Vqueue[0])
          return s

  else:
      if (len(Nqueue)==0):
          return None
      else:
          s = Nqueue[0]
          Nqueue.remove(Nqueue[0])
          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')

Author：yuyu

Link：http://example.com/2022/05/02/%E5%BE%AA%E7%8E%AF%E9%98%9F%E5%88%97/

Publish date：May 2nd 2022, 12:24:02 am

Update date：May 2nd 2022, 12:27:29 am

License：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 循环队列
    1. 1.1. 循环队列说明
    2. 1.2. CLZ 的银行普通队列
      1. 1.2.1. 问题描述
      2. 1.2.2. 输入描述
    3. 1.3. C++解法
    4. 1.4. java解法
    5. 1.5. Python解法
Total : 8
Invalid date
2022