Как реализовать стек и очередь на JavaScript?

В JavaScript для работы с массивами, как стеком (Stack) и очередью (Queue), можно использовать встроенные методы массивов. Вот примеры, иллюстрирующие, как это сделать.

Стек (Stack)

Стек — это структура данных, работающая по принципу "последний пришёл — первый вышел" (LIFO). Для реализации стека можно использовать методы push и pop:

var stack = [];

// Добавляем значение на вершину стека
stack.push(1);

// Удаляем значение с вершины стека
var value = stack.pop();

В этом примере мы добавляем значение 1 в стек с помощью метода push. Затем мы извлекаем его с помощью метода pop, который удаляет последний добавленный элемент и возвращает его.

Очередь (Queue)

Очередь — это структура данных, работающая по принципу "первый пришёл — первый вышел" (FIFO). Для реализации очереди можно использовать метод push для добавления и shift для удаления первого элемента:

var queue = [];

// Добавляем значение в конец очереди
queue.push(1);

// Извлекаем первое значение из очереди
var value = queue.shift();

Здесь мы добавляем значение 1 в конец очереди методом push. Затем мы извлекаем его с помощью метода shift, который удаляет первый элемент очереди и возвращает его.

Таким образом, с помощью метода push можно добавлять элементы в обе структуры данных, а команды pop и shift используются для извлечения элементов в разных порядках.

JavaScript имеет методы push и pop, которые работают с обычными массивами.

Для реализации очередей можно воспользоваться следующими методами:

http://safalra.com/web-design/javascript/queues/

Очереди можно реализовать в JavaScript, используя методы push и shift или unshift и pop объекта массива. Хотя это простой способ реализации очередей, он очень неэффективен для больших очередей — поскольку эти методы работают с массивами, каждый вызов shift и unshift перемещает все элементы массива.

Queue.js — это простая и эффективная реализация очереди в JavaScript, функция dequeue которой работает за амортизированное постоянное время. В результате, для больших очередей она может значительно превосходить по скорости использование массивов.

Если вы хотите создать свои собственные структуры данных, вы можете реализовать стек и очередь следующим образом:

Для стека:

var Stack = function() {
  this.top = null; // указатель на верхний элемент стека
  this.size = 0;   // размер стека
};

var Node = function(data) {
  this.data = data; // данные узла
  this.previous = null; // указатель на предыдущий узел
};

Stack.prototype.push = function(data) {
  var node = new Node(data); // создаем новый узел с переданными данными

  node.previous = this.top; // новый узел указывает на текущий верхний узел
  this.top = node; // обновляем верхний узел
  this.size += 1; // увеличиваем размер стека
  return this.top; // возвращаем новый верхний узел
};

Stack.prototype.pop = function() {
  var temp = this.top; // временная переменная для текущего верхнего узла
  this.top = this.top.previous; // обновляем верхний узел
  this.size -= 1; // уменьшаем размер стека
  return temp; // возвращаем удаленный узел
};

А для очереди:

var Queue = function() {
  this.first = null; // указатель на первый элемент очереди
  this.size = 0;     // размер очереди
};

var Node = function(data) {
  this.data = data; // данные узла
  this.next = null; // указатель на следующий узел
};

Queue.prototype.enqueue = function(data) {
  var node = new Node(data); // создаем новый узел с переданными данными

  if (!this.first) { // если очередь пуста
    this.first = node; // помещаем узел как первый
  } else {
    var n = this.first; // начинаем с первого узла
    while (n.next) { // пока есть следующий узел
      n = n.next; // продолжаем перемещение по узлам
    }
    n.next = node; // добавляем новый узел в конец очереди
  }

  this.size += 1; // увеличиваем размер очереди
  return node; // возвращаем добавленный узел
};

Queue.prototype.dequeue = function() {
  var temp = this.first; // временная переменная для первого узла
  this.first = this.first.next; // обновляем указатель на первый узел
  this.size -= 1; // уменьшаем размер очереди
  return temp; // возвращаем удаленный узел
};

