[Algorithms] Queue & Priority Queue
In this lesson, you will learn how to create a queue in JavaScript. A queue is a first-in, first-out data structure (FIFO). We can only remove items from the queue one at a time, and must remove items in the same sequence as they were placed in the queue.
Also learn how we can combine several queues to create a new data structure: a priority queue. A priority queue allows the user to add items to the queue that are deemed to be high priority, and get moved ahead in the line. This added complexity is simple to achieve and is a good example of how we can build up complexity through the use of data structures.
/**
*
* Queue
*
* First in First out
*
* API:
*
* enqueue() - Push a new item to the first place
* dequeue() - Get first in item from the last of array
* peek() - Check the next item in the queue
* length
* isEmpty()
*/ function createQueue() {
const queue = [];
return {
enqueue(item) {
queue.unshift(item);
},
dequeue() {
return queue.pop();
},
peek() {
return queue[queue.length - 1];
},
get length() {
return queue.length;
},
isEmpty() {
return queue.length === 0;
},
};
} /**
*
* Priority Queue
*
* First in First out for priority list and normal list
*
* API:
*
* enqueue() - Push a new item to the first place
* dequeue() - Get first in item from the last of array
* peek() - Check the next item in the queue
* length
* isEmpty()
*/
function createPriorityQueue() {
const queue = createQueue();
const p_queue = createQueue();
return {
enqueue (item, isPriority) {
if (isPriority) {
return p_queue.enqueue(item)
} queue.enqueue(item)
},
dequeue () {
if (!p_queue.isEmpty()) {
return p_queue.dequeue()
} return queue.dequeue()
},
peek () {
if (!p_queue.isEmpty()) {
return p_queue.peek()
} return queue.peek()
},
get length () {
return p_queue.length + queue.length;
},
isEmpty () {
return p_queue.isEmpty() && queue.isEmpty();
}
}
} module.exports = {createQueue, createPriorityQueue}; const q = createQueue();
q.enqueue("Learn algorithoms");
q.enqueue("Learn data structure");
q.enqueue("Learn thinking"); console.log(q.peek()); // 'Learn algorithoms'
q.dequeue();
console.log(q.peek()); // 'Learn data structure'
q.dequeue();
console.log(q.peek()); // 'Learn thinking'
q.dequeue();
console.log(q.isEmpty()); const pq = createPriorityQueue()
pq.enqueue('A fix here')
pq.enqueue('A bug there')
pq.enqueue('A new feature') pq.dequeue()
pq.enqueue('Emergency task!', true)
console.log(pq.dequeue())
console.log(pq.peek())
Notice 'unshift' function time Complixty is not O(1). For Queue, better have enqueue and dequeue both O(1): to achieve that we can use Map:
function Queue() {
let data = new Map();
let lastDeQueueIndex = ;
let nextEnQueueIndex = ;
return {
enqueue(item) {
// O(1)
data.set(nextEnQueueIndex, item);
nextEnQueueIndex++;
},
dequeue() {
// O(1)
const item = data.get(lastDeQueueIndex);
lastDeQueueIndex++;
return item;
},
size() {
return nextEnQueueIndex - lastDeQueueIndex;
}
};
}
最新文章
- 应该是Angular2的一个bug？
- Excel—利用散点图计算相关系数
- 18.Java泛型
- 如何在使用itext生成pdf文档时给文档添加背景图片
- 【读书笔记】iOS网络-底层网络
- Additive Number
- 从两个平方算法到分治算法-java
- 对DotNet分布式应用搭建的考虑
- poj 1338 Ugly Numbers
- 【Minimum Depth of Binary Tree】cpp
- 【转载】VMWare ESXi 5.0和vSphere Client安装和配置
- C语言的编译过程和GCC编译参数
- js前台与后台数据交互
- 向maven中添加本地jar包
- BootstrapTable，选中某几行，获取其数据并进行后台处理。以及其他的属性使用。
- Linux之RTOS学习
- oracle常用函数介绍
- [八省联考2018]林克卡特树lct——WQS二分
- 更新403 Forbidden
- 058——VUE中vue-router之实例操作新闻列表单页面应用与路由别名的使用