Форум программистов, компьютерный форум, киберфорум
Java SE (J2SE)
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.72/25: Рейтинг темы: голосов - 25, средняя оценка - 4.72
69 / 69 / 39
Регистрация: 22.05.2014
Сообщений: 311

Реализация очереди

13.08.2014, 21:01. Показов 4679. Ответов 7
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Добрый день. Разбираюсь как устроена очередь как структура данных.

вот мой код
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
public class Queue<T> {
 
    private Object[] elements;
    private int start;
    private int end;
 
    public Queue() {
        this(10);
    }
 
    public Queue(int capacity) {
        elements = new Object[capacity];
        start = capacity - 1;
        end = capacity - 1;
    }
 
    public int size() {
        return start - end;
    }
 
    public boolean isEmpty() {
        return start == end;
    }
 
    public void clear() {
        for (int i = 0; i < elements.length; i++) {
            elements[i] = null;
        }
        start = elements.length - 1;
        end = elements.length - 1;
    }
 
    public void add(T element) {
        if (element == null)
            throw new IllegalArgumentException();
 
        if (end >= 0) {
            elements[end--] = element;
        } else {
            Object[] elementsBefore = elements;
            end = elementsBefore.length - 1;
            elements = new Object[elements.length * 2];
            System.arraycopy(elementsBefore, 0, elements, elementsBefore.length, elementsBefore.length);
            start += elementsBefore.length;
            elements[end--] = element;
        }
    }
 
    // Exception if queue is empty
    public T remove() {
        if (start == end)
            throw new QueueIsEmptyException();
        return (T) elements[start--];
    }
 
    // returns null is queue is empty
    public T poll() {
        if (start == end)
            return null;
        return (T) elements[start--];
    }
 
    // Exception if queue is empty
    public T element() {
        if (start == end)
            throw new QueueIsEmptyException();
        return (T) elements[start];
    }
 
    // returns null is queue is empty
    public T peek() {
        if (start == end)
            return null;
        return (T) elements[start];
    }
 
    public void print() {
        for (int i = end + 1; i <= start; i++) {
            System.out.print(elements[i] + " --> ");
        }
        System.out.print(" Вiльна кaca!");
    }
}
Вопросы:
- я делал сначала очередь тоже через масив но через один индекс, добавление слева направо, дергаем за нулевой елемент массива и на каждом удалении елемента из очереди передвигаем оставшиеся елементы до левого края через system.arrayCopy()

но я так понимаю это плохое решение из-за вызова system.arrayCopy() для каждого удаления?

- нормально ли делать так как в моем коде если возникает переполнение массива то увеличить его и перекопировать все до правого края(ну и поменяв соответственно индексы start и end)?

- подскажите пожалуйста самописную простую реализацию очереди с приоритетами
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
13.08.2014, 21:01
Ответы с готовыми решениями:

Реализация очереди
Всем привет! Я новичок в Java, мне задали посмотреть реализацию очереди, поделитесь пожалуйста простыми примерами. Спасибо!

Реализация очереди в потоке
Здравствуйте, разбираюсь с потоками, хотел реализовать задачку (по своей сути она похожа на СМО): 1) Некий датчик генерирует сигналы с...

Реализация очереди
В существующем списке элементов реализуйте: добавление элемента в начало, * добавление элемента в конец, * извлечение и удаление...

7
Вежливость-главное оружие
 Аватар для some_name
233 / 234 / 86
Регистрация: 19.02.2013
Сообщений: 1,446
13.08.2014, 21:25
Цитата Сообщение от EdisonMiranda Посмотреть сообщение
но я так понимаю это плохое решение из-за вызова system.arrayCopy() для каждого удаления?
делайте смещение только когда в притык пододете, имхо, так вы будет профит.

Цитата Сообщение от EdisonMiranda Посмотреть сообщение
- нормально ли делать так как в моем коде если возникает переполнение массива то увеличить его и перекопировать все до правого края(ну и поменяв соответственно индексы start и end)?
Насколько я знаю да, так делается, например в ArrayList. Кста, можете посмотерть исходники /Java/jdk.../src/....

Цитата Сообщение от EdisonMiranda Посмотреть сообщение
- подскажите пожалуйста самописную простую реализацию очереди с приоритетами
Лично у меня нету. Но попробуйте погуглить, что-то типа такого:
java priority queue implementation using array example
1
69 / 69 / 39
Регистрация: 22.05.2014
Сообщений: 311
15.08.2014, 21:35  [ТС]
подскажите пожалуйста, все ли я правильно понял:

