Assign the shift to an array ref instead of an array:

my $entry = shift(@{@datastructure{'foo'}});   # it's an anrray ref
print $_ for @$entry;    # dereference it to get the array
[download]

As you demonstrated w/Data::Dumper, You have a HoAoA .. note that by "array" it really is an array ref, which Dumper shows by using [ ] instead of ( ). So the first element of foo's array is an array ref ..

A pointer w/using Data::Dumper -- always pass it a an array ref or hash ref instead of just an array or hash .. In this case it would have made the contents of @entry clearer (and Dumper(\%datastructure) would better illustrate the hashing):

Dumper(\@entry);
$VAR1 = [
          [
            'foo01',
            'foo02'
          ]
        ];
[download]