Java: руководство для начинающих (ЛП)

В кольцевой очереди повторно используются элементы массива, освобожденные при извлечении символов. Поэтому в нее можно поместить неограниченное число элементов (при условии, что элементы, помещенные в очередь ранее, будут вовремя удалены). Отслеживание границ массива производится очень просто (достаточно обнулить индекс по достижении верхней границы), хотя условие достижения этих границ может, на первый взгляд, показаться не совсем понятным. Кольцевая очередь переполняется не тогда, когда достигается верхняя граница массива, а тогда, когда число элементов, ожидающих извлечения из очереди, становится слишком большим. Поэтому в методе put проверяется ряд условий с целью определить момент переполнения очереди. Как следует из комментариев к коду, очередь считается заполненной, если индекс putloc оказывается на единицу меньше индекса getloc или если индекс putloc указывает на конец массива, а индекс getloc — на его начало. Как и прежде, очередь считается пустой, если индексы getloc и putloc равны.

Введите в файл IQDemo.java приведенный ниже код класса DynQueue. Этот код реализует динамическую, или “растущую”, очередь, т.е. такую очередь, размеры которой увеличиваются, когда в ней не хватает места для символов. // Динамическая очередь. class DynQueue implements ICharQ { private char q[]; // Массив для хранения элементов очереди, private int putloc, getloc; // Индексы размещения и извлечения // элементов очереди. // создать пустую очередь заданного размера public DynQueue(int size) { q = new char[size+1]; // выделить память для очереди putloc = getloc = 0; } // поместить символ в очередь public void put(char ch) { if(putloc==q.length-1)-{ // увеличить размер очереди char t[] = new ch^r[q.length * 2]; // скопировать элементы в новую очередь for(int i=0; i < q.length; i++) t[i] = q[i]; q = t; } putloc++; q[putloc] = ch; } // извлечь символ из очереди ' public char get { if(getloc == putloc) { System.out.println(" - Queue is empty."); return (char) 0; } getloc++; return q[getloc]; } }

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

Для того чтобы продемонстрировать все три реализации интерфейса ICharQ, добавьте в файл IQDemo.java приведенный ниже класс, в котором для доступа ко всем трем очередям используется переменная ссылки на интерфейс ICharQ. // Демонстрация трех реализаций интерфейса ICharQ. class IQDemo { public static void main(String args[]) { FixedQueue ql = new FixedQueue(10); DynQueue q2 = new DynQueue(5); CircularQueue q3 = new CircularQueue(10); ICharQ iQ; char ch; int i; iQ = q1; // поместить ряд символов в очередь фиксированного размера for(i=0; i < 10; i++) iQ.put((char) ('A1 + i) ) ; // отобразить содержимое очереди System.out.print("Contents of fixed queue: "); for(i=0; i < 10; i++) { ch = iQ. get ; System.out.print(ch); } System.out.println ; iQ = q2; // поместить ряд символов в динамическую очередь for (i=0; i < 10; i++) iQ.put((char) ('Z1 - i)); // отобразить содержимое очереди System.out.print("Contents of dynamic queue: "); for(i=0; i < 10; i++) { ch = iQ.get ; System.out.print(ch); } System.out.println ; iQ = q3; // поместить ряд символов в кольцевую очередь for (i=0; i < 10; i++) iQ.put((char) ('A1 + i)); // отобразить содержимое очереди System.out.print("Contents of circular queue: "); for(i=0; i < 10; i++) { ch = iQ.get; System.out.print(ch); } System.out.println; // поместить больше символов в кольцевую очередь for(i=10; i < 20; i++) - iQ.put((char) (’A' + i)); // отобразить содержимое очереди System.out.print("Contents of circular queue: "); for(i=0; i < 10; i++) { ch = iQ.get; System.out.print(ch); } System.out.println("\nStore and consume from" + " circular queue."); // поместить символы в кольцевую очередь и извлечь их оттуда for(i=0; i < 20; i++) { iQ.put((char) ('A1 + i)); ch = iQ.get; System.out.print(ch); } } }