есть принципиально 3 реализации очереди с приоритетом
1) через массив, добавление работает быстро - О(1) (просто добавляем в следующую ячейку), удаление работает долго - О(N) (перебираем все елементы массива в поисках с максимальным приоритетом)

2) через массив, добавление долго за О(N) (при добавлении поддерживаем массив в отсортированном состоянии), удаление быстро(так как удаляем крайний)

3) через кучу удаление и добавление работают средне за О(logN)
0
Вежливость-главное оружие
 Аватар для some_name
233 / 234 / 86
Регистрация: 19.02.2013
Сообщений: 1,446
15.08.2014, 22:52
EdisonMiranda, да, в общем и целов все так.
а что за "куча"?
1
237 / 236 / 72
Регистрация: 02.07.2013
Сообщений: 881
15.08.2014, 22:58
Цитата Сообщение от some_name Посмотреть сообщение
а что за "куча"?
куча мусора ))
0
69 / 69 / 39
Регистрация: 22.05.2014
Сообщений: 311
15.08.2014, 23:23  [ТС]
не пойму еще 1 момент. Насколько Я понимаю, очередь с приоритетом должна хранить штуки, которые имеют некоторое значение + приоритет по которому их доставать, то есть получается, что тип массива, который "под капотом" будет некое
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
public class Entry<K extends Comparable, V> {
    private K priority;
    private V value;
 
    public Entry() {
 
    }
 
    public Entry(K priority, V value) {
        this.priority = priority;
        this.value = value;
    }
 
    public K getPriority() {
        return priority;
    }
 
    public void setPriority(K priority) {
        this.priority = priority;
    }
 
    public V getValue() {
        return value;
    }
 
    public void setValue(V value) {
        this.value = value;
    }
 
    @Override
    public boolean equals(Object o) {
        if (o == null || o.getClass() != this.getClass())
            return false;
        if (this == o)
            return true;
        Entry<K, V> that = (Entry<K, V>) o;
        return this.priority.equals(that.priority) && this.value.equals(that.value);
    }
}
То есть у того, что стоит в очереди есть значение И приоритет, причем что бы приоритеты можно было сравнивать.

А везде в коде других, где не посмотрю, хранятся только приоритеты(как Comparable либо вообще частный его случай типа int). Я просто не пойму смысла хранить только приоритеты и ничего больше как реальное значение
0
Вежливость-главное оружие
 Аватар для some_name
233 / 234 / 86
Регистрация: 19.02.2013
Сообщений: 1,446
16.08.2014, 12:59
Цитата Сообщение от EdisonMiranda Посмотреть сообщение
приоритет по которому их доставать,
Вот это, как мне кажется, и достигается реализацией Comparable. Мы бежим по всей очереди и вней, вызывая compareTo(), нахожим того, кто самы самый важный.
1
69 / 69 / 39
Регистрация: 22.05.2014
Сообщений: 311
17.08.2014, 02:03  [ТС]
все, я понял.

просто все примеры на инте дак я и зациклился. получается в очереди хранится ТО, что реализует компарейбл чтобы его сравнивать, но помимо этого эТО может хранить еще сколько угодно полей
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
17.08.2014, 02:03
Помогаю со студенческими работами здесь

Реализация очереди
Добрый день. у меня такая проблема, создаю очередь из n элементов, беру первый элемент, сохраняю его и дальше удаляю из очереди ...

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

Реализация очереди
Реализуйте задание согласно варианту. В каждом из вариантов должно быть реализованы следующие режимы работы: · добавление элементов; ...

Реализация очереди в массиве.
Приветствую форумчан. Помогите с задачкой :( &quot;Реализовать операции с очередью в массиве. Пусть очередь прирастает справа, убывает...

Реализация очереди на указателях
Очередь на указателях: #include &lt;iostream&gt; using std::cin; using std::cout; using std::endl; const int Number = 10; enum...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image
8Observer8 10.02.2026
Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .
Установка Qt-версии Lazarus IDE в Debian Trixie Xfce
volvo 10.02.2026
В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer
8Observer8 08.02.2026
Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .
SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств
8Observer8 07.02.2026
Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .
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, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru