Java руководство для начинающих - Шилдт Герберт (2012)

// извлечь символ из очереди

public char get() {

if(getloc == putloc) {

System.out.println(" - Queue is empty.");

return (char) 0;

}

getloc++;

return q[getloc];

}

}

Эта реализация интерфейса ICharQ выполнена на основе уже знакомого вам класса Queue, разработанного в главе 5.

Добавьте в файл IQDemo. j ava приведенный ниже класс CircularQueue. Он реализует кольцевую очередь для хранения символов.

// Кольцевая очередь.

class CircularQueue implements ICharQ {

private char q[]; // Массив для хранения элементов очереди,

private int putloc, getloc; // Индексы размещения и извлечения

// элементов очереди.

// создать пустую очередь заданного размера

public CircularQueue (int size) {

q = new char[size+1]; // выделить память для очереди

putloc = getloc = 0;

}

// поместить символ в очередь

public void put(char ch) {

/* Очередь считается полной, если индекс putloc на единицу

меньше индекса getloc или если индекс putloc указывает

на конец массива, а индекс getloc - на его начало. */

if(putloc+l==getloc |

((putloc==q.length-1) & (getloc==0))) {

System.out.println(" - Queue is full.");

return;

}

putloc++;

if(putloc==q.length) putloc = 0; // перейти в начало массива

q[putloc] = ch;

}

// извлечь символ из очереди

public char get() {

if(getloc == putloc) {

System.out.println(" - Queue is empty.");

return (char) 0;

}

getloc++;

if (getloc==q. length) getloc = 0f- // вернуться в начало очереди

return q[getloc];

}

}

В кольцевой очереди повторно используются элементы массива, освобожденные при извлечении символов. Поэтому в нее можно поместить неограниченное число элементов (при условии, что элементы, помещенные в очередь ранее, будут вовремя удалены). Отслеживание границ массива производится очень просто (достаточно обнулить индекс по достижении верхней границы), хотя условие достижения этих границ может, на первый взгляд, показаться не совсем понятным. Кольцевая очередь переполняется не тогда, когда достигается верхняя граница массива, а тогда, когда число элементов, ожидающих извлечения из очереди, становится слишком большим. Поэтому в методе 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.");