Поиск

Списки и стеки

До сих пор мы рассматривали списки и массивы как линейные структуры данных, доступ к элементам которых осуществлялся с помощью индексов (рис. 9.3).

А теперь включите свое воображение и представьте себе этот массив элементов в виде вертикальной стопки (рис. 9.4).

В компьютерной терминологии подобная структура данных называется стеком. Стеки обычно используются там, где необходимо выполнить обработку элементов списка в определенном порядке. Хорошим примером использования стека могут служить компьютерные карточные игры. В них каждый расклад карт представляется в виде стека. Сначала карты в колоде расположены рубашкой вверх. По мере необходимости карты переворачиваются и извлекаются из колоды (т.е. из стека). Кроме того, при отбое отыгравшие карты складываются в верхнюю часть колоды.

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

Синтаксис перечисленных выше функций выглядит так:

Функции pop и shift удаляют один элемент из массива. Если параметр пассив не указан, то будет удален один элемент либо из массива i , либо из GARGV. Функции pop и shift возвращают в вызвавшую программу удаленный из массива элемент, а если массив пуст, то возвращается значение undef. При этом соответствующим образом уменьшается и размер массива.

Внутри подпрограмм функции pop, shift, unshift и push модифицируют переменную @ , если не указан другой массив. В теле главной программы эти функции модифицируют массив @ARGV, если не указан другой массив.

Функции push и unshift добавляют элементы нового списка в массив. При этом соответствующим образом увеличивается размер массива. Элементы нового_списка могут быть представлены в виде списка, массива или скаляра, как показано в следующем примере.

Операции добавления и удаления элементов массива с помощью функций push, pop, shift и unshift гораздо эффективнее аналогичных операций, выполненных вручную. Например, код push @list,@newitems эффективнее, чем @iist=(@1ist,@newitems). Перечисленные выше функции Perl специально оптимизированы для выполнения подобных операций над массивами.

При работе со стеком не стоит забывать и о том, что его элементы ничем не отличаются от элементов обычных массивов, которые можно адресовать с помощью индексов. При этом началу стека (или его нижней части) соответствует индекс 0, а вершине стека — последний элемент массива.

Слияние и разделение массивов

До сих пор мы ВЫПОЛНЯЛИ с массивами такие операции, как обращение к элементу по индексу, разделение массива на отдельные скаляры, а также всевозможные стековые манипуляции. Теперь пришла пора рассмотреть еще одну функцию — splice, с помощью которой можно выполнять как слияние, так и разделение массивов. Ее синтаксис выглядит так:

Функция splice удаляет из массива элементы, начиная с заданного смещения. При этом удаленные элементы возвращаются в вызывающую программу. Отрицательные значения смещения означают, что соответствующий элемент отсчитывается не с начала, а с конца массива. Если указан параметр длина, то - удаляется указанное количество элементов массива. Если указан параметр список, то после удаления указанного количества элементов вместо них в массив помещаются элементы из списка. Во время выполнения подобных операций размер массива соответствующим образом уменьшается или увеличивается. Вот несколько примеров: