数据结构与算法Javascript描述（二）队列

短命女 2022-08-21 02:12 236阅读 0赞

特点：先进先出

Queue类

<span style="white-space:pre">		</span>function Queue() {
    			this.dataSource = [];
    			this.enqueue = enqueue;
    			this.dequeue = dequeue;
    			this.front = front;
    			this.back = back;
    			this.empty = empty;
    			this.toString = toString;
    		}
    		function enqueue(element) {
    			this.dataSource.push(element);
    		}
    		function dequeue() {
    			return this.dataSource.shift();
    		}
    		function front() {
    			return this.dataSource[0];
    		}
    		function back() {
    			return this.dataSource[this.dataSource.length - 1];
    		}
    		function empty() {
    			if(this.dataSource.length === 0) {
    				return true;
    			}else {
    				return false;
    			}
    		}
    		function toString() {
    			var retStr = "",
    				i = 0,
    				len = this.dataSource.length;
    			while(i < len) {
    				retStr += this.dataSource[i] + "\n";
    				i++;
    			}
    			return retStr;
    		}

应用

1、基数排序

对于0~99 的数字，基数排序将数据集扫描两次。第一次按个位上的数字进行排序，第二次按十位上的数字进行排序。每个数字根据对应位上的数值被分在不同的盒子里。假设有如下数字：  
91, 46, 85, 15, 92, 35, 31, 22

经过基数排序第一次扫描之后，数字被分配到如下盒子中：

Bin 0:  
Bin 1: 91, 31  
Bin 2: 92, 22  
Bin 3:  
Bin 4:  
Bin 5: 85, 15, 35  
Bin 6: 46  
Bin 7:  
Bin 8:  
Bin 9:

根据盒子的顺序，对数字进行第一次排序的结果如下：

91, 31, 92, 22, 85, 15, 35, 46

然后根据十位上的数值再将上次排序的结果分配到不同的盒子中：

Bin 0:  
Bin 1: 15  
Bin 2: 22  
Bin 3: 31, 35  
Bin 4: 46  
Bin 5:  
Bin 6:  
Bin 7:  
Bin 8: 85  
Bin 9: 91, 92

最后，将盒子中的数字取出，组成一个新的列表，该列表即为排好序的数字：

15, 22, 31, 35, 46, 85, 91, 92

使用队列代表盒子，可以实现这个算法。我们需要九个队列，每个对应一个数字。将所有队列保存在一个数组中，使用取余和除法操作决定个位和十位。算法的剩余部分将数字加入相应的队列，根据个位数值对其重新排序，然后再根据十位上的数值进行排序，结果即为排好序的数字。

// 基数排序
    		function distribute(nums, queues, n ,digit) {//digit表示为1代表个位，10代表10位
    			var i;
    			for(i=0;i<n;i++) {
    				if(digit === 1) {
    					queues[nums[i]%10].enqueue(nums[i]);
    				}else {
    					queues[Math.floor(nums[i]/10)].enqueue(nums[i]);
    				}
    			}
    		}
    		function collect(queues,nums) {
    			var arr = [],i=0,j;
    			for(j=0;j<10;j++) {
    				while(!queues[j].empty()){
    					nums[i++] = queues[j].dequeue();
    				}
    			}
    		}
    		function disArr(nums) {
    			for(var i = 0;i<nums.length;i++) {
    				console.log(nums[i]+ ' ');
    			}
    			console.log("\n");
    		}
    		var queues = [];
    		for(var i=0;i<10;i++) {
    			queues[i] = new Queue();
    		}
    		var nums = [];
    		for(var i=0;i<10;i++) {
    			nums[i] = Math.floor(Math.random() * 101);
    		}
    		disArr(nums);
    		distribute(nums, queues, 10 ,1);
    		collect(queues,nums);
    		disArr(nums);
    		distribute(nums, queues, 10 ,10);
    		collect(queues,nums);
    		disArr(nums);