Алгоритмы, вторая неделя - "Стеки и очереди"
К сожалению, в последнее время мало было возможности писать, да ещё и компьютер домашний сломался, но постараюсь всё же дописать эту серию постов. Сегодня речь пойдёт о стеках, очередях, коллекциях и о том, как это реализуется.
Впервые с этой темой я познакомился во втором семестре первого курса на практикумах по программированию. Препод у нас был хороший, готовил хорошие материалы, беда только в том, что он был нетребовательный, иначе говоря, программирование у нас считался халявным предметом. Первый семестр я занимался очень хорошо и наверное, это способствовало тому, что одним из немногих своих одногруппников я до сих пор этим интересуюсь и регулярно программирую. А вот во втором семестре начал расслабляться и я и поэтому тема про стеки и подобные им алгоритмические конструкции как-то прошла мимо меня...
Что из себя представляет стек? Стек - это один из способов хранения группы объектов одного типа. Один из способов его представления - через связанный список. В этом случае стек представляет из себя структуру или класс, одним из полей которого является ссылка на объект этого же типа. Таким образом, первый объект содержит ссылку на второй, второй - на третий, третий - на четвёртый и т.д. Стек поддерживает несколько операций: 1) добавление нового элемента; 2) удаление элемента; 3) проверка на пустоту. Получить произвольный элемент из стека невозможно - для этого нужно итерировать по всем элементам (речь об этом пойдёт дальше). Стек подчиняется принципу LIFO - "last in, first out", что означает, что удаляемый (извлекаемый) из стека элемент является в нём самым новым (наиболее недавно добавленным). Например, если в стек поочерёдно добавлять числа 1, 2, 3, 4, 5, а потом 5 раз вызвать операцию извлечения (удаления), то порядок будет обратным : 5, 4, 3, 2, 1.
Другой способ реализации стека - через массив. Это довольно простой способ: надо всего лишь добавлять новые элементы в конец массива, извлекать элементы из конца массива и при необходимости менять размер массива. Но как менять размер массива? Если менять его после каждой операции добавления/извлечения, то это будет довольно затратно по отношению к времени выполнения - каждый раз при создании нового массива нужно будет постоянно копировать элементы туда-сюда. Оценка показывает, что затраченное время будет пропорционально количеству элементов в стеке во второй степени, что, как известно, плохо (кажется, я уже писал, что квадратичная сложность - это плохо). Был найден довольно изящный способ избежать этого: если добавляемый элемент оказывается в конце массива, то следует создать новый массив размером в два раза больше старого; если же после удаления очередного элемента количество элементов в массиве составляет одну четверть от его размера, то массив следует уменьшить в два раза. Это решение хорошо тем, что время, потраченное на последовательность добавлений/извлечений некоторого количества элементов, будет пропорционально этому количеству в первой степени.
Отличие очередей от стеков заключается только в том, что операция извлечения применяется к элементу, который был добавлен самым первым. Например, если в очередь добавлять числа 1, 2, 3, 4, 5, а потом 5 раз применить операцию извлечения, то порядок останется таким же: 1, 2, 3, 4, 5. Реализация с помощью связанного списка отличается только тем, что надо хранить ещё и ссылку на последний элемент в очереди - это сложнее, но ненамного. Реализация с помощью массива тоже имеет некоторые отличия, но не очень существенные.
Для получения произвольного элемента из стека/очереди нужно реализовать поддержку итераций. На языке Java это делается с помощью реализации интерфейса Iterable. В этом интерфейсе нужно реализовать две функции: hasNext и Next. Первая из них проверяет, есть ли ещё объекты после данного, вторая просто возвращает следующий (ненулевой) объект.
О применении - стеки и очереди применяются при создании списков и коллекций во многих стандартных библиотеках. Списки - очень удобная вещь, я люблю ими пользоваться и прежде даже злоупотреблял их использованием (в этой лекции рассказывалось, что они работают медленнее, чем обычные массивы), но благодаря этой лекции понял, что делать это нужно избирательно, хотя и до этого подозрения об их "медленности" у меня уже были.
Другие известные применения - разработка компиляторов, распознавание арифметических выражений (правильное определение порядков операций и операндов), вычисление рекурсивных функций и т.д.
Впервые с этой темой я познакомился во втором семестре первого курса на практикумах по программированию. Препод у нас был хороший, готовил хорошие материалы, беда только в том, что он был нетребовательный, иначе говоря, программирование у нас считался халявным предметом. Первый семестр я занимался очень хорошо и наверное, это способствовало тому, что одним из немногих своих одногруппников я до сих пор этим интересуюсь и регулярно программирую. А вот во втором семестре начал расслабляться и я и поэтому тема про стеки и подобные им алгоритмические конструкции как-то прошла мимо меня...
Что из себя представляет стек? Стек - это один из способов хранения группы объектов одного типа. Один из способов его представления - через связанный список. В этом случае стек представляет из себя структуру или класс, одним из полей которого является ссылка на объект этого же типа. Таким образом, первый объект содержит ссылку на второй, второй - на третий, третий - на четвёртый и т.д. Стек поддерживает несколько операций: 1) добавление нового элемента; 2) удаление элемента; 3) проверка на пустоту. Получить произвольный элемент из стека невозможно - для этого нужно итерировать по всем элементам (речь об этом пойдёт дальше). Стек подчиняется принципу LIFO - "last in, first out", что означает, что удаляемый (извлекаемый) из стека элемент является в нём самым новым (наиболее недавно добавленным). Например, если в стек поочерёдно добавлять числа 1, 2, 3, 4, 5, а потом 5 раз вызвать операцию извлечения (удаления), то порядок будет обратным : 5, 4, 3, 2, 1.
Другой способ реализации стека - через массив. Это довольно простой способ: надо всего лишь добавлять новые элементы в конец массива, извлекать элементы из конца массива и при необходимости менять размер массива. Но как менять размер массива? Если менять его после каждой операции добавления/извлечения, то это будет довольно затратно по отношению к времени выполнения - каждый раз при создании нового массива нужно будет постоянно копировать элементы туда-сюда. Оценка показывает, что затраченное время будет пропорционально количеству элементов в стеке во второй степени, что, как известно, плохо (кажется, я уже писал, что квадратичная сложность - это плохо). Был найден довольно изящный способ избежать этого: если добавляемый элемент оказывается в конце массива, то следует создать новый массив размером в два раза больше старого; если же после удаления очередного элемента количество элементов в массиве составляет одну четверть от его размера, то массив следует уменьшить в два раза. Это решение хорошо тем, что время, потраченное на последовательность добавлений/извлечений некоторого количества элементов, будет пропорционально этому количеству в первой степени.
Отличие очередей от стеков заключается только в том, что операция извлечения применяется к элементу, который был добавлен самым первым. Например, если в очередь добавлять числа 1, 2, 3, 4, 5, а потом 5 раз применить операцию извлечения, то порядок останется таким же: 1, 2, 3, 4, 5. Реализация с помощью связанного списка отличается только тем, что надо хранить ещё и ссылку на последний элемент в очереди - это сложнее, но ненамного. Реализация с помощью массива тоже имеет некоторые отличия, но не очень существенные.
Для получения произвольного элемента из стека/очереди нужно реализовать поддержку итераций. На языке Java это делается с помощью реализации интерфейса Iterable. В этом интерфейсе нужно реализовать две функции: hasNext и Next. Первая из них проверяет, есть ли ещё объекты после данного, вторая просто возвращает следующий (ненулевой) объект.
О применении - стеки и очереди применяются при создании списков и коллекций во многих стандартных библиотеках. Списки - очень удобная вещь, я люблю ими пользоваться и прежде даже злоупотреблял их использованием (в этой лекции рассказывалось, что они работают медленнее, чем обычные массивы), но благодаря этой лекции понял, что делать это нужно избирательно, хотя и до этого подозрения об их "медленности" у меня уже были.
Другие известные применения - разработка компиляторов, распознавание арифметических выражений (правильное определение порядков операций и операндов), вычисление рекурсивных функций и т.д.