Глава 14. Структуры данных

Коротко

Наиболее существенная вещь, отсутствовавшая в Perl до появления пятой версии, — это поддержка сложных структур данных (не было даже многомерных массивов, не говоря уже о более сложных структурах). Следствие этого, невозможность использования в массивах более одного индекса, была одной из самых ощутимых потерь для программистов. В прежние времена приходилось имитировать многомерные массивы способом, который хоть и не выглядел таким уж неуклюжим, но не становился от этого эффективнее. Индексы рассматривались, как текстовые строки (ключи хешей), и объединялись в один ключ. Вот, например, имитация «двумерного массива»:

for $outerloop (0..4) {

   for $innerloop (0..4) {

      $array{"$outerloop,$innerloop"} = 1;

   }

}

После создания подобной структуры данных для доступа к элементу такого «массива» требовалось передать конкатенацию индексов:

print $array{'0,0’};

1

Теперь Perl включает существенную поддержку структур данных, в том числе и многомерных массивов, поэтому тот же код можно записать как

for $outerloop (0..4) {

   for $innerloop (0..4) {

      $array[$outerloop][$innerloop] = 1;

   }

}

print $array[0][0];

1

Однако эта конструкция тоже более хитроумна, чем может показаться. Массивы и хеши Perl по-прежнему по существу одномерны. Поэтому на самом деле приведенная конструкция — это одномерный массив из ссылок, ссылающихся на другие одномерные массивы. То, что Perl позволяет опускать между парами скобок (квадратных или фигурных, но не круглых) оператор разыменования ссылки -> делает возможной запись массива «как бы» в двумерном виде — конструкция $array[$i][$j] совпадает с $array[$i]->[$j]. Однако необходимо помнить, что на самом деле это все-таки массив ссылок. Например, если вы попробуете выполнить команду print @array, то не увидите элементов двумерного массива. Вместо этого Perl напечатает шестнадцатеричные ссылки на другие одномерные массивы:

ARRAY(0x8a56e4)ARRAY(0x8a578c)

ARRAY(0x8a58d0)ARRAY(0x8a5924)

ARRAY(0x8a5978)

Поскольку двумерный массив — это массив из ссылок на одномерные массивы, его можно создать с помощью генератора анонимных массивов — пары квадратных скобок:

$array[0] = ["apples", "oranges"];

$array[1] = ["asparagus", "corn", "peas"];

$array[2] = ["ham", "chicken"];

print $array[1][1];

corn

Вот другой способ создания аналогичного массива, при котором массив сразу инициализируется списком, состоящим из ссылок на массивы:

@array = (

   ["apples", "oranges"],

   ["asparagus", "corn", "peas"],

   ["ham", "chicken"]

);

print $array[1][1];

corn

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

$array = [

   ["apples", "oranges"],

   ["asparagus", "corn", "peas"],

   ["ham", "chicken"]

];

print $array->[1][1];

corn

Кроме запоминания ссылок на анонимные массивы в некотором массиве, при создании двумерного массива можно использовать и такой код:

@{$array[0]} = ("apples", "oranges");

@{$array[1]} = ("asparagus", "corn", "peas");

@{$array[2]} = ("ham", "chicken");

print $array[1][1];

corn

Конструкция @{$array[0]} обрабатывается достаточно хитро: Perl знает, что конструкция @{...} означает разыменование ссылки на массив. Однако, поскольку ссылки $array[0] не существует, Perl создает ее, заполняет элементами списка, стоящего в правой части оператора присваивания (еще один пример задействованной в Perl стратегии автооживления), а значение ссылки заносит в переменную $array[0]. То же самое происходит с $array[1] и $array[2]. В результате создается двумерный массив, (то есть массив из ссылок на массивы). Обратите внимание, что с такой нотацией следует быть осторожным: если $array[0] существует в момент исполнения кода, все, на что он указывает, будет потеряно и замещено новыми данными.

После создания массива на его элементы можно ссылаться с помощью индексов:

@array = (

   ["apples", "oranges"],

   ["asparagus", "corn", "peas"],

   ["ham", "chicken"]

);

for $outerloop (0..$#array) {

   for $innerloop (0..$#{array[$outer]}) {

      print $array[$outerloop][$innerloop], " ";

   }

   print "\n";

}

apples oranges

asparagus corn peas

ham chicken

Методы работы с одномерными массивами по-прежнему действуют. Иногда это упрощает обращение к двумерных массивам. Вот, например, как с помощью индекса цикла и функции join распечатать двумерный массив, последовательно выводя одномерные массивы (обратите внимание, как используется конструкцию @{} для разыменования ссылок на массивы):

@array = (

   ["apples", "oranges"],

   ["asparagus", "corn", "peas"],

   ["ham", "chicken"]

);

for $loopindex (0..$#array) {

   print join(", ", @{$array[$loopindex]}), "\n";

}

apples, oranges

asparagus, corn, peas

ham, chicken

Следует запомнить одно, — в подобных ситуациях код всегда работает с массивом массивов, и этот факт является ключом ко всем структурам данных, обсуждающимся в этой главе. Они основаны на ссылках и не являются фундаментальными типами данных Perl.

Подсказка: используйте команду use strict vars

Иногда создание структур данных и разборка используемых при этом ссылок — процесс запутанный. Крайне полезной здесь оказывается прагма use strict vars. Допустим, например, что в результате ошибки вместо круглых скобок в коде оказались квадратные:

use strict vars;

$array = [

   ["apples", "oranges"],

   ["asparagus", "corn", "peas"],

   ["ham", "chicken"]

];

print $array[0][0];

Интерпретатор Perl при компиляции сценария сообщит об ошибке при обработке последней строки, потому что в ней неявно вызывается еще не описанная переменная @array. Эта ошибка напоминает, что надо либо заменить квадратные скобки на круглые, либо использовать $array как ссылку:

print $array->[0][0];

(Если же во второй строке вместо префикса $ использовать @, то переменной @array будет присвоен массив, состоящий из одного элемента — ссылки на анонимный массив. Формально ошибки в сценарии не будет, но при выводе вместо элемента массива вы получите шестнадцатеричное значение указателя.)

Помимо массива массивов и хеша хешей, можно создавать смешанные типы — например, массивы хешей, и т. д.:

$array[1][2]       # массив массивов

$hash{key1}{key2}   # хеш-таблица из хеш-таблиц

$array[3]{key}   # массив хеш-таблиц

$hash{key}[4]          # хеш-таблица массивов

Как эти, так и другие смешанные типы данных рассматриваются далее в основной части главы.

Непосредственные решения

Сложные записи: хранение ссылок и других элементов

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

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

string = "Here is a string";

@array = (1, 2, 3);

%hash = ('fruit’ => ’apples’, ’vegetables’ => ’corn’);

sub printem

{

   print shift;

}

$complex = {

   string          =>   $string,

   number       =>  3.1415926,

   array           =>  [@array],

   hash           =>  {%hash},

   arrayreference   =>  \@array,

   hashreference   =>  \%hash,

   sub             =>  \&printem,

   ananymoussub  =>  sub {print shift;},

   handle         =>  \*STDOUT

};

print $complex->{string}, "\n";

print $complex->{number}, "\n";

print $complex->{array}[0], "\n";

print $complex->{hash}{fruit}, "\n";

print ${$complex->{arrayreference}}[0], "\n";

print ${$complex->{hashreference}}{fruit}, "\n";

$complex->{sub}->("Subroutine call.\n";

$complex->{anonymoussub}->{"Anonymous subroutine.\n";

print {$complex->{handle}} "Printed Text.", "\n";

Here is a string.

3.1415926

1

apples

1

apples

Subroutine call.

Anonymous subroutine.

Printed text.

Объявление массива массивов

Массивы массивов (а также массивы массивов массивов, и т. д.) заменяют в Perl многомерные массивы данных. Такие структуры ценны тем, что данные упорядочиваются по нескольким индексам — например, массив имен студентов будет индексироваться идентификатором ID и порядковым номером группы. Вот наиболее распространенный способ объявления массива массивов в одном предложении (обратите внимание, что для многомерный массив объявляется с помощью генератора анонимного массива):

@array = (

   ["apples", "oranges"],

   ["asparagus", "corn", "peas"],

   ["ham", "chicken"]

);

Создание массива массивов «на лету»

Массив массивов создается фрагмент за фрагментом с помощью генератора анонимного массива [...]. Он будет заполнять элементы массива более низкими по уровню иерархии ссылками на одномерные массивы:

$array[0] = ["apples", "oranges"];

$array[1] = ["asparagus", "corn", "peas"];

$array[2] = ["ham", "chicken"];

print $array[1][1];

corn

Вы можете добиться того же результата, используя «привычку» Perl создавать ссылки самостоятельно (см. обсуждение в начале этой главы):

@{$array[0]} = ("apples", "oranges");

@{$array[1]} = ("asparagus", "corn", "peas");

@{$array[2]} = ("ham", "chicken");

print $array[1][1];

corn

Ну и, естественно, можно создавать и заполнять массив массивов элемент за элементом:

for $outerloop (0..4) {

   for $innerloop (0..4) {

      $array[$outerloop][$innerloop] = 1;

   }

}

print $array[0][0];

1

Кроме того, функциа push позволяет заносить в главный массив очередную ссылку:

for $outerloop (0..4) {

   push $array, [1, 1, 1, 1, 1];

}

print $array[0][0];

1

В следующем примере для создания массива массивов используется список, возвращаемый подпрограммой, и генератор анонимного массива:

for $loopindex (0..4) {

   $array[$loopindex] = [&zerolist];

}

sub zerolist

{

   return (0, 0, 0, 0, 0);

}

print $array[0][0];

0

К массиву массивов всегда можно добавить новую строку:

@array = (

   ["apples", "oranges"],

   ["asparagus", "corn", "peas"],

   ["ham", "chicken"]

);

$array[3] = ["chicken noodle", "chili"];

print $array[3][0];

chicken noodle

Или, если вы предпочитаете добавлять элементы в уже существующую строку массива, можно сделать так:

@array = (

   ["apples", "oranges"],

   ["asparagus", "corn", "peas"],

   ["ham", "chicken"]

);

push @{$array[0]}, "banana";

print $array[0][2];

banana

Наконец, с помощью функции splice можно добавлять, заменять и удалять строки с произвольным номером:

# добавить строку перед строкой с индексом 1:

@array = (

   ["apples", "oranges"],

   ["asparagus", "corn", "peas"],

   ["ham", "chicken"]

);

splice @array, 1 ,0 , ["chess", "checkers", "go"];

print $array[0][0], ", ", $array[1][0], ", ", $array[2][0];

apples, chess, asparagus

# заменить две строки на одну:

@array = (

   ["apples", "oranges"],

   ["asparagus", "corn", "peas"],

   ["ham", "chicken"]

);

splice @array, 0 ,2 , ["chess", "checkers", "go"];

print $array[0][0], ", ", $array[1][0];

chess, ham

# заменить одну строку на две:

@array = (

   ["apples", "oranges"],

   ["asparagus", "corn", "peas"],

   ["ham", "chicken"]

);

splice @array, 0 ,1 , ["chess", "checkers", "go"],

                       ["cat", "dog", "mouse"];

print $array[0][0], ", ", $array[1][0], ", ", $array[1][0];

chess, cat, asparagus

# удалить среднюю строку:

@array = (

   ["apples", "oranges"],

   ["asparagus", "corn", "peas"],

   ["ham", "chicken"]

);

splice @array, 1 ,0;

print $array[0][0], ", ", $array[1][0];

apples, ham

Естественно, то же самое можно проделывать и с элементами строки, то есть добавлять их, заменять и удалять в режиме прямого доступа.

Доступ к элементам массива массивов

Вы можете выполнять доступ к массиву массивов поэлементно:

for $outerloop (0..4) {

   for $innerloop (0..4) {

      $array[$outerloop][$innerloop] = 1;

   }

}

print $array[0][0];

1

Можно также использовать мощь операторов и функций Perl, предназначенных для работы с одномерными массивами, чтобы облегчить работу с многомерными массивами. Например, в следующем примере (приведенном также в начале главы) функция join объединяет несколько элементов в текстовую строку:

@array = (

   ["apples", "oranges"],

   ["asparagus", "corn", "peas"],

   ["ham", "chicken"]

);

for $arrayref (@array) {

   print join(", ", @{$arrayref}), "\n";

}

apples, oranges

asparagus, corn, peas

ham, chicken

Объявление хеша хешей

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

%hash = (

    fruits => {

                     favorite => "apples",

                     'second favorite’ => "oranges"

         },

    vegetables => {

                     favorite => "corn",

                     'second favorite’ => "peas",

                     'least favorite’ => "turnip"

         },

    meat => {

                     favorite => "chicken",

                     'second favorite’ => "beef"

         }

);

print $hash{fruits}{favorite};

apples

Обратите внимание, что в таком хеше значениями для пар ключ/значение выступают другие хеши (точнее, ссылки на них). Кроме того, для конструкций типа {...}{...}, как и используемых в случае массива массивов конструкций вида [...][[...], между парами фигурных скобок неявно подставляется оператор-стрелка -> разыменования ссылок.

Создание хеша хешей «на лету»

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

%hash{fruits} = {favorite => "apples",

           'second favorite’ => "oranges"};

%hash{vegetables} = {favorite => "corn",

                 'second favorite’ => "peas",

                 'least favorite’ => "turnip"};

%hash{meat} = {favorite => "chicken",

           'second favorite’ => "beef"};

print $hash{fruits}{favorite};

apples

В следующей схеме генератор анонимного хеша комбинируется со списком ключ/значение, возвращаемыи внешней подпрограммой:

for $key ("hash1", "hash2", "hash3") {

   $hash{$key} = {$retutrnlist};

}

sub returnlist

{

   return (key1 => value1, key2 => value2);

}

print $hash{hash1}{key2};

value2

Доступ к элементам хеша хешей

Чтобы получить отдельное значение, хранящееся в хеше хешей, надо явно указать набор последовательных ключей:

%hash = (

    fruits => {favorite => "apples",

           'second favorite’ => "oranges"},

    vegetables => {favorite => "corn",

           'second favorite’ => "peas",

           'least favorite’ => "turnip"}

);

print $hash{fruits}{’second favorite’};

oranges

Используя стандартные приемы работы с обычными хешами, можно организовать цикл по элементам хеша хешей:

%hash = (

    fruits => {favorite => "apples",

                 second => "oranges"},

    vegetables => {favorite => "corn",

                 second => "peas"}

);

for $food (keys %hash) {

   print "$food:\n\t {";

   for $key (keys %{$hash{$food}}) {

      print "’$key’ => \"$hash{$food}{$key}\",";

   }

   print "}\n";

}

vegetables:

     {’favorite’ => "corn", 'second’ => "peas", }

fruits:

     {’favorite’ => "apples", 'second’ => "oranges", }

Чтобы сортировать записи хеш-таблицы по ключам, в заголовок цикла можно включить операцию сортировки:

%hash = (

    fruits => {favorite => "apples",

                 second => "oranges"},

    vegetables => {favorite => "corn",

                 second => "peas"}

);

for $food (sort keys %hash) {

   print "$food:\n\t {";

   for $key (sort keys %{$hash{$food}}) {

      print "’$key’ => \"$hash{$food}{$key}\",";

   }

   print "}\n";

}

fruits:

     {’favorite’ => "apples", 'second’ => "oranges", }

vegetables:

     {’favorite’ => "corn", 'second’ => "peas", }

Объявление массива хешей

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

@array = (

         {

           favorite => "apples",

           'second favorite’ => "oranges"

         },

         {

           favorite => "corn",

           'second favorite’ => "peas",

           'least favorite’ => "turnip"

         },

         {

           favorite => "chicken",

           'second favorite’ => "beef"

         }

);

print $array[0]{favorite};

apples

Обратите внимание, что для конструкций вида [...]{...}, как и для рассмотренных ранее конструкций вида {...}{...} и [...][[...], между парами скобок неявно подставляется оператор-стрелка -> разыменования ссылок.

Создание массива хешей «на лету»

Можно создавать массивы хешей шаг за шагом, присваивая ссылки на анонимные хеши элементам массива:

@array[0] = {favorite => "apples",

           'second favorite’ => "oranges"};

@array[1] = {favorite => "corn",

           'second favorite’ => "peas",

           'least favorite’ => "turnip"};

@array[2] = {favorite => "chicken",

           'second favorite’ => "beef"};

print $array[0]{favorite};

apples

Как и в случае массива массивов, вы можете воспользоваться функцией push:

push @array, {favorite => "apples",

           'second favorite’ => "oranges"};

push @array, {favorite => "corn",

           'second favorite’ => "peas",

           'least favorite’ => "turnip"};

push @array, {favorite => "chicken",

           'second favorite’ => "beef"};

print $array[0]{favorite};

apples

В следующем примере мы последовательно читаем из текстовых строк пары ключ/значение и превращаем их в массив хешей:

$data[0] = "favorite:apples, second favorite:oranges";

$data[1] = "favorite:corn, second favorite:peas,

            least favorite:turnip";

$data[2] = "favorite:chicken, second favorite:beef";

for $loopindex (0..$#data) {

   for $element (split ’,’, $data[$loopindex]) {

      ($key, $value) = split ’:’, $element;

      $key =~ s/^[\s\n]+//;  # очистить от пробелов

      $key =~ s/[\s\n]+$;//;

      $value =~ s/^[\s\n]+//;  # очистить от пробелов

      $value =~ s/[\s\n]+$;//;

      $array[$loopindex]{$key} = $value;

   }

}

print $array[0]{’second favorite’};

oranges

(Обратите внимание, что мы здесь воспользовались контекстно-чувствительной процедурой автооживления ссылок (autovivification), описанной в главе 8.

Доступ к элементам массива хешей

Чтобы получить значение, хранимое в массиве хешей, надо указать индекс массива и ключ хеша:

@array[0] = {favorite => "apples",

                 'second favorite’ => "oranges"};

@array[1] = {favorite => "corn",

           'second favorite’ => "peas",

           'least favorite’ => "turnip"};

@array[2] = {favorite => "chicken",

           'second favorite’ => "beef"};

print $array[0]{favorite};

apples

В следующем случае мы полностью выводим массив хешей с помощью цикла по его элементам:

@array[0] = {favorite => "apples",

                 second => "oranges"};

@array[1] = {favorite => "corn",

                 second => "peas",

                 least => "turnip"};

@array[2] = {favorite => "chicken",

                 second => "beef"};

for $loopindex (0..$#array) {

   print "array[$loopindex]:\n\t{";

   for $key (keys %{$array[$loopindex]}) {

      print "$key => $array[$loopindex]{$key}, ";

   }

   print "}\n";

}

array[0]:

  {favorite => apples, second => oranges, }

array[1]:

  {favorite => corn, second => peas, least => turnip, }

array[2]:

  {favorite => chicken, second => beef, }

А вот как сделать то же самое, используя вместо индекса цикла ссылку:

@array[0] = {favorite => "apples",

                 second => "oranges"};

@array[1] = {favorite => "corn",

                 second => "peas",

                 least => "turnip"};

@array[2] = {favorite => "chicken",

                 second => "beef"};

for $hashreference (@array) {

   print "{";

   for $key (sort keys %$hashreference) {

      print "$key => $array[$loopindex]{$key}, ";

   }

   print "}\n";

}

{favorite => apples, second => oranges, }

{favorite => corn, second => peas, least => turnip, }

{favorite => chicken, second => beef, }

Объявление хеша массивов

Хеши, состоящие из массивов, позволяют разбивать данные, индексированные числовым значением, разбиваются на записи.

Подсказка: Из четырех возможных комбинаций массивов и хешей, хеши массивов используются наиболее редко.

В следующем примере мы объявляем хеш массивов в одном предложении:

%hash = (

   fruits => ["apples", "oranges"],

   vegetables => ["corn", "peas", "turnips"],

   meat => ["chicken", "ham"],

);

print $hash{fruits}[0];

apples

Обратите внимание, что для конструкций вида {...}[...], как и для рассмотренных ранее конструкций вида {...}{...} [...][[...], и [...]{...}, между парами скобок неявно подставляется оператор-стрелка -> разыменования ссылок.

Создание хеша массивов «на лету»

Чтобы собрать хеш массивов из отдельных элементов, можно заносить в хеш под нужным ключом ссылки на массивы, созданные генератором анонимных массивов:

%hash{fruits} = ["apples", "oranges"];

%hash{vegetables} = ["corn", "peas", "turnips"];

%hash{meat} = ["chicken", "ham"];

print $hash{fruits}[0];

apples

Если вы предпочитаете другой вариант, можете воспользоваться функцией push и контекстно-чувствительной процедурой автооживления ссылок (autovivification), описанной в главе 8:

push @{%hash{fruits}}, "apples", "oranges";

push @{%hash{vegetables}}, "corn", "peas", "turnips";

push @{%hash{meat}}, "chicken", "ham";

print $hash{fruits}[0];

apples

Доступ к элементам хеша массивов

Вы всегда можете получить доступ к отдельному элементу данных, хранимому в хеше массивов, указав ключ и индекс:

%hash = (

   fruits => ["apples", "oranges"],

   vegetables => ["corn", "peas", "turnips"],

   meat => ["chicken", "ham"],

);

print $hash{fruits}[0];

apples

В следующем примере мы полностью выводим отсортированный по значениям ключа хеш массивов, используя функцию join для преобразования массивов в текстовые строки:

%hash = (

   fruits => ["apples", "oranges"],

   vegetables => ["corn", "peas", "turnips"],

   meat => ["chicken", "ham"],

);

for $key (sort keys %hash) {

   print "$key:\t[", join(", ", @{$hash{$key}}), "]\n";

}

fruits:         [apples, oranges]

meat:               [chicken, ham]

vegetables:     [corn, peas, turnips]

Связные списки и кольцевые буферы

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

Одной из популярных разновидностей связных списков является кольцевой буфер, который получается при замыкании связного списка в кольцо. Кольцевой буфер хранит данные с помощью двух индексных элементов: головного (head) и концевого (tail). При занесении данных в буфер увеличивается концевой индекс. При извлечении данных из буфера, увеличивается головной индекс. Когда головной и концевой индексы перекрываются, буфер становится пустым. Перемещая по замкнутому кругу головной и концевой индексы, буфер позволяет эффективно использовать память. (Например, нажатия на клавиши клавиатуры, хранятся на компьютерах IBM PC и их клонах в кольцевых буферах, рассчитанных на пятнадцать элементов, и при их переполнении раздается гудок.)

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

Мы будем моделировать кольцевой буфер с помощью массива, состоящего из хешей. Каждый элемент массива — это хеш с двумя ключами. Ключ data предназначен для хранения данных. Ключ next — это идущий вслед за текущим индекс элемента массива. Тем самым получаем связный список индексов, который и моделирует наш кольцевой буфер.

Вот как инициализируется буфер (головной и концевой индексы устанавливаются в одно значение, что указывает на пустоту буфера):

$buffer[0]{next} = 1;

$buffer[0]{data} = 0;

$buffer[1]{next} = 2;

$buffer[1]{data} = 0;

$buffer[2]{next} = 3;

$buffer[2]{data} = 0;

$buffer[3]{next} = 0;

$buffer[3]{data} = 0;

$head = 0;

$tail = 0;

Чтобы занести в буфер новый элемент, надо проверить проверяете, не заполнен ли буфер. Если буфер полон — возвращается ноль. Если в буфере еще есть место, в него помещается элемент, концевой индекс увеличивается, а функция возвращает единицу:

sub store

{

   # проверка заполнения буфера

   if ($buffer[$tail]{next} != $head) {

      # в буфере есть место

      $buffer[$tail]{data} = shift;

      $tail = $buffer[$tail]{next};

      return 1;

   } else {

      # буфер переполнен

      return 0;

   }

}

Чтобы извлечь из буфера элемент, надо проверить, не пуст ли он. Если  пуст — возвращаем неопределенное значение. Если нет, — возвращаем злемент, на который указывает головной индекс, и увеличиваем последний:

sub retrieve

{

   # проверка заполнения буфера

   if ($head != $tail) {

      # в буфере есть данные

      $data = $buffer[$head]{data};

      $head = $buffer[$head]{next};

      return $data;

   } else {

      # буфер пуст

      return undef;

   }

}

Приведем пример добавления и извлечения данных из буфера:

store 0;

store 1;

store 2;

store 3;          # буфер заполнен, данное не сохранено

print retrieve, "\n";

print retrieve, "\n";

print retrieve, "\n";

0

1

2

Обратите внимание, что хотя мы пытались поместить в буфер четыре элемента, три полностью заполняют его, а четвертый игнорируется.