В мире программирования существует множество структур данных, каждая из которых имеет свои особенности и области применения. Среди них особое место занимают стек и очередь — две фундаментальные концепции, которые играют важную роль в разработке эффективных алгоритмов и программ. В контексте JavaScript, языка, который стал неотъемлемой частью веб-разработки, понимание этих структур данных приобретает особое значение.
Что такое стек?
Стек представляет собой упорядоченную коллекцию элементов, в которой добавление и удаление элементов происходит только с одного конца, называемого вершиной стека. Эта структура данных работает по принципу «последним пришел — первым ушел» (LIFO — Last In, First Out).
Можно представить стек как стопку тарелок: новые тарелки кладутся сверху, и когда нужно взять тарелку, берется верхняя. В программировании стек используется для хранения и управления данными в различных сценариях, от простых вычислений до сложных алгоритмов.
Основные операции со стеком
- Push: добавление элемента на вершину стека
- Pop: удаление элемента с вершины стека
- Peek (или Top): просмотр элемента на вершине стека без его удаления
- isEmpty: проверка, пуст ли стек
- Size: определение количества элементов в стеке
Реализация стека в JavaScript
В JavaScript стек можно реализовать несколькими способами. Самый простой — использование встроенного объекта Array с его методами push() и pop().
class Stack { constructor() { this.items = []; } push(element) { this.items.push(element); } pop() { if (this.isEmpty()) { return "Стек пуст"; } return this.items.pop(); } peek() { if (this.isEmpty()) { return "Стек пуст"; } return this.items[this.items.length - 1]; } isEmpty() { return this.items.length === 0; } size() { return this.items.length; } clear() { this.items = []; } print() { console.log(this.items.toString()); } } Эта реализация предоставляет все основные операции стека, а также дополнительные методы для удобства использования.
Применение стека в JavaScript
Стеки находят широкое применение в различных областях программирования:
- Управление вызовами функций (call stack)
- Обработка выражений (например, проверка сбалансированности скобок)
- Реализация алгоритмов обхода графов (DFS — поиск в глубину)
- Отмена действий в приложениях (undo functionality)
- Парсинг синтаксиса в компиляторах
Пример использования стека: проверка сбалансированности скобок
Рассмотрим практический пример использования стека для решения популярной задачи — проверки сбалансированности скобок в выражении.
function isBalanced(expression) { const stack = new Stack(); const openBrackets = '({['; const closeBrackets = ')}]'; const bracketsMap = { ')': '(', '}': '{', ']': '[' }; for (let char of expression) { if (openBrackets.includes(char)) { stack.push(char); } else if (closeBrackets.includes(char)) { if (stack.isEmpty() || stack.pop() !== bracketsMap[char]) { return false; } } } return stack.isEmpty(); } console.log(isBalanced("({[]})")); // true console.log(isBalanced("({[}])")); // false В этом примере стек используется для хранения открывающих скобок. При встрече закрывающей скобки проверяется, соответствует ли она последней открывающей скобке в стеке. Если все скобки сбалансированы, стек в конце должен быть пустым.
Концепция очереди в JavaScript
После рассмотрения стека, следует обратить внимание на другую важную структуру данных — очередь. Если стек работает по принципу «последний пришел — первый ушел», то очередь функционирует по принципу «первый пришел — первый ушел» (FIFO — First In, First Out).
Что такое очередь?
Очередь — это упорядоченная коллекция элементов, в которой добавление новых элементов происходит с одного конца (хвост), а удаление — с другого (голова). Это напоминает очередь в реальной жизни: первый, кто встал в очередь, первым же ее и покинет.
Основные операции с очередью
- Enqueue: добавление элемента в конец очереди
- Dequeue: удаление элемента из начала очереди
- Front: просмотр первого элемента очереди без его удаления
- isEmpty: проверка, пуста ли очередь
- Size: определение количества элементов в очереди
Реализация очереди в JavaScript
Как и в случае со стеком, очередь можно реализовать различными способами. Вот пример простой реализации с использованием массива:
class Queue { constructor() { this.items = []; } enqueue(element) { this.items.push(element); } dequeue() { if (this.isEmpty()) { return "Очередь пуста"; } return this.items.shift(); } front() { if (this.isEmpty()) { return "Очередь пуста"; } return this.items[0]; } isEmpty() { return this.items.length === 0; } size() { return this.items.length; } clear() { this.items = []; } print() { console.log(this.items.toString()); } } В этой реализации используется метод shift() для удаления первого элемента массива, что может быть неэффективно для больших очередей, так как требует перемещения всех остальных элементов.
Оптимизированная реализация очереди
Для более эффективной работы с большими объемами данных можно использовать оптимизированную реализацию очереди:
class OptimizedQueue { constructor() { this.items = {}; this.frontIndex = 0; this.backIndex = 0; } enqueue(element) { this.items[this.backIndex] = element; this.backIndex++; } dequeue() { if (this.isEmpty()) { return "Очередь пуста"; } const item = this.items[this.frontIndex]; delete this.items[this.frontIndex]; this.frontIndex++; return item; } front() { if (this.isEmpty()) { return "Очередь пуста"; } return this.items[this.frontIndex]; } isEmpty() { return this.frontIndex === this.backIndex; } size() { return this.backIndex - this.frontIndex; } clear() { this.items = {}; this.frontIndex = 0; this.backIndex = 0; } print() { console.log(Object.values(this.items)); } } Эта реализация использует объект вместо массива и два указателя (frontIndex и backIndex) для отслеживания начала и конца очереди. Операции enqueue и dequeue выполняются за постоянное время O(1), что делает эту реализацию более эффективной для больших очередей.
Применение очереди в JavaScript
Очереди находят применение во многих областях программирования:
- Управление асинхронными операциями (например, очередь задач)
- Буферизация данных (например, при передаче данных между процессами)
- Реализация алгоритмов обхода графов (BFS — поиск в ширину)
- Управление печатью в принтерах
- Обработка событий в веб-приложениях
Пример использования очереди: симуляция печати документов
Рассмотрим практический пример использования очереди для симуляции работы принтера:
class Printer { constructor() { this.queue = new OptimizedQueue(); } addDocument(doc) { this.queue.enqueue(doc); console.log(`Документ "${doc}" добавлен в очередь печати.`); } printDocuments() { console.log("Начало печати документов:"); while (!this.queue.isEmpty()) { const doc = this.queue.dequeue(); console.log(`Печать документа: "${doc}"`); } console.log("Все документы напечатаны."); } } // Использование const printer = new Printer(); printer.addDocument("Отчет"); printer.addDocument("Презентация"); printer.addDocument("Договор"); printer.printDocuments(); В этом примере очередь используется для управления порядком печати документов. Документы добавляются в конец очереди и печатаются в порядке их добавления.
Сравнение стека и очереди
Хотя стек и очередь имеют некоторые общие черты, они существенно различаются в своем поведении и применении. Рассмотрим основные различия между этими структурами данных:
| Характеристика | Стек | Очередь |
|---|---|---|
| Принцип работы | LIFO (Last In, First Out) | FIFO (First In, First Out) |
| Добавление элементов | На вершину | В конец (хвост) |
| Удаление элементов | С вершины | Из начала (головы) |
| Основные операции | push, pop | enqueue, dequeue |
| Типичные применения | Управление вызовами функций, отмена действий | Управление задачами, буферизация данных |
Выбор между стеком и очередью
Выбор между стеком и очередью зависит от конкретной задачи и требований к обработке данных:
- Если требуется обработать элементы в обратном порядке их поступления, стек будет оптимальным выбором.
- Если элементы должны обрабатываться в том же порядке, в котором они поступают, очередь будет более подходящей структурой.
Продвинутые концепции и вариации
Помимо базовых реализаций стека и очереди, существуют их различные модификации и расширения, которые могут быть полезны в определенных сценариях.
Двусторонняя очередь (Deque)
Двусторонняя очередь, или дек (от англ. double-ended queue), — это структура данных, которая объединяет свойства стека и очереди. Она позволяет добавлять и удалять элементы с обоих концов.
class Deque { constructor() { this.items = {}; this.frontIndex = 0; this.backIndex = 0; } addFront(element) { this.frontIndex--; this.items[this.frontIndex] = element; } addBack(element) { this.items[this.backIndex] = element; this.
backIndex++;
}
removeFront() {
if (this.isEmpty()) {
return "Дек пуст";
}
const item = this.items[this.frontIndex];
delete this.items[this.frontIndex];
this.frontIndex++;
return item;
}
removeBack() {
if (this.isEmpty()) {
return "Дек пуст";
}
this.backIndex--;
const item = this.items[this.backIndex];
delete this.items[this.backIndex];
return item;
}
peekFront() {
if (this.isEmpty()) {
return "Дек пуст";
}
return this.items[this.frontIndex];
}
peekBack() {
if (this.isEmpty()) {
return "Дек пуст";
}
return this.items[this.backIndex - 1];
}
isEmpty() {
return this.frontIndex === this.backIndex;
}
size() {
return this.backIndex - this.frontIndex;
}
clear() {
this.items = {};
this.frontIndex = 0;
this.backIndex = 0;
}
}
Двусторонняя очередь полезна в ситуациях, когда требуется гибкость в добавлении и удалении элементов с обоих концов структуры данных. Например, она может использоваться для реализации алгоритмов, таких как поиск палиндромов или в задачах, связанных с обработкой последовательностей данных.
Приоритетная очередь
Приоритетная очередь — это разновидность очереди, в которой каждый элемент имеет связанный с ним приоритет. Элементы с более высоким приоритетом обслуживаются раньше, чем элементы с более низким приоритетом.
class PriorityQueue { constructor() { this.items = []; } enqueue(element, priority) { const queueElement = { element, priority }; let added = false; for (let i = 0; i < this.items.length; i++) { if (queueElement.priority < this.items[i].priority) { this.items.splice(i, 0, queueElement); added = true; break; } } if (!added) { this.items.push(queueElement); } } dequeue() { if (this.isEmpty()) { return "Очередь пуста"; } return this.items.shift().element; } front() { if (this.isEmpty()) { return "Очередь пуста"; } return this.items[0].element; } isEmpty() { return this.items.length === 0; } size() { return this.items.length; } clear() { this.items = []; } print() { console.log(this.items.map(item => `${item.element} (приоритет: ${item.priority})`)); } } Приоритетные очереди часто используются в системах управления процессами, планирования задач и в алгоритмах, где важен порядок обработки элементов на основе их приоритета.
Циклический буфер
Циклический буфер, также известный как кольцевой буфер, — это структура данных фиксированного размера, которая работает как будто концы буфера соединены. Эта структура особенно полезна для буферизации потоков данных.
class CircularBuffer { constructor(capacity) { this.capacity = capacity; this.buffer = new Array(capacity); this.head = 0; this.tail = 0; this.size = 0; } enqueue(item) { if (this.isFull()) { throw new Error("Буфер переполнен"); } this.buffer[this.tail] = item; this.tail = (this.tail + 1) % this.capacity; this.size++; } dequeue() { if (this.isEmpty()) { throw new Error("Буфер пуст"); } const item = this.buffer[this.head]; this.head = (this.head + 1) % this.capacity; this.size--; return item; } peek() { if (this.isEmpty()) { throw new Error("Буфер пуст"); } return this.buffer[this.head]; } isEmpty() { return this.size === 0; } isFull() { return this.size === this.capacity; } clear() { this.head = 0; this.tail = 0; this.size = 0; } } Циклические буферы часто используются в ситуациях, где данные должны быть обработаны в порядке их поступления, но с ограничением по объему памяти, например, в системах реального времени или при обработке потоковых данных.
Применение стеков и очередей в реальных проектах
Понимание концепций стека и очереди важно не только для прохождения технических собеседований, но и для разработки эффективных решений в реальных проектах. Рассмотрим несколько примеров применения этих структур данных в практических сценариях.
Управление состоянием в веб-приложениях
Стеки часто используются для реализации функциональности отмены действий (undo) в веб-приложениях. Каждое действие пользователя может быть сохранено в стеке, что позволяет легко вернуться к предыдущим состояниям.
class UndoStack { constructor() { this.stack = []; } pushAction(action) { this.stack.push(action); } undo() { if (this.stack.length > 0) { const action = this.stack.pop(); action.undo(); } } } // Пример использования const undoStack = new UndoStack(); function addText(text) { document.body.innerHTML += text; undoStack.pushAction({ undo: () => { document.body.innerHTML = document.body.innerHTML.slice(0, -text.length); } }); } addText("Привет, "); addText("мир!"); // Отмена последнего действия undoStack.undo(); // Удаляет "мир!" Асинхронное выполнение задач
Очереди часто используются для управления асинхронными задачами в JavaScript, особенно в серверных приложениях на Node.js. Например, можно реализовать систему обработки задач с ограничением на количество одновременно выполняемых операций.
class TaskQueue { constructor(concurrency) { this.concurrency = concurrency; this.running = 0; this.queue = new Queue(); } pushTask(task) { return new Promise((resolve, reject) => { this.queue.enqueue({ task, resolve, reject }); this.runTask(); }); } runTask() { if (this.running >= this.concurrency || this.queue.isEmpty()) { return; } this.running++; const { task, resolve, reject } = this.queue.dequeue(); task() .then(resolve) .catch(reject) .finally(() => { this.running--; this.runTask(); }); } } // Пример использования const taskQueue = new TaskQueue(2); // Максимум 2 задачи одновременно function simulateAsyncTask(id, delay) { return new Promise(resolve => { setTimeout(() => { console.log(`Задача ${id} выполнена`); resolve(); }, delay); }); } taskQueue.pushTask(() => simulateAsyncTask(1, 2000)); taskQueue.pushTask(() => simulateAsyncTask(2, 1000)); taskQueue.pushTask(() => simulateAsyncTask(3, 3000)); taskQueue.pushTask(() => simulateAsyncTask(4, 1000)); В этом примере TaskQueue использует очередь для хранения задач и обеспечивает их выполнение с ограничением на количество одновременно выполняемых задач.
Обработка событий в браузере
JavaScript в браузере использует очередь событий для обработки пользовательских действий и других асинхронных операций. Понимание этого механизма помогает разработчикам создавать более эффективные и отзывчивые веб-приложения.
console.log("Начало скрипта"); setTimeout(() => { console.log("Таймер 1"); }, 0); Promise.resolve().then(() => { console.log("Промис 1"); }); setTimeout(() => { console.log("Таймер 2"); }, 0); Promise.resolve().then(() => { console.log("Промис 2"); }); console.log("Конец скрипта"); // Вывод: // Начало скрипта // Конец скрипта // Промис 1 // Промис 2 // Таймер 1 // Таймер 2 Этот пример демонстрирует, как очередь событий и очередь микрозадач работают в JavaScript. Промисы выполняются в очереди микрозадач, которая имеет приоритет над очередью макрозадач (таймеры, I/O операции и т.д.).
Оптимизация и производительность
При работе со стеками и очередями в JavaScript важно учитывать вопросы производительности, особенно при работе с большими объемами данных.
Оптимизация стека
Для оптимизации работы стека можно использовать объект вместо массива, что позволит избежать проблем с производительностью при работе с большими стеками.
class OptimizedStack { constructor() { this.count = 0; this.storage = {}; } push(value) { this.storage[this.count] = value; this.count++; } pop() { if (this.count === 0) { return undefined; } this.count--; const result = this.storage[this.count]; delete this.storage[this.count]; return result; } peek() { return this.storage[this.count - 1]; } size() { return this.count; } } Эта реализация обеспечивает константное время O(1) для операций push и pop, что делает ее более эффективной при работе с большими объемами данных.
Оптимизация очереди
Для очереди также можно использовать объект-хранилище вместо массива, чтобы избежать затратной операции shift().
class OptimizedQueue { constructor() { this.head = 0; this.tail = 0; this.storage = {}; } enqueue(value) { this.storage[this.tail] = value; this.tail++; } dequeue() { if (this.head === this.tail) { return undefined; } const result = this.storage[this.head]; delete this.storage[this.head]; this.head++; return result; } peek() { return this.storage[this.head]; } size() { return this.tail - this.head; } } Эта реализация обеспечивает константное время O(1) для операций enqueue и dequeue, что делает ее более эффективной при работе с большими очередями.
Измерение производительности
Для оценки производительности различных реализаций стека и очереди можно использовать встроенный объект Performance API в JavaScript.
function measurePerformance(dataStructure, operations, size) { const start = performance.now(); for (let i = 0; i < size; i++) { dataStructure.push(i); } for (let i = 0; i < size; i++) { dataStructure.pop(); } const end = performance.now(); console.log(`${operations} операций заняли ${end - start} миллисекунд`); } const arrayStack = []; const optimizedStack = new OptimizedStack(); measurePerformance(arrayStack, "Array Stack", 1000000); measurePerformance(optimizedStack, "Optimized Stack", 1000000); Этот код позволяет сравнить производительность различных реализаций и выбрать наиболее подходящую для конкретного сценария использования.
Стеки и очереди в алгоритмах
Стеки и очереди играют ключевую роль во многих алгоритмах. Рассмотрим несколько классических алгоритмов, где эти структуры данных особенно полезны.
Алгоритм обхода графа в глубину (DFS) с использованием стека
Алгоритм поиска в глубину (DFS) часто реализуется с использованием стека для хранения вершин, которые нужно посетить.
class Graph { constructor() { this.adjacencyList = {}; } addVertex(vertex) { if (!this.adjacencyList[vertex]) { this.adjacencyList[vertex] = []; } } addEdge(v1, v2) { this.adjacencyList[v1].push(v2); this.adjacencyList[v2].push(v1); } dFS(start) {
const stack = [start];
const result = [];
const visited = {};
visited[start] = true;
while (stack.length) {
const vertex = stack.pop();
result.push(vertex);
this.adjacencyList[vertex].forEach(neighbor => {
if (!visited[neighbor]) {
visited[neighbor] = true;
stack.push(neighbor);
}
});
}
return result;
}
}
// Пример использования
const graph = new Graph();
['A', 'B', 'C', 'D', 'E', 'F'].forEach(vertex => graph.addVertex(vertex));
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('B', 'D');
graph.addEdge('C', 'E');
graph.addEdge('D', 'E');
graph.addEdge('D', 'F');
graph.addEdge('E', 'F');
console.log(graph.DFS('A')); // ['A', 'C', 'E', 'F', 'D', 'B']
В этом примере стек используется для хранения вершин графа, которые нужно посетить. Алгоритм продолжает извлекать вершины из стека и исследовать их соседей, пока стек не опустеет.
Алгоритм обхода графа в ширину (BFS) с использованием очереди
Алгоритм поиска в ширину (BFS) обычно реализуется с использованием очереди для хранения вершин, которые нужно посетить.
class Graph { // ... (предыдущие методы остаются без изменений) BFS(start) { const queue = [start]; const result = []; const visited = {}; visited[start] = true; while (queue.length) { const vertex = queue.shift(); result.push(vertex); this.adjacencyList[vertex].forEach(neighbor => { if (!visited[neighbor]) { visited[neighbor] = true; queue.push(neighbor); } }); } return result; } } // Пример использования const graph = new Graph(); ['A', 'B', 'C', 'D', 'E', 'F'].forEach(vertex => graph.addVertex(vertex)); graph.addEdge('A', 'B'); graph.addEdge('A', 'C'); graph.addEdge('B', 'D'); graph.addEdge('C', 'E'); graph.addEdge('D', 'E'); graph.addEdge('D', 'F'); graph.addEdge('E', 'F'); console.log(graph.BFS('A')); // ['A', 'B', 'C', 'D', 'E', 'F'] В этом алгоритме очередь используется для обеспечения того, чтобы вершины обрабатывались в порядке их удаленности от начальной вершины.
Алгоритм Дейкстры с использованием приоритетной очереди
Алгоритм Дейкстры для поиска кратчайшего пути в графе часто реализуется с использованием приоритетной очереди для выбора следующей вершины с наименьшим расстоянием.
class PriorityQueue { constructor() { this.values = []; } enqueue(val, priority) { this.values.push({val, priority}); this.sort(); } dequeue() { return this.values.shift(); } sort() { this.values.sort((a, b) => a.priority - b.priority); } } class WeightedGraph { constructor() { this.adjacencyList = {}; } addVertex(vertex) { if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = []; } addEdge(vertex1, vertex2, weight) { this.adjacencyList[vertex1].push({node: vertex2, weight}); this.adjacencyList[vertex2].push({node: vertex1, weight}); } Dijkstra(start, finish) { const nodes = new PriorityQueue(); const distances = {}; const previous = {}; let path = []; let smallest; // Построение начального состояния for (let vertex in this.adjacencyList) { if (vertex === start) { distances[vertex] = 0; nodes.enqueue(vertex, 0); } else { distances[vertex] = Infinity; nodes.enqueue(vertex, Infinity); } previous[vertex] = null; } // Пока есть вершины для посещения while (nodes.values.length) { smallest = nodes.dequeue().val; if (smallest === finish) { // Построение пути while (previous[smallest]) { path.push(smallest); smallest = previous[smallest]; } break; } if (smallest || distances[smallest] !== Infinity) { for (let neighbor in this.adjacencyList[smallest]) { let nextNode = this.adjacencyList[smallest][neighbor]; let candidate = distances[smallest] + nextNode.weight; let nextNeighbor = nextNode.node; if (candidate < distances[nextNeighbor]) { distances[nextNeighbor] = candidate; previous[nextNeighbor] = smallest; nodes.enqueue(nextNeighbor, candidate); } } } } return path.concat(smallest).reverse(); } } // Пример использования const graph = new WeightedGraph(); graph.addVertex("A"); graph.addVertex("B"); graph.addVertex("C"); graph.addVertex("D"); graph.addVertex("E"); graph.addVertex("F"); graph.addEdge("A", "B", 4); graph.addEdge("A", "C", 2); graph.addEdge("B", "E", 3); graph.addEdge("C", "D", 2); graph.addEdge("C", "F", 4); graph.addEdge("D", "E", 3); graph.addEdge("D", "F", 1); graph.addEdge("E", "F", 1); console.log(graph.Dijkstra("A", "E")); // ["A", "C", "D", "F", "E"] В этом примере приоритетная очередь используется для эффективного выбора вершины с наименьшим расстоянием на каждом шаге алгоритма.
Стеки и очереди в контексте асинхронного программирования
В асинхронном программировании на JavaScript стеки и очереди играют важную роль в управлении порядком выполнения задач.
Event Loop и очередь задач
JavaScript использует модель Event Loop для обработки асинхронных операций. Event Loop использует несколько очередей для управления выполнением кода:
- Очередь задач (Task Queue) для макрозадач (setTimeout, setInterval, I/O операции)
- Очередь микрозадач (Microtask Queue) для микрозадач (Promise, queueMicrotask)
console.log('1'); setTimeout(() => { console.log('2'); }, 0); Promise.resolve().then(() => { console.log('3'); }); console.log('4'); // Вывод: 1, 4, 3, 2 В этом примере '3' выводится перед '2', несмотря на то, что setTimeout вызывается раньше. Это происходит потому, что промисы (микрозадачи) имеют приоритет над макрозадачами.
Реализация собственного планировщика задач
Можно реализовать простой планировщик задач, используя очередь и setTimeout:
class TaskScheduler { constructor() { this.queue = []; this.isRunning = false; } addTask(task) { this.queue.push(task); if (!this.isRunning) { this.runTasks(); } } runTasks() { if (this.queue.length === 0) { this.isRunning = false; return; } this.isRunning = true; const task = this.queue.shift(); setTimeout(() => { task(); this.runTasks(); }, 0); } } // Пример использования const scheduler = new TaskScheduler(); scheduler.addTask(() => console.log("Задача 1")); scheduler.addTask(() => console.log("Задача 2")); scheduler.addTask(() => console.log("Задача 3")); Этот планировщик использует очередь для хранения задач и setTimeout для асинхронного выполнения каждой задачи, что позволяет избежать блокировки основного потока выполнения.
Стеки и очереди в контексте функционального программирования
В функциональном программировании стеки и очереди часто реализуются как неизменяемые (immutable) структуры данных. Рассмотрим, как можно реализовать такие структуры в JavaScript.
Неизменяемый стек
class ImmutableStack { constructor(items = []) { this.items = items; } push(item) { return new ImmutableStack([...this.items, item]); } pop() { if (this.isEmpty()) { return this; } return new ImmutableStack(this.items.slice(0, -1)); } peek() { return this.isEmpty() ? undefined : this.items[this.items.length - 1]; } isEmpty() { return this.items.length === 0; } } // Пример использования let stack = new ImmutableStack(); stack = stack.push(1).push(2).push(3); console.log(stack.peek()); // 3 stack = stack.pop(); console.log(stack.peek()); // 2 В этой реализации каждая операция создает новый экземпляр стека, оставляя оригинальный стек неизменным.
Неизменяемая очередь
class ImmutableQueue { constructor(items = []) { this.items = items; } enqueue(item) { return new ImmutableQueue([...this.items, item]); } dequeue() { if (this.isEmpty()) { return this; } return new ImmutableQueue(this.items.slice(1)); } front() { return this.isEmpty() ? undefined : this.items[0]; } isEmpty() { return this.items.length === 0; } } // Пример использования let queue = new ImmutableQueue(); queue = queue.enqueue(1).enqueue(2).enqueue(3); console.log(queue.front()); // 1 queue = queue.dequeue(); console.log(queue.front()); // 2 Аналогично стеку, каждая операция с очередью создает новый экземпляр, сохраняя неизменность исходной структуры.
Заключение
Стеки и очереди являются фундаментальными структурами данных, которые находят широкое применение в различных областях программирования. В JavaScript эти структуры могут быть реализованы различными способами, каждый из которых имеет свои преимущества и недостатки в зависимости от конкретного сценария использования.
Ключевые моменты для запоминания:
- Стек работает по принципу LIFO (Last In, First Out), в то время как очередь следует принципу FIFO (First In, First Out).
- Обе структуры могут быть эффективно реализованы с использованием массивов или объектов в JavaScript.
- Стеки и очереди играют важную роль в различных алгоритмах, таких как обход графов и поиск кратчайшего пути.
- В асинхронном программировании на JavaScript концепции стеков и очередей используются в работе Event Loop и управлении задачами.
- Функциональное программирование предлагает подход к реализации неизменяемых версий этих структур данных.
Понимание принципов работы стеков и очередей, а также умение эффективно их применять, является важным навыком для любого разработчика JavaScript. Эти структуры данных не только помогают в решении алгоритмических задач, но и играют ключевую роль в понимании внутренних механизмов работы языка и среды выполнения JavaScript.
