1 Array common operations

let str = ['a', 'b', 'c', 'd', 'e']; str.push('f'); // Add an element to the end of the array str.unshift('g'); // Add an element at the beginning of the array str.pop(); // Remove the last element in the array str.shift(); // Delete the first element in the array str.splice(2, 0, 'h'); // Append 'h' to position 2 in arrayCopy the code

2 the stack

What is a stack?

  1. A stack is a linear structure with limited operations, LIFO last in first out.
  • It’s like taking an elevator
  1. The limitation is that only one end of the table is allowed for insert and delete operations. This end is called the top of the stack, and the other end is called the bottom of the stack.
  2. Inserting a new element into a stack becomes a new top-stack element, while deleting an element from a stack removes the top-stack element so that its neighboring elements become the new top-stack element.

Use arrays to encapsulate the stack

<script> function Stack() { this.item = []; Prototype. Push = function (element) {this.item.push(element); }; Prototype. Pop = function () {return this.item.pop(); }; Prototype. Peek = function () {return this.item[this.item.length-1]; }; Function () {return this.item.length == 0; }; Stack. Prototype. Size = function () {return this.item.length; }; Prototype. ToString = function () {let resString = ''; for (let i = 0; i < this.item.length; i++) { resString += this.item[i] + ' '; } return resString; }; } let stack = new Stack(); stack.push('a'); stack.push('b'); stack.push('c'); console.log(stack); stack.pop(); console.log(stack); console.log(stack.peek()); console.log(stack.size()); console.log(stack.isEmpty()); console.log(stack.toString()); </script>Copy the code

Use the stack to achieve decimal to binary

Using the features of last in first out stack and just encapsulated stack to achieve decimal to binary

Function dec2bin(num) {let stack = new stack (); let remainder; While (num > 0) {remainder = num % 2; num = Math.floor(num / 2); stack.push(remainder); } // let result = ''; while (! stack.isEmpty()) { result += stack.pop(); } return result; } console.log(dec2bin(22));Copy the code

3 the queue

What is a queue?

  1. Queues are also linear tables with limited operations, FIFO first in first out.
  • It’s like queuing
  1. The limitation is that it allows only delete operations at the front end of the table and insert operations at the back end

Implement queues with arrays

class Queue { constructor() { this.item = []; } //1. Add one or more items to the end of the queue (element) {this.item.push(element); RemoveQueue () {return this.item.shift(); } front() {return this.item[0]; } //4. Check whether the queue isEmpty isEmpty() {return this.item.length == 0; } u size() {return this.item.length; } //6. ToString method toString() {let resultString = "; for (let i = 0; i < this.item.length; i++) { resultString += this.item[i] + ' '; } return resultString; } } let queue = new Queue(); Queue.addqueue ('a'); queue.addQueue('b'); queue.addQueue('c'); console.log(queue); queue.removeQueue(); console.log(queue); console.log(queue.size()); console.log(queue.isEmpty()); console.log(queue.front()); console.log(queue.toString());Copy the code

Drum pass flower case

Listen to the question: several friends play a game together, gather in a circle, start to count, count to a certain number of people automatically eliminated. The last person left is going to win, and what position was the last person left? Ideas:

  1. Parameters are the contestant list and set number
  2. Put the contestants in the queue
  3. Place the queue elements before the selected number in order, delete the first one, store it last, and continue
  4. Delete the elements corresponding to the number after deleting the elements before the number
  5. Loop through steps 3 and 4 as a loop body
  6. The loop ends with only one element left in the queue
Function game(nameList, num) {function game(nameList, num) {let queue = new queue (); for (let i = 0; i < nameList.length; i++) { queue.addQueue(nameList[i]); } while (queue.size() > 1) { for (let i = 0; i < num; i++) { queue.addQueue(queue.removeQueue(queue[i])); queue; } queue.removeQueue(); } console.log(queue.size()); Console. log(namelist.indexof (queue.front())); Return queue.front(); return queue.front(); Who is the last man} / / the queue / / calling function let STR = [' a ', 'b', 'c', 'd']. console.log(game(str, 3));Copy the code

Priority queue

When an element is placed in a queue, not only the element itself is added, but also a priority is added to the element. The smaller the priority is, the higher the priority is placed in the queue.

function PriorityQueue() { function QueueElement(element, priority) { this.element = element; this.priority = priority; } this.item = []; PriorityQueue.prototype.enterQueue = function (element, priority) { let queueElement = new QueueElement(element, priority); if (this.item.length == 0) { this.item.push(queueElement); } else { let added = false; for (let i = 0; i < this.item.length; i++) { if (queueElement.priority < this.item[i].priority) { this.item.splice(i, 0, queueElement); added = true; break; } } if (! added) { this.item.push(queueElement); }}}; / / delete the elements in the queue PriorityQueue. Prototype. RemoveQueue = function () {return this. Item. The shift (); }; / / 3. Check the queue PriorityQueue front element. The prototype. The front = function () {return this. The item [0]. }; / / 4, to determine whether a queue is empty PriorityQueue. Prototype. IsEmpty = function () {return this. Item. The length = = 0; }; / / 5. The number of elements to obtain the queue PriorityQueue. Prototype. Size = function () {return this. Item. Length; }; / / 6. ToString method PriorityQueue. Prototype. ToString = function () {let resString = ' '; for (let i = 0; i < this.item.length; i++) { resString += this.item[i].element + ' '; } return resString; }; } let priorityQ = new PriorityQueue(); priorityQ.enterQueue('a', 5); priorityQ.enterQueue('b', 2); priorityQ.enterQueue('c', 8); console.log(priorityQ); console.log(priorityQ.size()); console.log(priorityQ.toString()); console.log(priorityQ.isEmpty());Copy the code