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

Автор книги: Герберт Шилдт

сообщить о нарушении

Текущая страница: 10 (всего у книги 36 страниц)

В данной версии конструктора класса Pwr имена параметров совпадают с именами переменных экземпляра, скрывая их. А ключевое слово this используется здесь для того, чтобы “раскрыть” переменные экземпляра.

Упражнение для самопроверки по материалу главы 4

В чем отличие класса от объекта?

Как определяется класс?

Чью собственную копию содержит каждый объект?

Покажите, как объявить объект counter класса MyCounter, используя два отдельных оператора.

Как должен быть объявлен метод myMeth, принимающий два параметра, а и b, типа int и возвращающий значение типа double?

Как должно завершаться выполнение метода, возвращающего некоторое значение?

Каким должно быть имя конструктора?

Какие действия выполняет оператор new?

Что такое “сборка мусора” и какие действия она выполняет? Зачем нужен метод finalize()?

Что означает ключевое слово this?

Может ли конструктор иметь один или несколько параметров?

Если метод не возвращает значения, то как следует объявить тип этого метода?

Глава 5 Дополнительные сведения о типах данных и операторах

Основные навыки и понятия

Представление о массивах

Создание многомерных массивов

Создание нерегулярных массивов

Представление об альтернативном синтаксисе объявления массивов

Присваивание ссылок на массивы

Применение переменной экземпляра length

Использование разновидности for-each цикла for

Манипулирование символьными строками

Употребление аргументов командной строки

Использование поразрядных операторов

Применение оператора ?

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

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

Главное преимущество массива – в организации данных таким образом, чтобы ими было проще манипулировать. Так, если имеется массив, содержащий дивиденды, выплачиваемые по избранной группе акций, то, организовав циклическое обращение к элементам этого массива, можно без особого труда рассчитать средний доход от этих акций. Кроме того, массивы позволяют организовать данные таким образом, чтобы легко отсортировать их.

Массивами в Java можно пользоваться практически так же, как и в других языках программирования. Тем не менее у них имеется одна особенность: они реализованы в виде объектов. Именно поэтому их рассмотрение было отложено до тех пор, пока в этой книге не были представлены объекты. Реализация массивов в виде объектов дает ряд существенных преимуществ, и далеко не самым последним среди них является возможность утилизировать неиспользуемые массивы средствами “сборки мусора”. Одномерные массивы

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

Для объявления одномерного массива обычно применяется следующая общая форма: тип имя_массива[] = new тип[размер];

где тип объявляет конкретный тип элемента массива. Тип элемента, называемый также базовым, определяет тип данных каждого элемента, составляющего массив. А размер определяет число элементов массива. В связи с тем что массивы реализованы в виде объектов, создание массива происходит в два этапа. Сначала объявляется переменная, ссылающаяся на массив, затем выделяется память для массива, а ссылка на нее присваивается переменной массива. Следовательно, память для массивов в Java динамически распределяется с помощью оператора new.

Проиллюстрируем все сказанное выше на конкретном примере. В следующей строке кода создается массив типа int, состоящий из 10 элементов, а ссылка на него присваивается переменной sample: int sample[] = new int[10];

Объявление массива происходит так же, как и объявление объекта. В переменной sample сохраняется ссылка на область памяти, выделяемую для массива оператором new. Этой памяти должно быть достаточно для размещения в ней 10 элементов типа int.

Как и объявление объектов, приведенное выше объявление массива можно разделить на две отдельные составляющие следующим образом: int sample []; sample = new int[10];

В данном случае сначала создается переменная sample, которая пока что не ссылается на конкретный объект. А затем переменная sample получает ссылку на конкретный массив.

Доступ к отдельным элементам массива осуществляется с помощью индексов. Индекс обозначает положение элемента в массиве. В Java индекс первого элемента массива равен нулю. Так, если массив sample содержит 10 элементов, их индексы находятся в пределах от 0 до 9. Индексирование массива осуществляется по номерам его элементов, заключенным в квадратные скобки. Например, для доступа к первому элементу массива sample следует указать sample [ 0 ], а для доступ к последнему элементу этого массива – sample [9]. В приведенном ниже примере программы в массиве sample сохраняются числа от 0 до 9. // Демонстрация одномерного массива, class ArrayDemo { public static void main(String args[]) { int sample[] = new int[10]; int i; // Массивы индексируются с нуля, как показано ниже. for(i = 0; i < 10; i = i+1) sample[i] = i; for(i =0; i < 10; i = i+1) System.out.println("This is sample[" + i + "] : " + sample [i]); } }

