javascript数据结构4-队列

发表于 | 更新于 | 分类于

队列是一种先进先出（FIFO，first-in-first-out）的数据结构

javascript代码实现队列：

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
<!doctype html>
<html>
<head>
<meta charset=utf-8 /> 
	<title>Queue Sample</title>
</head>
<body>
      
   <script type="text/javascript">
   	    /*定义队列*/
   	    function Queue(){
   	    	this.dataStore=[];
   	    	this.enqueue=enqueue;
   	    	this.dequeue=dequeue;
          this.front=front;
          this.back=back;
          this.toStr=toStr;
          this.isEmpty=isEmpty;
   	    }
     
     function enqueue(element){
         this.dataStore.push(element);
     }
     
     function dequeue(){
        return this.dataStore.shift();
     }
     
     function front(){
     	return this.dataStore[0];
     }
     
     function back(){
     	return this.dataStore[this.dataStore.length-1];
     }
     
     function toStr(){
      	var retStr="";
        for(var i=0;i<this.dataStore.length;i++){
        	retStr+=this.dataStore[i]+"\n";
        }
        //console.log(retStr);
         return retStr;
     }
     //判断是否为空
     function isEmpty(){
      	  if(this.dataStore.length==0){
          		return true;
          	}else{
           		return false;   
           	}
     }
     var que=new Queue();
     que.enqueue("Tom");
     que.enqueue("Sam");
     que.enqueue("Pom");
     console.log(que.dataStore.length);
     document.write(que.toStr());
     que.dequeue();
     document.write(que.toStr());
    console.log(que.toStr);

	</script>
  </body>
</html>

举个案例：
常用队列模拟排队的人。下面我们使用队列来模拟跳方块舞的人。
当男男女女来到舞池，他们按照自己的性别排成两队。当舞池中有地方空出来时，选两个队列中的第一个人组成舞伴。他们身后的人各自向前移动一位，变成新的队首。当一对舞伴迈入舞池时，主持人会大声喊出他们的名字。当一对舞伴走出舞池，且两排队伍中有任意一队没人时，主持人也会把这个情况告诉大家。

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
<!doctype html>
<html>
<head>
<meta charset=utf-8 /> 
	<title>Queue Sample</title>
</head>
<body>
      
   <script type="text/javascript">
   	    /*定义队列*/
   	    function Queue(){
   	    	this.dataStore=[];
   	    	this.enqueue=enqueue;
   	    	this.dequeue=dequeue;
          this.front=front;
          this.back=back;
          this.toStr=toStr;
          this.isEmpty=isEmpty;
   	    }
     
     function enqueue(element){
         this.dataStore.push(element);
     }
     
     function dequeue(){
        return this.dataStore.shift();
     }
     
     function front(){
     	return this.dataStore[0];
     }
     
     function back(){
     	return this.dataStore[this.dataStore.length-1];
     }
     
     function toStr(){
      	var retStr="";
        for(var i=0;i<this.dataStore.length;i++){
        	retStr+=this.dataStore[i]+"\n";
        }
        //console.log(retStr);
         return retStr;
     }
     //判断是否为空
     function isEmpty(){
      	  if(this.dataStore.length==0){
          		return true;
          	}else{
           		return false;   
           	}
     }
    
      //舞蹈员性别  姓名
    var  allStr="F Shun F Tim M Huipin M Lanlan F Ping F Li F Lou M Funr F Sun M Pop";  
     
      function Dancer(name,sex){
      	this.name=name;
        this.sex=sex;
      }
     
     //男女分队
     function getDancers(males,females){
          var numbers=allStr.split(" ");
         //document.write(numbers);
          //console.log(numbers);
          for(var i=0;i<numbers.length-1;++i){
             //var dances=numbers[i].trim();
             var sex=numbers[i];
             i++;
             var name=numbers[i]; 
            //console.log(name);
            //console.log(sex);
            if(sex == "F"){  //??????
            	 famaleDances.enqueue(new Dancer(name,sex));
                 console.log(famaleDances);
            }else{
            	 maleDances.enqueue(new Dancer(name,sex));//整体对象存在队列中
            }
         }
     } 
       //队首男女就是要出队的
       function dance(males,famales){
       		document.write("The dance parter are: ");
            document.write("<br />");
            while(!males.isEmpty() && !famales.isEmpty()){
                fperson=famales.dequeue();
               // console.log(fperson);
                document.write("The Famale dance  is:"+fperson.name);               
                person=males.dequeue();
                document.write(" and The Male dance  is:"+person.name);
              	document.write("<br />");
            }
       } 
      var maleDances=new Queue();
      var famaleDances=new Queue();
         // document.write("1");
      getDancers(maleDances,famaleDances);
      dance(maleDances,famaleDances);
     
       if(!famaleDances.isEmpty()){
          document.write(famaleDances.front().name+"is waiting");
       }
       
       if(!maleDances.isEmpty()){
          document.write(maleDances.front().name+"is waiting");
       }
   </script>
</body>
</html>