Мы уже рассмотрели базовые структуры данных такие как массивы и связанные списки, теперь можем глянуть как на их основе строятся другие, но для начала чуток терминологии:
1) Стэк - структура данных, основанная на принципе LIFO (last in first out), то есть значения добавляются в конец, извлекаются тоже с конца.
2) Очередь - структура данных, основанная на принципе FIFO (first in first out), то есть значения добавляются в конец, а извлекаются с начала. Есть еще очереди с приоритетом, но это немного другая история.
Давайте попробуем построить стэк с помощью динамического массива и связанного списка:
// реализация стэка на динамическом массиве
val stack1 = ArrayList<String>()
// добавляем значение в конец стэка
stack1.add(10)
stack1.add(20)
// извлекаем значение с конца стэка
stack1.removeLast()
// реализация стэка на связанном списке
val stack2 = LinkedList<String>()
stack2.add(10)
stack2.add(20)
stack2.removeLast()
Для очереди практически то же самое:
// реализация очереди на динамическом массиве
val queue1 = ArrayList<String>()
// добавляем значение в конец очереди
queue1.add(10)
queue1.add(20)
// извлекаем значение с начала очереди
queue1.removeFirst()
// реализация очереди на связанном списке
val queue2 = LinkedList<String>()
queue2.add(10)
queue2.add(20)
queue2.removeFirst()
Обе реализации практически идентичны, разве что в динамическом массиве при удалении происходит сдвиг всего массива, а в связанном списке удаляется только ссылка, поэтому в скорости однозначно выигрывает связанный список, особенно это отражается на очередях, где должен извлекаться первый элемент.
Всех с выпавшим снегом, хотя может у вас снега нет, короче хорошего кода!