Упорядоченный список, в котором элементы добавляются к одному концу списка, а удаляются с другой стороны, называется очередью (queue). Группа людей, ожидающих обслуживания в магазине, образует очередь. Вновь прибывшие подходят сзади. Когда покупатель доходит до начала очереди, кассир его обслуживает. Из‑за их природы, очереди иногда называют списками типа первый вошел — первый вышел (First‑In‑First‑Out list).
@Рис. 3.1. Два стека в одном массиве
=======52
Можно реализовать очереди в Visual Basic, используя методы типа использованных для организации простых стеков. Создадим массив, и при помощи счетчиков будем определять положение начала и конца очереди. Значение переменной QueueFront дает индекс элемента в начале очереди. Переменная QueueBack определяет, куда должен быть добавлен очередной элемент очереди. По мере того как новые элементы добавляются в очередь и покидают ее, размер массива, содержащего очередь, изменяется так, что он растет на одном конце и уменьшается на другом.
Global Queue() As String ' Массив очереди.
Global QueuePront As Integer ' Начало очереди.
Global QueueBack As Integer ' Конец очереди.
Sub EnterQueue(value As String)
ReDim Preserve Queue(QueueFront To QueueBack)
Queue(QueueBack) = value
QueueBack = QueueBack + 1
End Sub
Sub LeaveQueue(value As String)
value = Queue(QueueFront)
QueueFront = QueueFront + 1
ReDim Preserve Queue (QueueFront To QueueBack - 1)
End Sub
К сожалению, Visual Basic не позволяет использовать ключевое слово Preserve в операторе ReDim, если изменяется нижняя граница массива. Даже если бы Visual Basic позволял выполнение такой операции, очередь при этом «двигалась» бы по памяти. При каждом добавлении или удалении элемента из очереди, границы массива увеличивались бы. После пропускания достаточно большого количества элементов через очередь, ее границы могли бы в конечном итоге стать слишком велики.
Поэтому, когда требуется увеличить размер массива, вначале необходимо переместить данные в начало массива. При этом может образоваться достаточное количество свободных ячеек в конце массива, так что увеличение размера массива может уже не понадобиться. В противном случае, можно воспользоваться оператором ReDim для увеличения или уменьшения размера массива.
Как и в случае со списками, можно повысить производительность, добавляя сразу несколько элементов при увеличении размера массива. Также можно сэкономить время, уменьшая размер массива, только когда он содержит слишком много неиспользуемых ячеек.
В случае простого списка или стека, элементы добавляются и удаляются на одном его конце. Если размер списка остается почти постоянным, его не придется изменять слишком часто. С другой стороны, так как элементы добавляются на одном конце очереди, а удаляются с другого конца, может потребоваться время от времени переупорядочивать очередь, даже если ее размер остается неизменным.
=====53
Const WANT_FREE_PERCENT = .1 ' 10% свободного пространства.
Const MIN_FREE = 10 ' Минимум свободных ячеек.
Global Queue() As String ' Массив очереди.
Global QueueMax As Integer ' Наибольший индекс массива.
Global QueueFront As Integer ' Начало очереди.
Global QueueBack As Integer ' Конец очереди.
Global ResizeWhen As Integer ' Когда увеличить размер массива.
' При инициализации программа должна установить QueueMax = -1
' показывая, что под массив еще не выделена память.
Sub EnterQueue(value As String)
If QueueBack > QueueMax Then ResizeQueue
Queue(QueueBack) = value
QueueBack = QueueBack + 1
End Sub
Sub LeaveQueue(value As String)
value = Queue(QueueFront)
QueueFront = QueueFront + 1
If QueueFront > ResizeWhen Then ResizeOueue
End Sub
Sub ResizeQueue()
Dim want_free As Integer
Dim i As Integer
' Переместить записи в начало массива.
For i = QueueFront To QueueBack - 1
Queue(i - QueueFront) = Queue(i)
Next i
QueueBack = QueueBack - QueuePront
QueueFront = 0
' Изменить размер массива.
want_free = WANT_FREE_PERCENT * (QueueBack - QueueFront)
If want_free < MIN_FREE Then want_free = MIN_FREE
Max = QueueBack + want_free - 1
ReDim Preserve Queue(0 To Max)
' Если QueueFront > ResizeWhen, изменить размер массива.
ResizeWhen = want_free
End Sub
При работе с программой, заметьте, что когда вы добавляете и удаляете элементы, требуется изменение размера очереди, даже если размер очереди почти не меняется. Фактически, даже при неоднократном добавлении и удалении одного элемента размер очереди будет изменяться.
Имейте в виду, что при каждом изменении размера очереди, вначале все используемые элементы перемещаются в начало массива. При этом на изменение размера очередей на основе массива уходит больше времени, чем на изменение размера описанных выше связных списков и стеков.
=======54
Программа ArrayQ2 аналогична программе ArrayQ, но она использует для управления очередью класс ArrayQueue.
Очереди, описанные в предыдущем разделе, требуется переупорядочивать время от времени, даже если размер очереди почти не меняется. Даже при неоднократном добавлении и удалении одного элемента будет необходимо переупорядочивать очередь.
Если заранее известно, насколько большой может быть очередь, этого можно избежать, создав циклическую очередь (circular queue). Идея заключается в том, чтобы рассматривать массив очереди как будто он заворачивается, образуя круг. При этом последний элемент массива как бы идет перед первым. На рис. 3.2 изображена циклическая очередь.
Программа может хранить в переменной QueueFront индекс элемента, который дольше всего находится в очереди. Переменная QueueBack может содержать конец очереди, в который добавляется новый элемент.
В отличие от предыдущей реализации, при обновлении значений переменных QueueFront и QueueBack, необходимо использовать оператор Mod для того, чтобы индексы оставались в границах массива. Например, следующий код добавляет элемент к очереди:
Queue(QueueBack) = value
QueueBack = (QueueBack + 1) Mod QueueSize
На рис. 3.3 показан процесс добавления нового элемента к циклической очереди, которая может содержать четыре записи. Элемент C добавляется в конец очереди. Затем конец очереди сдвигается, указывая на следующую запись в массиве.
Таким же образом, когда программа удаляет элемент из очереди, необходимо обновлять указатель на начало очереди при помощи следующего кода:
value = Queue(QueueFront)
QueueFront = (QueueFront + 1) Mod QueueSize
@Рис. 3.2. Циклическая очередь
=======55
@Рис. 3.3. Добавление элемента к циклической очереди
На рис. 3.4 показан процесс удаления элемента из циклической очереди. Первый элемент, в данном случае элемент A, удаляется из начала очереди, и указатель на начало очереди обновляется, указывая на следующий элемент массива.
Для циклических очередей иногда бывает сложно отличить пустую очередь от полной. В обоих случаях значения переменных QueueBottom и QueueTop будут равны. На рис. 3.5 показаны две циклические очереди, пустая и полная.
Простой вариант решения этой проблемы — сохранять число элементов в очереди в отдельной переменной NumInQueue. При помощи этого счетчика можно узнать, остались ли в очереди еще элементы, и осталось ли в очереди место для новых элементов.
@Рис. 3.4. Удаление элемента из циклической очереди
@Рис. 3.5 Полная и пустая циклическая очереди
=========56
Следующий код использует все эти методы для управления циклической очередью:
Queue() As String ' Массив очереди.
QueueSize As Integer ' Наибольший индекс в очереди.
QueueFront As Integer ' Начало очереди.
QueueBack As Integer ' Конец очереди.
NumInQueue As Integer ' Число элементов в очереди.
Sub NewCircularQueue(num_items As Integer)
QueueSize = num_items
ReDim Queue(0 To QueueSize - 1)
End Sub
Sub EnterQueue(value As String)
' Если очередь заполнена, выйти из процедуры.
' В настоящем приложении потребуется более сложный код.
If NumInQueue >= QueueSize Then Exit Sub
Queue(QueueBack) = value
QueueBack = (QueueBack + 1) Mod QueueSize
NumInQueue = NumInQueue + 1
End Sub
Sub LeaveQueue (value As String)
' Если очередь пуста, выйти из процедуры.
' В настоящем приложении потребуется более сложный код.
If NumInQueue <= 0 Then Exit Sub
value = Queue (QueueFront)
QueueFront = (QueueFront + 1) Mod QueueSize
NumInQueue = NumInQueue - 1
End Sub
Так же, как и в случае со списками на основе массивов, можно изменять размер массива, когда очередь полностью заполнится или если в массиве будет слишком много неиспользуемого пространства. Тем не менее, изменение размера циклической очереди сложнее, чем изменить размер стека или списка, основанного на массиве.
Когда изменяется размер массива, конец очереди может не совпадать с концом массива. Если просто увеличить массив, то вставляемые элементы будут находиться в конце массива, так что они попадут в середину списка. На рис. 3.6 показано, что может произойти при таком увеличении массива.
===========57
При уменьшении размера массива возникают похожие проблемы. Если элементы огибают конец массива, то элементы в конце массива, которые будут находиться в начале очереди, будут потеряны.
Для того чтобы избежать этих затруднений, необходимо переупорядочить массив перед тем, как изменять его размер. Проще всего это сделать, используя временный массив. Скопируем элементы очереди во временный массив в правильном порядке, поменяем размер массива очереди, и затем скопируем элементы из временного массива обратно в массив очереди.
Private Sub EnterQueue(value As String)
If NumInQueue >= QueueSize Then ResizeQueue
Queue(QueueBack) = value
QueueBack = (QueueBack + 1) Mod QueueSize
NumInQueue = NumInQueue + 1
End Sub
Private Sub LeaveQueue(value As String)
If NumInQueue <= 0 Then Exit Sub
value = Queue (QueueFront)
QueueFront = (QueueFront + 1) Mod QueueSize
NumInQueue = NumInQueue - 1
If NumInQueue < ShrinkWhen Then ResizeQueue
End Sub
Sub ResizeQueue()
Dim temp() As String
Dim want_free As Integer
Dim i As Integer
' Скопировать элементы во временный массив.
ReDim temp(0 To NumInQueue - 1)
For i = 0 To NumInQueue - 1
temp(i) = Queue((i + QueueFront) Mod QueueSize)
Next i
' Изменить размер массива.
want_free = WANT_FREE_PERCENT * NumInQueue
If want_free < MIN_PREE Then want_free = MIN_FREE
QueueSize = NumInQueue + want_free
ReDim Queue(0 To QueueSize - 1)
For i = 0 To NumInQueue - 1
Queue(i) = temp(i)
Next i
QueueFront = 0
QueueBack = NumInQueue
' Уменьшить размер массива, если NunInQueue < ShrinkWhen.
ShrinkWhen = QueueSize - 2 * want_free
' Не менять размер небольших очередей. Это может вызвать
' проблемы с "ReDim temp(0 To NumInQueue - 1)" выше и
' просто глупо!
If ShrinkWhen < 3 Then ShrinkWhen = 0
End Sub