Результат выполнения данной программы выглядит следующим образом: This is sample[0]: 0 This is sample[1]: 1 This is sample[2]: 2 This is sample[3]: 3 This is sample[4]: 4 This is sample[5]: 5 This is sample[6]: 6 This is sample[7]: 7 This is sample[8]: 8 This is sample[9]: 9

Структура массива sample наглядно показана на приведенном ниже рисунке. Массивы часто употребляются в программировании, поскольку они позволяют обрабатывать в цикле большое количество переменных. Например, в результате выполнения следующего примера программы определяется минимальное и максимальное значения из всех, хранящихся в массиве nums. Элементы этого массива перебираются в цикле for. // Нахождение минимального и максимального значений в массиве, class MinMax { public static void main(String args[]) { int nums[] = new int[10]; int min, max; nums[0] = 99; nums[l] = -10; nums[2] = 100123; nums[3] = 18; nums[4] = -978; nums[5] = 5623; nums[6] = 4 63; nums[7] = -9; nums[8] =287; nums[9] = 4 9; min = max = nums[0]; for(int i=l; i < 10; i++) { if(nums[i] < min) min = nums[i]; if(nums[i] > max) max = nums[i]; } System.out.println("min and max: " + min + " " + max); } }

Ниже приведен результат выполнения данной программы. min and max: -978 100123

В приведенном выше примере программы массив nums заполняется вручную в десяти операторах присваивания. И хотя в этом нет ничего неверного, существует более простой способ решения той же самой задачи. Массивы можно инициализировать в процессе их создания. Для этой цели служит приведенная ниже общая форма инициализации массива. тип имя_массива[] = {vail, val2, val3, ..., valN} ;

где vall-valN обозначают первоначальные значения, которые присваиваются элементам массива по очереди, слева направо и по порядку индексирования. Для хранения инициализаторов массива в Java автоматически распределяется достаточный объем памяти. А необходимость пользоваться оператором new явным образом отпадает сама собой. В качестве примера ниже приведена улучшенная версия программы, в которой определяются максимальное и минимальное значения в массиве. // Применение инициализаторов массива, class MinMax2 { public static void main(String args[]) { // Инициализаторы массива. int nums[] = { 99, -10, 100123, 18, -978, 5623, 463, -9, 287, 49 }; int min, max; min = max = nums[0]; for(int i=l; i < 10; i++) { if(nums[i] < min) min = nums[i]; if(nums[i] > max) max = nums[i]; } System.out.println("Min and max: " + min + " " + max); } }

Границы массива в Java строго соблюдаются. Если границы массива не достигаются или же превышаются, при выполнении программы возникает ошибка. Для того чтобы убедиться в этом, попробуйте выполнить приведенную ниже программу, в которой намеренно превышаются границы массива. // Демонстрация превышения границ массива, class ArrayErr { public static void main(String args[]) { int sample[] = new int[10]; int i; // воссоздать превышение границ массива for(i = 0; i < 100; i = i+1) sample[i] = i; } }

Как только значение переменной i достигнет 10, будет сгенерировано исключение ArraylndexOutOfBoundsException и выполнение программы прекратится.

Пример для опробования 5.1. Сортировка массива

Как пояснялось выше, данные в одномерном массиве организованы в виде индексируемого линейного списка. Такая структура как нельзя лучше подходит для сортировки. В этом проекте предстоит реализовать простой алгоритм сортировки массива. Вам, вероятно, известно, что существуют разные алгоритмы сортировки, в том числе быстрая сортировка, сортировка перемешиванием, сортировка методом Шелла. Но самым простым и общеизвестным алгоритмом является пузырьковая сортировка. Этот алгоритм не очень эффективен, но отлично подходит для сортировки небольших массивов.

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

Создайте новый файл Bubble. j ava.

