Динамическая кольцевая очередь

@evgmur · Регистрация: 12.12.2012

Студворк — интернет-сервис помощи студентам

Изучаю Java по книге Шилдта. Там есть задание создание кольцевого варианта динамической очереди. Я уже не знаю, как еще ее можно сделать, ведь при заполнении очереди она расширяется и как тогда должны переносится элементы из конца кольца? (при организации очереди один элемент должен быть всегда пустым)
Вот класс с динамической очередью:

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public 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 char[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];
    }
 
}

А это с обычной кольцевой:

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public 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+1==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=0;//вернутьсь в начало очереди
        return q[getloc];
    }
 
}

@M_Kenan · 28.10.2014, 11:08

В чом конкретно ваша проблема

@evgmur · 28.10.2014, 11:39 **[ТС]**

проблема в том, что я не знаю как сделать так, чтобы при полной очереди она расширялась

@turbanoff · 28.10.2014, 12:04

evgmur, Вроде же очевидно, вместо

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

нужно написать код, который увеличивает размер массива q.

@evgmur · 28.10.2014, 12:22 **[ТС]**

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

@turbanoff · 28.10.2014, 12:41

evgmur, не понял, почему она будет затирать старые элементы? Мы же знаем, где именно очередь начинается, и где заканчивается. И мы точно можем сделать правильное расширение массива.

Добавлено через 5 минут
Напишите код, который будет затирать элементы. Я потом вам подскажу что именно нужно подправить.

@evgmur · 28.10.2014, 13:29 **[ТС]**

Сообщение от turbanoff

evgmur, не понял, почему она будет затирать старые элементы? Мы же знаем, где именно очередь начинается, и где заканчивается. И мы точно можем сделать правильное расширение массива.

Добавлено через 5 минут
Напишите код, который будет затирать элементы. Я потом вам подскажу что именно нужно подправить.

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class DynCircQueue implements ICharQ{
    private char q[];
    private int putloc, getloc;
    
    public DynCircQueue(int size) {
        q=new char[size+1];
        putloc=getloc=0;
    }
 
    @Override
    public void put(char ch) {
        // TODO Auto-generated method stub
        if(putloc+1==getloc | ((putloc==q.length-1) & (getloc==0))){
            char t[]=new char[q.length*2];
            
            for(int i=0;i<q.length;i++)
                t[i]=q[i];
                q=t;
            }
            putloc++;
            if (putloc==q.length) putloc=0;
            q[putloc]=ch;
        }
 
 
    @Override
    public char get() {
        // TODO Auto-generated method stub
        if(getloc==putloc){
            System.out.println(" - Queue is empty.");
            return (char) 0;
        }
        getloc++;
        if(getloc==q.length) getloc=0;
        return q[getloc];
    }
 
}

@M_Kenan · 28.10.2014, 13:33

Кау то так. Но лучше не смотри и сам разберись

Кликните здесь для просмотра всего текста

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class DynQoue {
    int[] qoue;
    int[] buffer;
    int teil;
    public DynQoue() {
        qoue = new int[2];
        teil = qoue.length - 1;
    }
    
    public void put(int element){
        if(teil == 0){
            buffer = qoue;
            qoue = new int[buffer.length * 2 - 1];
            for(int i = 0; i < buffer.length;i++)
                qoue[i+buffer.length - 1] = buffer[i];
            teil = buffer.length - 1;
            buffer = null;
        }
        qoue[teil] = element;
        teil--;
    }
    public int get(){
        if(teil == qoue.length -1){
            System.out.println("Очередь пуста");
            return 0;
            }
        int element = qoue[qoue.length - 1];
        put(element);
        for(int i = 0; i < (qoue.length - (teil + 1)); i++){
            qoue[qoue.length - i -1] = qoue[qoue.length - i - 2];
        }
        teil++;
        return element;
    }
    public void print(){
        for(int i = teil + 1; i < qoue.length; i++)
            System.out.print(qoue[i] + " ");
            System.out.println();
    }
}

@evgmur · 28.10.2014, 15:03 **[ТС]**

Сообщение от M_Kenan

Кау то так. Но лучше не смотри и сам разберись

Кликните здесь для просмотра всего текста

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class DynQoue {
    int[] qoue;
    int[] buffer;
    int teil;
    public DynQoue() {
        qoue = new int[2];
        teil = qoue.length - 1;
    }
    
    public void put(int element){
        if(teil == 0){
            buffer = qoue;
            qoue = new int[buffer.length * 2 - 1];
            for(int i = 0; i < buffer.length;i++)
                qoue[i+buffer.length - 1] = buffer[i];
            teil = buffer.length - 1;
            buffer = null;
        }
        qoue[teil] = element;
        teil--;
    }
    public int get(){
        if(teil == qoue.length -1){
            System.out.println("Очередь пуста");
            return 0;
            }
        int element = qoue[qoue.length - 1];
        put(element);
        for(int i = 0; i < (qoue.length - (teil + 1)); i++){
            qoue[qoue.length - i -1] = qoue[qoue.length - i - 2];
        }
        teil++;
        return element;
    }
    public void print(){
        for(int i = teil + 1; i < qoue.length; i++)
            System.out.print(qoue[i] + " ");
            System.out.println();
    }
}

как-то я все равно не могу понять ваш метод...можете рассказать сам алгоритм? потому что в методе get вы зачем-то опять используете метод put

Добавлено через 6 минут
И заодно тогда еще вопрос: при написании метода, который будет устанавливать очередь в исходное состояние, в нем нужно просто реализовать putloc=getloc=0; ?

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@M_Kenan 16 / 16 / 10 Регистрация: 17.03.2014 Сообщений: 59
	28.10.2014, 11:08
	В чом конкретно ваша проблема 0

@evgmur 1 / 1 / 0 Регистрация: 12.12.2012 Сообщений: 31
	28.10.2014, 11:39 [ТС]
	проблема в том, что я не знаю как сделать так, чтобы при полной очереди она расширялась 0

@evgmur 1 / 1 / 0 Регистрация: 12.12.2012 Сообщений: 31
	28.10.2014, 12:22 [ТС]
	ок, представим, что у нас запихнули в очередь на три элемента три элемента, потом забрали один, а потом еще туда решили запихнуть четыре элемента. получится, что очередь переполнится, станет в два раза больше и продолжит даль запихивать элементы, тем самым, затирая старые элементы 0

@turbanoff 4094 / 3828 / 745 Регистрация: 18.05.2010 Сообщений: 9,331 Записей в блоге: 12
	28.10.2014, 12:41
	evgmur, не понял, почему она будет затирать старые элементы? Мы же знаем, где именно очередь начинается, и где заканчивается. И мы точно можем сделать правильное расширение массива. Добавлено через 5 минут Напишите код, который будет затирать элементы. Я потом вам подскажу что именно нужно подправить. 0