Chapter 4 "Queues"
Queues are a set of orderly items that follow the FIFO (First In First Out) principle.
Queues add new elements at the tail and remove elements from the top. The newly added elements must be at the end of the queue
A common example is queuing.
1. Creating queues
- We need to create our own class to represent a queue. Start with the most basic declarative class:
function Queue() {
//Here are attributes and methods
}
- First, you need a data structure to store elements in the queue. We can use arrays, just like the Stack class in the previous chapter.
Use it that way (you will find that Queue and Stack classes are very similar, except that the principles for adding and removing elements are different):
var items = []; - Some methods available for queues need to be declared:
Enquequeue (element (s): Add a new item (or items) to the end of the queue. dequeue(): Remove the first item in the queue (that is, the first item in the queue) and return the removed element. front(): Returns the first element in the queue - the element that was first added and removed. Queue No Make any changes (without removing elements, only returning element information -- very similar to the peek method of the Stack class). isEmpty(): If the queue does not contain any elements, return true or false. size(): Returns the number of elements contained in the queue, similar to the length attribute of the array.
- Add a new element enqueue to the queue. New items can only be added to the end of the queue
Since the queue follows the first-in-first-out principle, the first item added is also the first to be removed.
function Queue() {
//Here are attributes and methods
var items = [];
// Add new elements to the queue. New items can only be added to the end of the queue
this.enqueue = function(element){
items.push(element);
console.log(items);Array(1)
};
}
var queue = new Queue();
queue.enqueue(3);//[3]
queue.enqueue(5);//[3,5]
- Remove the item dequeue from the queue. Since the queue follows the first-in-first-out principle, the first item added is also the first to be removed.
function Queue() {
//Here are attributes and methods
var items = [];
// Add new elements to the queue. New items can only be added to the end of the queue
this.enqueue = function(element){
items.push(element);
console.log(items);Array(1)
};
this.dequeue = function(){
return items.shift();
};
}
var queue = new Queue();
queue.enqueue(3);//[3]
queue.enqueue(5);//[3,5]
queue.dequeue();//Remove the first element
//To see the effect of dequeue removal, you can print out all the elements.
//You can also see the length of the queue (array) now.
- Only the enqueue method and the dequeue method can add and remove elements, which ensures that the Queue class follows the first-in-first-out principle.
- Additional auxiliary methods: front/isEmpty/size/print
Returns the front item of the queue:front
this.front = function(){
return items[0];
};
isEmpty Method. If the queue is empty, it will return true ，Otherwise return false
(Pay attention to this method and Stack The same in the class)
this.isEmpty = function(){
return items.length == 0;
};
The size method is the same as in the Stack class.
Judge the number of elements in an array
this.size = function(){
return items.length;
};
Print the same elements in the queue as in the Stack class
this.print = function(){
console.log(items.toString());
};
Complete the code:
<script>
function Queue() {
//Here are attributes and methods
var items = [];
// Add new elements to the queue. New items can only be added to the end of the queue
this.enqueue = function(element){
items.push(element);
console.log(items);Array(1)
};
// Remove items from the queue
// Since the queue follows the first-in-first-out principle, the first item added is also the first to be removed.
this.dequeue = function(){
return items.shift();
};
// Only enqueue and dequeue methods can add and remove elements.
// This ensures that the Queue class follows the first-in-first-out principle
// Additional auxiliary methods
// Return the item at the front of the queue
this.front = function(){
return items[0];
};
// isEmpty method. If the queue is empty, it returns true or false
// (Note that this method is the same as in the Stack class)
this.isEmpty = function(){
return items.length == 0;
};
// The size method is the same as in the Stack class.
// Judge the number of elements in an array
this.size = function(){
return items.length;
};
// Print the same elements in the queue as in the Stack class
this.print = function(){
console.log(items.toString());
};
}
var queue = new Queue();
queue.enqueue(3);//[3]
queue.enqueue(5);//[3,5]
// queue.dequeue();// Remove the first element
console.log(queue.front());//3
console.log(queue.isEmpty());//false
console.log(queue.size());//2
queue.print();//3,5
</script>
- Queue classes are very similar to Stack classes. The only difference is the dequeue method and the front method, which are caused by the different first-in, first-out and last-in, first-out principles.
- Using Queue classes
The first thing we need to do is instantiate the Queue class we just created, and then we can verify that it is empty (the output is true, because we have not added any elements to the queue yet):
function Queue() {
//Here are attributes and methods
var items = [];
this.isEmpty = function(){
return items.length == 0;
};
}
var queue = new Queue();
console.log(queue.isEmpty());//true
Complete code:
function Queue() {
var items = [];
this.enqueue = function(element){
items.push(element);
console.log(items);
};//Join the team
this.dequeue = function(){
return items.shift();
};//Team out
this.front = function(){
return items[0];
};//View the team header elements
this.isEmpty = function(){
return items.length == 0;
};//Determine whether the queue is empty
this.size = function(){
return items.length;
};//Queue size
this.print = function(){
console.log(items.toString());
};//Print queue
}
var queue = new Queue();//Examples of declaration queues
console.log(queue.isEmpty());//false
queue.enqueue("John");//["John"]
queue.enqueue("Jack");//(2) ["John", "Jack"]
queue.enqueue("Camila");//(3) ["John", "Jack", "Camila"]
console.log(queue.size()); //Output 3
console.log(queue.isEmpty()); //Output false
queue.dequeue();
queue.dequeue();
queue.print();//Camila
II. Priority Queue
A practical example is the sequence of airport boarding.
First class and business class passengers have higher priority than economy class passengers. In some countries, older people and pregnant women (or women with children) also enjoy higher priority than other passengers when boarding planes.
Another practical example is the waiting room of a hospital.
Doctors give priority to patients with more serious illness. Normally, nurses will identify and classify the patients according to the severity of their illness.
- There are two options for implementing a priority queue: setting priorities and adding elements in the right place; or adding elements with a column operation and then removing them according to priority.
- Simple Analog Queuing
function Queue() {
var items = [];
this.enqueue = function(element){
items.push(element);
console.log(items);
};//Join the team
this.dequeue = function(){
return items.shift();
};//Team out
this.front = function(){
return items[0];
};//View the team header elements
this.isEmpty = function(){
return items.length == 0;
};//Determine whether the queue is empty
this.size = function(){
return items.length;
};//Queue size
this.clear = function () {
items = [];
};//ClearQueue
this.print = function(){
console.log(items.toString());
};//Print queue
}
var queue = new Queue();
console.log("Is the queue empty? " + queue.isEmpty());
queue.enqueue('Mr.A');
queue.enqueue('Mr.B');
queue.enqueue('Mr.C');
console.log("Current queue:");
queue.print();
console.log("Team members: " + queue.dequeue());
console.log("Current queue:");
queue.print();
console.log("Empty the queue:");
queue.clear();
queue.print();
- Priority queue own understanding: In our queue, came a friend with VIP membership card, inserted in the front of the line. After a while, a friend with a SVIP membership card came to the front of the VIP (there may be a priority queue, and people with higher priority can find people with lower priority).
Note: Priority size and ranking are set by yourself. Here we set the order from small to large, the same priority first in first out
function PriorityQueue(){
var items = [];
function QueueElement(element,priority){
this.element = element;
this.priority = priority;
}
this.enqueue = function(element, priority){
var qe = new QueueElement(element, priority);
//If the queue is empty, the element is listed directly or the priority of the element is compared with that of other elements.
if(this.isEmpty()){
items.push(qe);
}else{
var added = false;
//Find items that have a higher priority value than adding elements, and insert new elements before it.
for(var i=0; i<items.length; i++){
//Once you find an element with a higher priority value, insert a new element and terminate the queue loop
if(qe.priority < items[i].priority){
items.splice(i,0,qe);
added = true;
break;
}
}
if(!added){
items.push(qe);
}
}
};
this.isEmpty = function(){
return items.length === 0;
};
this.print = function(){
var str = '';
for(var i=0; i<items.length; i++){
str += items[i].priority + ' ' + items[i].element + '\n'
}
console.log(str.toString());
}
}
/*test*/
var pq = new PriorityQueue();
pq.enqueue('John',2);
pq.enqueue('Jack',1);
pq.enqueue('Camila',1);
pq.print();
Change the following to Maximum Priority Queue
3. Cyclic Queue: Drum-beating and Flower-spreading
-
Another modified version of the queue implementation is the circular queue.
-
An example of a circular queue is the drum and flower game (Hot).
Potato). In this game, the children form a circle and pass the flowers to the people next to them as soon as possible. At some point the flowering stops.
Whoever spends this time will quit the circle to end the game. Repeat the process until only one child (winner) is left. -
Drum Spread Flower (Circulating Queue) Code:
function Queue() {
var items = [];
this.enqueue = function (ele) {
items.push(ele);
};//Join the team
this.dequeue = function () {
return items.shift();
};//Team out
this.front = function () {
return items[0];
};//View the team header elements
this.isEmpty = function () {
return items.length === 0;
};//Determine whether the queue is empty
this.size = function () {
return items.length;
};//Queue size
this.clear = function () {
items = [];
};//ClearQueue
this.print = function () {
console.log(items.toString());
};//Print queue
}
function hotPotato (nameList, num){//Parameter: Array of people, frequency of flowering
var queue = new Queue(); // {1}
for (var i=0; i<nameList.length; i++){
queue.enqueue(nameList[i]); // Initialize {2}/// / and add all the names to the queue.
}
var eliminated = '';//Eliminated persons
while (queue.size() > 1){ //As long as there are at least two people in the queue, it's always going round.
for (var i=0; i<num; i++){//Enter the team and simulate the cycle effect
queue.enqueue(queue.dequeue()); // Given a number, {3} iterates over the queue. Remove an item from the beginning of the queue and add it to the end of the queue
}
eliminated = queue.dequeue();//Once the number of passes reaches a given number, the person holding the flower is eliminated (removed from the queue).
console.log(eliminated + 'Was eliminated in the drum-beating and flower-passing game');
}
return queue.dequeue();// {5}
}
var names = ['John','Jack','Camila','Ingrid','Carl'];
var winner = hotPotato(names, 7);
console.log('Winner:' + winner);//The final remaining person