Эти примеры показывают, как можно реализовать основные операции для стека (push и pop) и очереди (enqueue и dequeue) с использованием JavaScript. Вы можете использовать эти структуры данных в своих приложениях для управления данными.

Вот моя реализация стека и очереди с использованием связного списка:

// Связный список
function Node(data) {
  this.data = data;
  this.next = null;
}

// Стек, реализованный с помощью связного списка
function Stack() {
  this.top = null;
}

Stack.prototype.push = function(data) {
  var newNode = new Node(data);

  newNode.next = this.top; // Особое внимание
  this.top = newNode;
}

Stack.prototype.pop = function() {
  if (this.top !== null) {
    var topItem = this.top.data;
    this.top = this.top.next;
    return topItem;
  }
  return null; // Возвращает null, если стек пуст
}

Stack.prototype.print = function() {
  var curr = this.top;
  while (curr) {
    console.log(curr.data);
    curr = curr.next;
  }
}

// var stack = new Stack();
// stack.push(3);
// stack.push(5);
// stack.push(7);
// stack.print();

// Очередь, реализованная с помощью связного списка
function Queue() {
  this.head = null;
  this.tail = null;
}

Queue.prototype.enqueue = function(data) {
  var newNode = new Node(data);

  if (this.head === null) {
    this.head = newNode;
    this.tail = newNode;
  } else {
    this.tail.next = newNode;
    this.tail = newNode;
  }
}

Queue.prototype.dequeue = function() {
  var newNode;
  if (this.head !== null) {
    newNode = this.head.data;
    this.head = this.head.next;
  }
  return newNode; // Возвращает данные из головы очереди
}

Queue.prototype.print = function() {
  var curr = this.head;
  while (curr) {
    console.log(curr.data);
    curr = curr.next;
  }
}

var queue = new Queue();
queue.enqueue(3);
queue.enqueue(5);
queue.enqueue(7);
queue.print();
queue.dequeue();
queue.dequeue();
queue.print();

В этой реализации сте́ка используется свойство top, которое указывает на верхний элемент стека. Методы push и pop позволяют добавлять и удалять элементы. В очередь добавлены методы enqueue и dequeue, которые управляют вставкой и удалением элементов соответственно. Обе структуры используют связный список для хранения элементов, что позволяет гибко управлять памятью.

Вопрос: "Почему метод shift() у массивов в JavaScript медленный, особенно когда массив содержит много элементов? Есть ли способы реализовать очередь с амортизированной сложностью O(1)?"

Ответ: Да, вы правы, метод shift() массива в JavaScript действительно имеет линейную сложность O(n), что делает его неэффективным при работе с большими наборами данных. Я знаю два способа реализации очереди с амортизированной сложностью O(1).

Первый способ - использовать кольцевой буфер и удвоение массива. Я реализовывал это ранее, и вы можете ознакомиться с моим исходным кодом здесь: rapid-queue на GitHub.

Второй способ - использование двух стеков. Вот пример кода для реализации очереди с помощью двух стеков:

function createDoubleStackQueue() {
    var that = {};
    var pushContainer = [];
    var popContainer = [];

    function moveElementToPopContainer() {
        while (pushContainer.length !== 0) {
            var element = pushContainer.pop();
            popContainer.push(element);
        }
    }

    that.push = function(element) {
        pushContainer.push(element);
    };

    that.shift = function() {
        if (popContainer.length === 0) {
            moveElementToPopContainer();
        }
        if (popContainer.length === 0) {
            return null;
        } else {
            return popContainer.pop();
        }
    };

    that.front = function() {
        if (popContainer.length === 0) {
            moveElementToPopContainer();
        }
        if (popContainer.length === 0) {
            return null;
        }
        return popContainer[popContainer.length - 1];
    };

    that.length = function() {
        return pushContainer.length + popContainer.length;
    };

    that.isEmpty = function() {
        return (pushContainer.length + popContainer.length) === 0;
    };

    return that;
}

Я также провел сравнительное тестирование производительности с использованием jsPerf:

Сравнение CircularQueue.shift() с Array.shift(): jsPerf.

Как видно из результатов, использование двух стеков или кольцевого буфера значительно увеличивает скорость при работе с большими наборами данных.