JavaScript实现循环队列（非Array.prototype.pop和Array.prototype.shift）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了JavaScript实现循环队列（非Array.prototype.pop和Array.prototype.shift），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2571字，纯文字阅读大概需要4分钟。

内容图文

循环队列优点

重用浪费的内存

例: [1,2,3,4] -> deQueue -> [null, 2,3,4] -> deQueue -> [null,null,3,4]
优于数组已满,无法从队尾将新元素入队,因此用循环队列来重新利用被浪费的空间

功能

MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。
changeHeadPoint(): 移动头指针。
changeTailPoint(): 移动尾指针。

思路

一般来说,利用JavaScript实现队列可用Array.prototype.pop()和Array.prototype.shift()来实现入队和出队,但是为了表现循环队列的优点,即可以重复利用普通队列浪费的空间,此处定义一个空数组,并利用头指针和尾指针的移动来实现循环队列

代码

MyCircularQueue类

var MyCircularQueue = function(k) {
	this.queue = new Array(k)
	for(let i = 0;i < this.queue.length;i++) {
		this.queue[i] = null
	}
	this.head = -1
	this.tail = -1
};

MyCircularQueue.prototype.enQueue = function(value) {
	if (!this.isFull()) {
		// 改变尾指针后入队
		this.changeTailPoint()
		this.queue[this.tail] = value
		return true
	} else {
		return false
	}
};

MyCircularQueue.prototype.deQueue = function() {
	if (!this.isEmpty()) {
		// 出队后改变头指针
		this.queue[this.head] = null
		this.changeHeadPoint()
		return true
	} else {
		return false
	}

};

MyCircularQueue.prototype.Front = function() {
	if(!this.isEmpty()) {
		return this.queue[this.head]
	} else {
		return -1
	}
};

MyCircularQueue.prototype.Rear = function() {
	if(!this.isEmpty()) {
		return this.queue[this.tail]
	} else {
		return -1
	}
};

MyCircularQueue.prototype.isEmpty = function() {
	return this.head === -1 && this.tail === -1
};


MyCircularQueue.prototype.isFull = function() {
	return this.queue.indexOf(null) === -1

};

MyCircularQueue.prototype.changeHeadPoint = function() {
	// 是否剩下一个元素
	if(this.head === this.tail) {
		this.head = -1
		this.tail = -1
	} else {
		this.head++
		// 边界
		if(this.head === this.queue.length) {
			this.head = 0
		}
	}
}

MyCircularQueue.prototype.changeTailPoint = function() {
	// 空数组入队
	if(this.tail === -1 && this.head === -1) {
		this.tail++
		this.head++
	} else {
		this.tail++
		// 边界
		if(this.tail === this.queue.length) {
			this.tail = 0
		}
	}
}

MyCircularQueue.prototype.show = function() {
	console.log('queue: ', this.queue)
	console.log('front: ', this.head)
	console.log('rear: ', this.tail)
}

调试

let queue = new MyCircularQueue(6)
queue.enQueue(2)
queue.enQueue(2)
queue.enQueue(2)
queue.enQueue(2)
queue.enQueue(2)
queue.enQueue(2)
queue.deQueue()
queue.deQueue()
queue.enQueue(2)
queue.show()

调试结果:
queue: [ 2, null, 2, 2, 2, 2 ]
front: 2
rear: 0

内容总结

以上是互联网集市为您收集整理的JavaScript实现循环队列（非Array.prototype.pop和Array.prototype.shift）全部内容，希望文章能够帮你解决JavaScript实现循环队列（非Array.prototype.pop和Array.prototype.shift）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端