Всплывание очереди.
Перед тем, как кодировать очередь обратим внимание на одну особенность ее линейного представления в виде массива. Очередь с "активным кассиром" будет неизбежно всплывать к верхним адресам массива, оставляя за собой неиспользуемое пустое пространство. Для массивов конечного размера это ведет к скорому переполнению (при наличии в массиве массы пустого места снизу), а для условно бесконечных массивов к быстрому росту занимаемой ими памяти. Решить эту проблему без применения каких-либо специальных ухищрений, по сути превращающих очередь в связный список, не представляется возможным. Поэтому, в качестве идеи алгоритма можно взять, например, обычную циклическую очередь с наперед заданным размером и контролем переполнения или очередь меняющую направление роста при образовании под ней достаточного пустого пространства.
В SmallBasic проблемы управления памятью решаются еще проще. Наряду с включенной почти в каждую версию Бейсика командой REDIM, позволяющей управлять размерами массива после его создания, в SmallBasic присутствует инструкция DELETE:
DELETE arr, idx, [count]
удаляющая count элементов массива начиная с индекса idx c восстановлением сплошной нумерации. Если для внутренней реализации массива используются динамические структуры, то какая-бы то ни была нужда в использовании указателей в таком Бейсике - пропадает полностью. Помимо DELETE в SmallBasic введены инструкции APPEND и INSERT.
Примеры:
dim a(10)
dim b
a(0)=0
a(1)=1
a(2)=2
a(3)=3
a(4)=4
a(5)=5
a(6)=6
a(7)=7
a(8)=8
a(9)=9
a(10)=10
print a
DELETE a,4,3
for i=0 to len(a)-1
? i, a(i)
next i
print b
APPEND b, "xxx"
APPEND b, "yyy"
APPEND b, "zzz"
APPEND b, "ttt"
APPEND b, "ppp"
print b
DELETE b, 2, 2
print b
INSERT b,2, "val"
print b
Результат:
[0,1,2,3,4,5,6,7,8,9,10]
0 0
1 1
2 2
3 3
4 7
5 8
6 9
7 10
[]
[xxx,yyy,zzz,ttt,ppp]
[xxx,yyy,ppp]
[xxx,yyy,val,ppp]
Однако данные возможности - это специфика SmallBasic и не имеют к стандарту на Бейсик никакого отношения. Хотя с их помощью реализация очереди выглядит особенно просто.
В SmallBasic проблемы управления памятью решаются еще проще. Наряду с включенной почти в каждую версию Бейсика командой REDIM, позволяющей управлять размерами массива после его создания, в SmallBasic присутствует инструкция DELETE:
DELETE arr, idx, [count]
удаляющая count элементов массива начиная с индекса idx c восстановлением сплошной нумерации. Если для внутренней реализации массива используются динамические структуры, то какая-бы то ни была нужда в использовании указателей в таком Бейсике - пропадает полностью. Помимо DELETE в SmallBasic введены инструкции APPEND и INSERT.
Примеры:
dim a(10)
dim b
a(0)=0
a(1)=1
a(2)=2
a(3)=3
a(4)=4
a(5)=5
a(6)=6
a(7)=7
a(8)=8
a(9)=9
a(10)=10
print a
DELETE a,4,3
for i=0 to len(a)-1
? i, a(i)
next i
print b
APPEND b, "xxx"
APPEND b, "yyy"
APPEND b, "zzz"
APPEND b, "ttt"
APPEND b, "ppp"
print b
DELETE b, 2, 2
print b
INSERT b,2, "val"
print b
Результат:
[0,1,2,3,4,5,6,7,8,9,10]
0 0
1 1
2 2
3 3
4 7
5 8
6 9
7 10
[]
[xxx,yyy,zzz,ttt,ppp]
[xxx,yyy,ppp]
[xxx,yyy,val,ppp]
Однако данные возможности - это специфика SmallBasic и не имеют к стандарту на Бейсик никакого отношения. Хотя с их помощью реализация очереди выглядит особенно просто.