В алгоритме пузырьковой сортировки соседние элементы массива сравниваются и меняются, если требуется, местами. При этом малые значения сдвигаются к одному краю массива, а большие значения – к другому. Этот процесс напоминает всплывание пузырьков воздуха на разные уровни в емкости с жидкостью, откуда и произошло название данного алгоритма. Пузырьковая сортировка предполагает обработку массива в несколько проходов. Элементы, взаимное расположение которых отличается от требуемого, меняются местами. Число проходов должно быть таким, чтобы все элементы непременно встали на свои места. Максимальное количество проходов должно быть на один меньше, чем число элементов в массиве. Ниже приведен исходный код, составляющий основу алгоритма пузырьковой сортировки. Сортируемый массив называется nums. // Это пример реализации алгоритма пузырьковой сортировки. for(a=l; а < size; а++) for(b=size-l; b >= a; b—) { if(nums[b-l] > nums[b]) { // если требуемый порядок следования // не соблюдается, поменять элементы местами t = nums[b—1]; nums[b-l] = nums[b]; nums[b] = t; } } Как видите, в приведенном выше фрагменте кода используются два цикла for. Во внутреннем цикле сравниваются соседние элементы массива и выявляются элементы, находящиеся не на своих местах. Если обнаружен элемент, положение которого отличается от требуемого, то два соседних элемента меняются местами. На каждом проходе наименьший элемент передвигается на один шаг в нужное положение. Внешний цикл обеспечивает повторение описанного выше процесса до тех пор, пока сортировка массива не будет завершена.

Ниже приведен весь исходный код программы из файла Bubble. j ava. /* Пример для опробования 5.1. Демонстрация алгоритма пузырьковой сортировки. */ class Bubble { public static void main(String args[]) { int nums[] = { 99, -10, 100123, 18, -978, 5623, 463, -9,, 287, 49 }; int a, b, t; int size; size = 10; // Количество элементов для сортировки // отобразить исходный массив System.out.print("Original array is:"); for(int i=0; i < size; i++) System.out.print(" " + nums[i]); System.out.println(); // реализовать алгоритм пузырьковой сортировки for(a=l; а < size; а++) for(b=size-l; b >= a; b—) { if(nums[b-l] > nums[b]) { // если требуемый порядок // следования не соблюдается, поменять элементы местами t = nums[b-l]; nums[b-l] = nums[b]; nums[b] = t; } } // отобразить отсортированный массив System, out .print ("Sorted array is: "); for(int i=0; i < size; i++) System.out.print(" " + nums[i]); System.out.println(); } }

Ниже приведен результат выполнения данной программы. Original array is: 99 -10 100123 18 -978 5623 463 -9 287 49 Sorted array is: -978 -10 -9' 18 49 99 287 463 5623 100123

Как упоминалось выше, пузырьковая сортировка отлично подходит для обработки мелких массивов, но при большом числе элементов массива она становится неэффективной. Более универсальным является алгоритм быстрой сортировки, но для его эффективной реализации необходимы языковые средства Java, которые рассматриваются далее в этой книге. Многомерные массивы

Несмотря на то что одномерные массивы употребляются чаще всего, в программировании, безусловно, применяются и многомерные (двух-, трехмерные и т.д.) массивы. В Java многомерные массивы представляют собой массивы массивов. Двумерные массивы

Среди многомерных массивов наиболее простыми являются двумерные массивы. Двумерный массив, по существу, представляет собой ряд одномерных массивов. Для того чтобы объявить двумерный целочисленный табличный массив table размерами 10x20, следует написать такое выражение: int tablet][] = new int[10][20];

Обратите особое внимание на объявление этого массива. В отличие от некоторых других языков программирования, где размеры массива разделяются запятыми, в Java они заключаются в отдельные квадратные скобки. Так, для обращения к элементу массива table по индексам 3 и 5 следует указать table [ 3 ] [ 5 ].

В следующем примере двумерный массив заполняется числами от 1 до 12: // Демонстрация двумерного массива, class TwoD { public static void main(String args[]) { int t, i; int table [][] = new int[3][4]; for(t=0; t < 3; ++t) { for(i=0; i < 4; ++i) { table[t][i] = (t*4)+i+l; System.out.print(table[t][i] + " "); } System.out.println() ; } } }

В данном примере элемент table [0] [0] будет содержать значение 1, элемент table [0] [ 1 ] – значение 2, элемент table [0] [2] – значение 3 и так далее, а элемент table [2 ] [ 3 ] – значение 12. Структура данного массива наглядно показана на рис. 5.1. Нерегулярные массивы

Выделяя память под многомерный массив, достаточно указать лишь первый (крайний слева) размер. А память под остальные размеры массива можно выделять по отдельности. Например, в приведенном ниже фрагменте кода память выделяется только под первый размер двумерного массива table. А под второй его размер она выделяется вручную. int tablet][] = new int[3][]; table[0] = new int[4]; table[1] = new int[4]; table[2] = new int[4];

