ПРИМЕР 4. Создание класса очереди

Вам, вероятно, известно, что структура данных — это способ их организации. Одной из самых простых структур является массив, который представляет собой линейный список элементов, допускающий произвольный доступ к ним. Нередко массивы используются в качестве основания для создания более сложных структур вроде стеков или очередей. Стек — это набор элементов с организацией доступа по принципу “первым пришел — последним обслужен”. А очередь — это набор элементов с организацией доступа по принципу “первым пришел — первым обслужен”. Стек можно сравнить со стопкой тарелок на столе: первая тарелка снизу стопки используется последней. А очередь можно сравнить с выстроившейся очередью к окошку в банке: клиент, стоящий в очереди первым, обслуживается первым. В очередях и стеках нас больше всего интересует способ хранения информации и обращения к ней. И стеки, и очереди представляют собой механизмы доступа к данным, в которых хранение и извлечение информации поддерживается самой структурой, а не реализуется в программе. Такое сочетание способов хранения и обработки данных лучше всего реализуется в рамках класса, поэтому в данном проекте предстоит создать простой класс очереди.

В очереди поддерживаются две основные операции: размещение и извлечение. При выполнении операции размещения новый элемент помещается в конец очереди, а при операции извлечения очередной элемент извлекается из начала очереди. Операции с очередью являются истощающими: элемент, однажды извлеченный из очереди, не может быть извлечен из нее повторно. Очередь может быть переполнена, когда в ней не остается места для новых элементов. Но очередь может быть и пуста, когда в ней нет ни одного элемента. И последнее замечание: существуют два типа очередей — циклические и нециклические. В циклической очереди элементы массива, на основе которого она создана, могут использоваться повторно по мере удаления данных. Нециклическая очередь не позволяет повторно использовать элементы, поэтому со временем пространство для хранения новых элементов исчерпывается. Нециклическую очередь создать намного проще, чем циклическую, поэтому именно ее мы и реализуем в данном примере для опробования. Но если немного подумать, то нециклическую очередь можно без особого труда превратить в циклическую.

Последовательность действий

1. Создайте новый файл QDemo.java.

2. Очередь можно организовать разными способами. Мы создадим ее на основании массива, выступающего в роли хранилища данных, помещаемых в очередь. Для доступа к массиву будут использованы два индекса. Индекс размещения данных определяет, в каком месте будет размещен следующий элемент очереди. А индекс извлечения данных указывает место, откуда должен быть извлечен очередной элемент очереди. Напомним, что операция извлечения является истощающей и не позволяет извлечь один и тот же элемент дважды. Создаваемая здесь очередь предназначена для хранения символов, но та же самая логика ее организации может быть использована для размещения данных любых типов, в том числе объектов. Итак, начните создание класса очереди Queue со следующих строк кода:

class Queue {

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

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

// очереди

3. Конструктор класса Queue создает очередь заданного размера. Его код приведен ниже.

Queue(int size) {

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

putloc = getloc = 0;

}

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

4. Метод put (), помещающий элемент в очередь, имеет следующий вид:

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

void put(char ch) {

if(putloc==q.length-1) {

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

return;

}

putloc++;

q [putloc] = ch;

}

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

5. Для извлечения элементов из очереди служит метод get(), код которого приведен ниже.

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

char get О {

if(getloc == putloc) {

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

return (char) 0;

}

getloc++;

return q[getloc];

}

Сначала в данном методе проверяется, пуста ли очередь. Если значения индексов в переменных getloc и putloc совпадают, то в очереди нет ни одного элемента. Именно поэтому в конструкторе Queue переменные getloc и putloc инициализируются нулевыми значениями. Если очередь не пуста, то переменная getloc инкрементируется и из нее извлекается очередной элемент. Следовательно, переменная getloc содержит индекс последнего извлеченного элемента.

6. Ниже приведен весь исходный код программы из файла QDemo.java.

/*

Класс, реализующий очередь, для хранения символов.

*/

class Queue {

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

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

// очереди

Queue(int size) {

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

putloc = getloc = 0;

}

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

void put(char ch) {

if(putloc==q.length-1) {

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

return;

}

putloc++;

q[putloc] = ch;

}

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

char get О {

if(getloc == putloc) {

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

return (char) 0;

}

getloc++;

return q[getloc];

}

}

// продемонстрировать класс Queue

class QDemo {

public static void main(String args[]) {

Queue bigQ = new Queue (100);

Queue smallQ = new Queue(4);

char ch;

int i;

System.out.println(" Using bigQ to store the alphabet.");

// поместить буквенные символы в очередь bigQ

for(i=0; i < 26; i++)

bigQ.put((char) ('A' + i));

// извлечь буквенные символы из очереди bigQ и отобразить

System.out.print(" Contents of bigQ: ");

for(i=0; i < 26; i++) {

ch = bigQ.get();

if(ch! = (char) 0) System.out.print(ch);

}

System.out.println(" \n");

System.out.println(" Using smallQ to generate errors.");

// использовать небольшую очередь smallQ для генерации ошибок

for(i=0; i < 5; i++) {

System.out.print(" Attempting to store " + (char) CZ' - i));

smallQ.put((char) ('Z' - i));

System.out.println();

}

System.out.println();

// дополнительные ошибки при обращении к очереди smallQ

System.out.print(" Contents of smallQ: ");

for(i=0; i < 5; i++) {

ch = smallQ.get0;

if(ch! = (char) 0) System.out.print(ch);

}

}

}

7. Ниже приведен результат выполнения данной программы.

Using bigQ to store the alphabet.

Contents of bigQ: ABCDEFGHIJKLMNOPQRSTUVWXYZ

Using smallQ to generate errors.

Attempting to store Z

Attempting to store Y

Attempting to store X

Attempting to store W

Attempting to store V - Queue is full.

Contents of smallQ: ZYXW - Queue is empty.