Глава 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
Обратите внимание, что хотя мы пытались поместить в буфер четыре элемента, три полностью заполняют его, а четвертый игнорируется.