Объявляя массив подобным образом, мы не получаем никаких преимуществ, но в некоторых случаях такое объявление оказывается вполне оправданным. Это, в частности, дает возможность установить разную длину массива по каждому индексу. Как упоминалось выше, многомерный массив реализован в виде массива массивов, что позволяет контролировать длину каждого из них. Допустим, требуется написать программу, в процессе работы которой будет сохраняться число пассажиров, перевезенных автобусом-экспрессом в аэропорт. Если автобус-экспресс делает по десять рейсов в будние дни и по два рейса в субботу и воскресенье, то массив riders можно объявить так, как показано в приведенном ниже фрагменте кода. Обратите внимание на то, что длина массива по второму размеру для первых пяти элементов равна 10, а для двух последних элементов – 2. // Указать разную длину по второму размеру массива вручную, class Ragged { public static void main(String args[]) { int riders[][] = new int[7][]; // Для первых пяти элементов длина массива //по второму размеру равна 10. riders[0] = new int[10]; riders[1] = new int[10]; riders[2] = new int[10]; riders[3] = new int[10]; riders[4] = new int[10]; // Для остальных двух элементов длина массива //по второму размеру равна 2. riders[5] = new int[2]; riders[6] = new int[2]; int i, j; // сформировать произвольные данные for(i=0; i < 5; i++) for(j=0; j < 10; j++) riders[i][j] = i + j + 10; for(i=5; i < 7; i++) for(j=0; j < 2; j++) riders[i][j] = i + j + 10; System.out.println("Riders per trip during the week:"); for(i=0; i < 5; i++) { for(j =0; j < 10; j++) System.out.print(riders[i] [j] + " ") ; System.out.println() ; } System.out.println() ; System.out.println("Riders per trip on the weekend:"); for(i=5; i < 7; i++) { for (j=0; j < 2; j++) System.out.print(riders[i][j] + " "); System.out.println(); } } }

Для большинства приложений использовать нерегулярные массивы не рекомендуется, поскольку это затрудняет восприятие кода другими программистами. Но в некоторых случаях такие массивы вполне уместны и могут существенно повысить эффективность программ. Так, если вам требуется создать большой двумерный массив, в котором используются не все элементы, то нерегулярный массив позволит существенно сэкономить память. Трехмерные, четырехмерные и многомерные массивы

В Java допускаются массивы размерностью больше двух. Ниже приведена общая форма объявления многомерного массива. тип имя_массива[] []...[] = new тип[размер_1] [размер_2] . . . [размер_Ы] ;

В качестве примера ниже приведено объявление трехмерного целочисленного массива размерами 4x10x3. int multidim[][][] = new int[4][10][3]; Инициализация многомерных массивов

Многомерный массив можно инициализировать, заключая инициализирующую последовательность для каждого размера массива в отдельные фигурные скобки, как показано ниже. тип имя_массива[] [] = { { val, val, val, ..., val }, { val, val, val, ..., val }, { val, val, val, .. ., val } };

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

В следующем фрагменте кода двумерный массив sqrs инициализируется числами от 1 до 10 и их квадратами: // Инициализация двумерного массива, class Squares { public static void main(String args[]) { // Обратите внимание на то, что у каждой строки свой ряд инициализаторов. int sqrs[][] = { { 1, 1 }, { 2, 4 }, { 3, 9 }, { 4, 16 }, { 5, 25 }, { 6, 36 }, { 7, 49 }, { 8, 64 }, { 9, 81 }, { 10, 100 } }; int i, j; for(i=0; i < 10; i++) { for (j=0; j < 2; j++) System.out.print(sqrs[i][j] + " "); System.out.println(); } } }

