Введение
Все три относятся к структуре данных.Как профессиональный техник, понимание структуры данных является неотъемлемой частью. На ежедневных собеседованиях вы можете столкнуться с рядом вопросов, таких как стеки, кучи и очереди.
- Стек выполнения и очередь задач цикла событий.
- Проблемы кучи и стека хранения переменных.
- Реализация структур данных стека и очереди.
- Что такое стеки, кучи и очереди?
- Есть также некоторые связанные проблемы с почерком.
Во время интервью я часто задаю ряд вопросов, связанных с ним.
Во-вторых, стек
2.1 Введение
Стек — это упорядоченная коллекция, которая следует принципу «последним пришел — первым ушел» (LIFO). Как вновь добавленные, так и удаленные данные хранятся в верхней части стека на одном конце стека, а другой конец находится внизу стека. Новые элементы находятся в верхней части стека, а старые элементы — в нижней части стека. Стек автоматически выделяется и освобождается компилятором. Стек использует кэш первого уровня. Он находится в памяти при вызове и автоматически освобождается после завершения вызова.
Для каштана: Теннисная коробка/деревянные блоки
2.2 Хранение основных структур данных (стек хранения)
В javaScript типы данных делятся на базовые типы данных и ссылочные типы данных.Основные типы данных включают в себя: строку, число, логическое значение, неопределенное значение, нуль, символ и большое число. В памяти эти типы данных хранятся в пространстве стека, и мы обращаемся к ним по значению. Типы прототипов хранятся в памяти стека, фиксированного размера и упорядочены.
2.3 Стек выполнения (стек вызовов функций)
После того, как мы узнали, как хранить базовую структуру данных, давайте посмотрим, как управлять несколькими стеками в JavaScript.контекст выполнения.
- Когда выполнение программы входит в контекст выполнения, его контекст выполнения создается и помещается в стек выполнения (push).
- Когда выполнение программы завершено, ее контекст выполнения уничтожается, выталкивается из вершины стека (извлекается), а управление передается следующему контексту выполнения.
Каждый исполняемый код в JavaScript перед интерпретацией и выполнением создает исполняемый контекст. Согласно блоку исполняемого кода, его можно разделить на три исполняемых контекста.
- Глобальный исполняемый контекст: у каждой программы есть глобальный исполняемый код, и он только один. Любой код не внутри функции находится в глобальном контексте выполнения.
- Контекст выполнения функции: всякий раз, когда вызывается функция, для этой функции создается новый контекст. Каждая функция создает свой собственный контекст выполнения при вызове.
- Контекст выполнения Eval: Eval также имеет свой собственный контекст выполнения.
Поскольку выполнение JS сначала входит в глобальную среду, «нижняя часть стека всегда является контекстом выполнения глобальной среды». А на «вершине стека находится контекст выполнения выполняющейся в данный момент функции», когда вызов функции завершится, она будет протолкнута из вершины стека (в идеале замыкание предотвратит эту операцию, замыкание будет подробно описано в последующих статьях).
«Существует только одна глобальная среда, и есть только один соответствующий контекст глобального выполнения. Он будет выталкиваться из стека выполнения только после закрытия страницы, в противном случае она всегда будет существовать в нижней части стека»
См. пример:
let name = '蜗牛';
function sayName(name) {
sayNameStart(name);
}
function sayNameStart(name) {
sayNameEnd(name);
}
function sayNameEnd(name) {
console.log(name);
}
По мере выполнения кода объявляйте:
2.4 Создать стек (реализовать метод стека)
Нам нужно самим создать стек, и этот стек содержит некоторые методы.
- push(element(s)): добавить один (или несколько) новых элементов в верхнюю часть стека
- pop(): удалить элемент в верхней части стека и вернуть элемент
- peek(): возвращает элемент наверху стека, ничего не делая со стеком.
- isEmpty(): Проверить, пуст ли стек
- size(): возвращает количество элементов в стеке
- clear(): очистить стек
function Stack() {
let items = [];
this.push = function(element) {
items.push(element);
};
this.pop = function() {
let s = items.pop();
return s;
};
this.peek = function() {
return items[items.length - 1];
};
this.isEmpty = function() {
return items.length == 0;
};
this.size = function() {
return items.length;
};
this.clear = function() {
items = [];
}
}
Но этот метод создает несколько копий элементов при создании нескольких экземпляров. не подходит. Как реализовать класс Stack с ES 6. Может быть реализовано с помощью WeakMap и гарантирует конфиденциальность свойств.
let Stack = (function() {
const items = new WeakMap();
class Stack {
constructor() {
items.set(this, []);
}
getItems() {
let s = items.get(this);
return s;
}
push(element) {
this.getItems().push(element);
}
pop() {
return this.getItems().pop();
}
peek() {
return this.getItems()[this.getItems.length - 1];
}
isEmpty() {
return this.getItems().length == 0;
}
size() {
return this.getItems().length;
}
clear() {
this.getItems() = [];
}
}
return Stack;
})();
2.5 Использование стеков для решения задач
Стек может решить проблему преобразования от десятичной к двоичной проблеме, задачу произвольного базового преобразования, задачу сбалансированных скобок, а также проблему HAN Luota.
// 例子十进制转二进制问题
function divideBy2(decNumber) {
var remStack = new Stack(),
rem,
binaryString = '';
while (decNumber > 0) {
rem = Math.floor(decNumber % 2);
remStack.push(rem);
decNumber = Math.floor(decNumber / 2);
}
while(!remStack.isEmpty()) {
binaryString += remStack.pop().toString();
}
return binaryString;
}
// 任意进制转换的算法
function baseConverter(decNumber, base) {
var remStack = new Stack(),
rem,
binaryString = '',
digits = '0123456789ABCDEF';
while (decNumber > 0) {
rem = Math.floor(decNumber % base);
remStack.push(rem);
decNumber = Math.floor(decNumber / base);
}
while(!remStack.isEmpty()) {
binaryString += digits[remStack.pop()].toString();
}
return binaryString;
}
2.6 проблема переполнения стека
2.6.1 Ограничение размера стека
В разных браузерах есть ограничение на размер стека вызовов, и при его превышении возникает проблема переполнения стека. Следующий код проверяет, что браузер не ограничивает размер стека вызовов.
var i = 0;
function recursiveFn () {
i++;
recursiveFn();
}
try {
recursiveFn();
} catch (ex) {
console.log(`我的最大调用栈 i = ${i} errorMsg = ${ex}`);
}
Гугл Хром:
2.6.2 Проблема переполнения стека рекурсивных вызовов
function Fibonacci (n) {
if ( n <= 1 ) {return 1};
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
Fibonacci(10) // 89
Fibonacci(100) // 超时
Fibonacci(500) // 超时
Вышеприведенный код представляет собой факториальную функцию.Чтобы вычислить факториал n, необходимо сохранить не более n записей вызовов, а сложность - O(n). Если предел превышен, возникает проблема переполнения стека.
2.6.3 Оптимизация хвостового рекурсивного вызова
Рекурсия очень требовательна к памяти, потому что она должна сохранять сотни кадров вызовов одновременно, и она склонна к ошибкам "переполнения стека". Но для хвостовой рекурсии, поскольку существует только один кадр вызова, ошибка «переполнение стека» никогда не возникнет.
function Fibonacci2 (n , ac1 = 1 , ac2 = 1) {
if( n <= 1 ) {return ac2};
return Fibonacci2 (n - 1, ac2, ac1 + ac2);
}
Fibonacci2(100) // 573147844013817200000
Fibonacci2(1000) // 7.0330367711422765e+208
Fibonacci2(10000) // Infinity
Из этого следует, что «оптимизация хвостового вызова» настолько важна для рекурсивных операций, что некоторые языки функционального программирования записывают ее в спецификацию языка. То же самое верно и для ES6, который впервые прямо предусматривает, что все реализации ECMAScript должны использовать «оптимизацию хвостового вызова». То есть, пока в ES6 используется хвостовая рекурсия, переполнения стека (или тайм-аута, вызванного послойной рекурсией) не произойдет, а память будет относительно сохранена.
2.6.4 Почему стековая память, занимаемая хвостовой рекурсией, также увеличивается с параметрами в этом примере?
Источник столбца:Начало работы с ECMAScript 6
Три, куча
3.1 Введение
Куча обычно выделяется и освобождается оператором (программистом).Если оператор не выделяет и не освобождает, она будет восстановлена и освобождена ОС. Метод распределения аналогичен связному списку. Куча хранится в кеше L2.
3.2 Куча памяти
В дополнение к примитивным типам в JavaScript есть еще один тип данных, тип объекта, который включает в себя:
- Object
- Function
- Array
- Date
- RegExp
Все типы объектов хранятся в динамической памяти, которая имеет переменный размер, сложна и переменна. Указатель данных типа Object хранится в пространстве памяти стека, а значение, на которое фактически указывает указатель, хранится в пространстве кучи памяти.
3.3 Почему существует различие между памятью кучи и памятью стека?
Обычно связано с механизмом сборки мусора. Для того, чтобы минимизировать объем памяти, занимаемой программой при ее работе.
Когда метод выполняется, каждый метод устанавливает свой собственный стек памяти, и переменные, определенные в этом методе, будут помещаться в эту память стека одна за другой.По мере завершения выполнения метода стек памяти этого метода также будет уничтожается естественным путем. Поэтому все переменные, определенные в методе, помещаются в память стека;
Когда мы создаем объект в программе, этот объект будет сохранен в области данных времени выполнения для повторного использования (поскольку стоимость создания объекта обычно велика), эта область данных времени выполнения является памятью кучи. Объект в памяти кучи не будет уничтожен с окончанием метода.Даже после завершения метода на объект может ссылаться другая ссылочная переменная (общая при передаче параметра метода), тогда объект не будет уничтожен, only Когда у объекта нет ссылочных переменных, ссылающихся на него, системный механизм сборки мусора соберет его, когда он будет проверен.
4. Очередь
4.1 Введение
Очередь следует FIFO, упорядоченному набору принципов «первым пришел — первым вышел». Очередь добавляет элементы в конец и удаляет элементы вверху. Самая распространенная очередь в реальности – это очередь. Первый в очереди, первый обслужен. (Пожалуйста, встаньте в очередь цивилизованно, не сокращайте очередь.)
4.2 Очередь задач
JavaScript является однопоточным, а однопоточные задачи делятся на синхронные задачи и асинхронные задачи. Синхронная задача ожидает выполнения основного потока по очереди в стеке вызовов.После того, как асинхронная задача имеет результат, она регистрирует callback-функцию в очереди задач, ожидает простоя основного потока (стек вызовов пуст) и помещает его в стек выполнения для ожидания выполнения основного потока.
Цикл событий выполняется, как показано на рисунке ниже, и очередь задач является лишь его частью.
После того, как стек выполнения выполнит задачу синхронизации, если стек выполнения пуст, он проверит, пуста ли очередь микрозадач (MicroTask), и если она пуста, выполнит очередь макрозадач (MacroTask). В противном случае все очереди микрозадач будут выполняться одновременно. Каждый раз, когда выполняется макрозадача, она проверяет, пуста ли очередь микрозадач.Если она не пуста, очередь микрозадач будет выполняться в порядке поступления. Затем выполните следующую задачу макроса и так далее. до конца.
4.3 Создайте очередь (реализуйте метод очереди)
Реализуйте класс Queue, содержащий следующие методы.
- enqueue(element(s)): добавляет один (или несколько) элементов в конец очереди.
- dequeue(): удаляет первый элемент из очереди и возвращает удаленный элемент.
- front(): возвращает первый элемент очереди — первый добавляемый элемент и первый удаляемый.
- isEmpty(): определяет, пуста ли очередь.
- size(): возвращает длину очереди.
// 队列Queue类简单实现
function Queue() {
let items = [];
// 添加元素
this.enqueue = function(element) {
items.push(element);
};
// 删除元素
this.dequeue = function() {
return items.shift();
};
// 返回队列第一个元素
this.front = function() {
return items[0];
};
// 判断队列是否为空
this.isEmpty = function() {
return items.length === 0;
};
// 返回队列长度
this.size = function() {
return items.length;
};
}
Синтаксис ES6 реализует класс очереди Queue, использует WeakMap для сохранения элементов частного свойства и использует внешние функции (замыкания) для инкапсуляции класса Queue.
let Queue1 = (function() {
const items = new WeakMap();
class Queue1 {
constructor() {
items.set(this, []);
}
// 获取队列
getQueue() {
return items.get(this);
}
// 添加元素
enqueue (element) {
this.getQueue().push(element);
}
// 删除元素
dequeue() {
return this.getQueue().shift();
}
// 返回队列第一个元素
front() {
return this.getQueue()[0];
}
// 判断队列是否为空
isEmpty() {
return this.getQueue().length === 0;
}
// 返回队列长度
size() {
return this.getQueue().length;
}
}
return Queue1;
})();
4.4 Приоритетная очередь
Элементы добавляются и удаляются в зависимости от приоритета. Наиболее распространена последовательность посадки в аэропорту. Первый класс и бизнес-класс имеют приоритет перед эконом-классом. Реализуйте очередь с приоритетами и установите приоритеты.
// 优先列队
function PriorityQueue() {
let items = [];
// 创建元素和它的优先级（priority越大优先级越低）
function QueueElement(element, priority) {
this.element = element;
this.priority = priority;
}
// 添加元素（根据优先级添加）
this.enqueue = function(element, priority) {
let queueElement = new QueueElement(element, priority);
// 标记是否添加元素的优先级的值最大
let added = false;
for (let i = 0; i < items.length; i++) {
if (queueElement.priority < items[i].priority) {
items.splice(i, 0, queueElement);
added = true;
break;
}
}
if (!added) {
items.push(queueElement);
}
};
// 删除元素
this.dequeue = function() {
return items.shift();
};
// 返回队列第一个元素
this.front = function() {
return items[0];
};
// 判断队列是否为空
this.isEmpty = function() {
return items.length === 0;
};
// 返回队列长度
this.size = function() {
return items.length
};
// 打印队列
this.print = function() {
for (let i = 0; i < items.length; i++) {
console.log(`${items[i].element} - ${items[i].priority}`);
}
};
}
4.5 Круговая очередь (барабанит и передает цветы)
// 循环队列（击鼓传花）
function hotPotato(nameList, num) {
let queue = new Queue(); //{1} // 构造函数为4.3创建
for(let i =0; i< nameList.length; i++) {
queue.enqueue(nameList[i]); // {2}
}
let eliminted = '';
while(queue.size() > 1) {
// 把队列num之前的项按照优先级添加到队列的后面
for(let i = 0; i < num; i++) {
queue.enqueue(queue.dequeue()); // {3}
}
eliminted = queue.dequeue(); // {4}
console.log(eliminted + '在击鼓传花游戏中被淘汰');
}
return queue.dequeue(); // {5}
}
let names = ['John', 'Jack', 'Camila', 'Ingrid', 'Carl'];
let winner = hotPotato(names, 7);
console.log('获胜者是：' + winner);
- Используя класс очереди, создайте очередь.
- Поставьте в очередь всех, кто сейчас играет в Drumming and Passing Flowers.
- Получив число, пройдитесь по очереди, удаляя предмет из начала очереди и добавляя его в конец очереди (как в игре: вы передаете цветок человеку рядом с вами, и вы в безопасности) .
- Как только количество итераций достигнуто, лицо, удерживающее цветок в это время, будет устранено.
- В конце концов, остается только один человек, и этот человек является победителем.
Источник ссылки: