Стеки и очереди часто обучаются на одном дыхании. Они представляют собой относительно простую структуру данных, для работы каждой из которых по определению требуется только два метода. Нам нужен способ что-то вставить, а затем что-то вынуть.
Несколько реальных примеров этих структур данных:
Куча:
Куча тарелок в кафетерии. Когда вы вынимаете блюдо из стопки, вы собираетесь взять блюдо сверху (так как удаление снизу вызовет беспорядок). Это означает, что последняя добавленная в стопку пластина удаляется первой. Это означает, что стек работает по принципу LIFO.
Последний
In
Первый
Вне
Очереди:
Если вы когда-либо ждали в очереди, вы были узлом в очереди. Думаю, кассовая линия. Первым в очереди будет тот, кого обслужат первым. Если вы недавно присоединились к очереди и стали пятым, вам нужно дождаться обслуживания четырех человек впереди вас. К счастью, очереди (и линии) работают по принципу FIFO.
Первый
In
Первый
Вне
Давайте закодируем класс стека
Выше показан план, с которого мы можем начать работу с нашей структурой данных Stack. По своей сути стек - это особый вариант односвязного списка. У нас просто будут методы для добавления и удаления в / из вершины стека.
Начнем с add(), так как вы не можете remove() из пустого Stack
add() Псевдокод:
// определяем функцию с именем add; он принимает value в качестве аргумента
// создаёт новый Node, используя переданное значение
// если стек пуст; установите first и last на новый узел
// иначе; сохранить this.first в переменную, затем повторно назначить this.first нашему новому Node
// новый Node должен указывать на наш oldFirst
// увеличить size стека
// return size стека
В приведенном выше псевдокоде мы создаем стек, который будет добавляться и удаляться с вершины (this.first) стека. * Помните, что односвязные списки не очень хороши для удаления из конца списка, поскольку у нас нет предыдущего свойства, чтобы легко получить предпоследний узел (который стал бы нашим новым хвостом). Добавление и удаление сверху (this.first) позволяет нам делать это за постоянное время.
Пока мы занимаемся этим, давайте обработаем псевдокод remove()
remove() Псевдокод:
// определяем функцию с именем remove(); не принимает аргументов
// если стек пуст; return null
// присваиваем first элемент в стеке переменной
// если в стеке только один элемент; установить this.last на null
// затем переназначить this.first на oldFirst.next
// уменьшить size
// return value из oldFirst
Здесь мы также убеждаемся, что удаляемся в постоянное время. Нам нужно убедиться, что, если мы очищаем список, мы также удаляем соединение с this.last.
Вот моя реализация:
Аналогичным образом, для очередей нужен только метод для добавления и удаления из очереди. Разница в том, что очереди нужно add() до конца и убирать с начала. Это обеспечит использование упомянутой выше методологии LIFO.
Давайте составим наш план для класса Queue
Давайте поговорим о наших add() и remove() методах
add() Псевдокод:
// определяем функцию с именем add(); он принимает значение в качестве аргумента
// создаёт новый Node, используя значение, переданное в
// если Queue пусто, устанавливает this.first и this.last в наш новый Node
// otherwise add the new Node to the end of our list
remove() Псевдокод:
// определяем функцию с именем remove(); не принимает аргументов
// если queue пусто; return null
// сохраняем oldFirst в переменной
// если есть только один узел в очереди, устанавливаем this.last в ноль
// устанавливаем this.first на следующий node в очереди
// уменьшаем size очереди
// возвращаем oldFirst.val
Наша очередь добавляется в конец списка (this.last) и удаляется с начала queue. Это соответствует нашей методологии FIFO.
Вот моя реализация:
Очереди и стеки - это простые структуры с некоторыми базовыми функциями, но они будут использоваться как компонент для других более крупных и сложных структур данных. Если вы хотите узнать о них больше, в ближайшие недели я дам ссылки на другие статьи о них.