Выполнение этого фрагмента кода дает следующий результат: 1 1 2 4 3 9 4 16 5 25 6 36 7 49 8 64 9 81 10 100 Альтернативный синтаксис объявления массивов

Помимо рассмотренной выше общей формы, для объявления массива можно также пользоваться следующей синтаксической конструкцией: тип [ ] имя_переменной;

Здесь квадратные скобки указываются после спецификатора типа, а не имени переменной. Поэтому следующие два объявления равнозначны: int counter[] = new int[3]; int[] counter = new int[3];

Равнозначными являются и приведенные ниже строки кода. char table[] [] = new char[3] [4]; char[][] table = new char [3] [4];

Альтернативный синтаксис объявления массива оказывается удобным в тех случаях, если требуется объявить несколько массивов одного типа. Например: int[] nums, nums2, nums3; // создать три массива

В этом объявлении создаются три переменные, ссылающиеся на массивы типа int. Тот же результат можно получить с помощью следующей строки кода: int nums[], nums2[], nums3[]; // создать три массива

Альтернативный синтаксис объявления массива оказывается удобным и в тех случаях, если в качестве типа, возвращаемого методом, требуется указать массив. Например: int[] someMeth( ) { ...

В этой строке кода объявляется метод someMeth (), возвращающий целочисленный массив.

Обе рассмотренные выше формы объявления массивов широко распространены в программировании на Java, и поэтому они употребляются в примерах, представленных в этой книге. Присваивание ссылок на массивы

Присваивание значения одной переменной ссылки на массив другой переменной, по существу, означает, что обе переменные ссылаются на один и тот же массив, и в этом отношении массивы ничем не отличаются от любых других объектов. Такое присваивание не приводит ни к созданию копии массива, ни к копированию содержимого одного массива в другой. В качестве примера рассмотрим следующую программу: // Присваивание ссылок на массивы, class AssignARef { public static void main(String args[]) { int i; int numsl[] = new int[10]; int nums2[] = new int[10]; for(i=0; i < 10; i++) nums1[i] = i; for(i=0; i < 10; i++) nums2[i] = -i; System.out.print("Here is numsl: "); for(i=0; i < 10; i++) System.out.print(numsl[i] + " "); System.out.println(); System.out.print("Here is nums2: "); for(i=0; i < 10; i++) System.out.print(nums2[i] + " "); System.out.println(); // присвоить ссылку на массив // Теперь переменные nums2 и numsl ссылаются //на один и тот же массив. nums2 = numsl; System.out.print("Here is nums2 after assignment: "); for(i=0; i < 10; i++) System.out.print(nums2[i] + " "); System.out.println() ; // выполнить операции над массивом numsl // по ссылке на массив nums2. nums2[3] = 99; System.out.print("Here is numsl after change through nums2: "); for(i=0; i < 10; i++) System.out.print(numsl[i] + " "); System.out.println(); } }

Выполнение этой программы дает следующий результат: Here is numsl: 0123456789 Here is nums2: 0 -1 -2 -3 -4 -5 -6 -7 -8 -9 Here is nums2 after assignment: 0123456789 Here is numsl after change through nums2: 012 99 456789

Нетрудно заметить, что в результате присваивания ссылки на массив numsl переменной nums 2 обе переменные ссылаются на один и тот же массив. Применение переменной экземпляра length

В связи с тем что массивы реализованы в виде объектов, в каждом массиве содержится переменная экземпляра length. Значением этой переменной является число элементов, которые может содержать массив. (Иными словами, в переменной length содержится размер массива.) Ниже приведен пример программы, демонстрирующий данное свойство массивов. // Использование переменной экземпляра length, class LengthDemo { public static void main(String args[]) { int list[] = new int[10]; int nums[] = { 1, 2, 3 }; int tablet][] = { // таблица со строками переменной длины {1, 2, 3}, { 4, 5 }, {6, 7, 8, 9} }; System.out.println("length of list is " + list.length); System.out.println("length of nums is " + nums.length); System.out.println("length of table is " + table.length); System.out.println("length of table[0] is " + table[0].length); System.out.println("length of table[l] is " + table[1].length); System.out.println("length of table[2] is " + table[2].length); System.out.println() ; // использовать переменную length для инициализации списка // Переменная length служит для управления циклом for. for(int i=0; i < list.length; i++) list[i] = i * i; System.out.print("Here is list: "); for (int i=0; i < list.length; i++) System.out.print(list[i] + " "); System.out.println() ; } }

Выполнение этой программы дает следующий результат: length of list is 10 length of nums is 3 length of table is 3 length of table[0] is 3 length of table[1] is 2 length of table[2] is 4 Here is list: 0 1 4 9 16 25 36 49 64 81

Обратите особое внимание, каким образом переменная length используется в двумерном массиве. Как пояснялось ранее, двумерный массив представляет собой массив массивов. Поэтому приведенное ниже выражение позволяет определить число массивов, содержащихся в массиве table, table.length

Число таких массивов равно 3. Для того чтобы получить длину отдельного массива, содержащегося в массиве table, потребуется выражение, аналогичное следующему: table[0].length

Это выражение возвращает длину первого массива.

Анализируя код класса LengthDemo, следует также заметить, что выражение list. length используется в цикле for для определения требуемого количества итераций. Учитывая то, что у каждого подмассива своя длина, пользоваться таким выражением удобнее, чем отслеживать вручную размеры массивов. Но не следует забывать, что переменная length не имеет никакого отношения к количеству фактически используемых элементов массива. Она содержит лишь данные о том, сколько элементов может содержать массив.

Использование переменной экземпляра length позволяет упростить многие алгоритмы. Так, в приведенном ниже примере программы эта переменная используется при копировании одного массива в другой и предотвращает возникновение при выполнении программы исключительной ситуации в связи с превышением границ массива. // Использование переменной length для копирования массивов, class АСору { public static void main(String args[]) { int i; int numsl[] = new int[10]; int nums2[] = new int[10]; for(i=0; i < numsl.length; i++) numsl[i] = i; // копировать массив numsl в массив nums2 // Переменная length служит для сравнения размеров массивов. if(nums2.length >= numsl.length) for(i =0; i < nums2.length; i++) nums2[i] = numsl[i]; for(i=0; i < nums2.length; i++) System.out.print(nums2[i] + " "); } }

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

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

Пример для опробования 5.2. Создание класса очереди

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

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

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

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

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

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

Очередь можно организовать разными способами. Мы создадим ее на основании массива, выступающего в роли хранилища данных, помещаемых в очередь. Для доступа к массиву будут использованы два индекса. Индекс размещения данных определяет, в каком месте будет размещен следующий элемент очереди. А индекс извлечения данных указывает место, откуда должен быть извлечен очередной элемент очереди. Напомним, что операция извлечения является истощающей и не позволяет извлечь один и тот же элемент дважды. Создаваемая здесь очередь предназначена для хранения символов, но та же самая логика ее организации может быть использована для размещения данных любых типов, в том числе объектов. Итак, начните создание класса очереди Queue со следующих строк кода: class Queue { char q[]; // Массив для хранения элементов очереди int putloc, getloc; // Индексы размещения и извлечения элементов очереди }

Конструктор класса Queue создает очередь заданного размера. Его код приведен ниже.Queue(int size) { q = new char[size+1]; // выделить память для очереди putloc = getloc = 0; } Обратите внимание на то, что размер очереди оказывается на единицу больше размера, задаваемого параметром size. Особенности реализации очереди таковы, что один элемент массива остается неиспользованным, поэтому размер массива должен быть на единицу больше размера очереди, создаваемой на его основе. Первоначально индексы размещения и извлечения данных равны нулю.

Метод put (), помещающий элемент в очередь, имеет следующий вид:// поместить символ в очередь void put(char ch) { if(putloc==q.length-1) { System, out .println (11 – Queue is full."); return; } putloc++; q[putloc] = ch; } Прежде всего в теле данного метода проверяется, не переполнена ли очередь. Если значение переменной putloc соответствует последнему местоположению в массиве q, то места для размещения новых элементов в очереди нет. В противном случае переменная putloc инкрементируется и новый элемент располагается в указанном месте массива. Следовательно, переменная putloc всегда содержит индекс элемента, помещенного в очередь последним.