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

@Pantheonptz · Регистрация: 05.05.2017

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

pos - указывает на след элемент после головы
start - начало
Как проверять очередь на пустоту и заполненность?
получается когда pos = start то очередь может быть как заполнена полностью так и пуста. Ввести какой то дополнительный flag?

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
84
85
86
87
88
89
90
91
92
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package queue1;
import java.util.Scanner;
/**
 *
 * @author 1
 */
 
 
 
public class Queue1 {
 
    /**
     * @param args the command line arguments
     */
    final static int count = 5;
    static int arr[] = new int[count - 1];
    static int start = 0;
    static int pos = 0;
    
    
    public static boolean isEmpty(){
        return  (pos == start);
    }
    
    public static boolean isFull(){
        return ((pos+1)%count == start) || (pos+1 == start);
    }
    
    public static void push(int elem){
        if(!isFull()){
            arr[pos++] = elem;
        if(pos + 1 == count) 
            pos = 0;}
        else
            System.out.println("Error! Queue is full.");
    }
    
    public static int pop(){
        if(!isEmpty()){
            if(start == count-1){
                start = 0;
                return arr[count-1];}
            else
                return arr[start++];
        }
        else{
            System.out.println("Error! Queue is empty.");
        }
        return 0;
    }
    
    public static void outQueue(){
        if(!isEmpty())
        if(start < pos)
            for(int i = start;i<pos;i++)
                System.out.print(arr[i]+" - ");
        else{
            for(int i = start; i < count; i++)
                System.out.print(arr[i]+" - ");
            for(int i = 0; i < pos; i++)
                System.out.print(arr[i]+" - ");}
            System.out.println("");
    }
    
    public static void main(String[] args) {
        // TODO code application logic here
        Scanner in = new Scanner(System.in);
        String s = "";
        while(!s.equalsIgnoreCase("q")){
            System.out.println("type 'p' - to push digit to queue");
            System.out.println("type 'u' - to pop digits from queue");
            System.out.println("type 'i' - to out digits from queue");
            System.out.println("type 'q' - to quit");
            s = in.next();
            if(s.equalsIgnoreCase("p")){
                System.out.println("enter digit - ");
                s = in.next();
                push(Integer.valueOf(s));
                        }
            if(s.equalsIgnoreCase("u"))
                System.out.println(pop());
            if(s.equalsIgnoreCase("i"))
                outQueue();
        }        
    }
    
}

Добавлено через 4 минуты

Java
1
2
3
4
5
6
7
8
9
    static int flag = 0;
    
    public static boolean isEmpty(){
        return flag == 0;
    }
    
    public static boolean isFull(){
        return flag == count;
    }

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

Добавлено через 7 секунд

Java
1
2
3
4
5
6
7
8
9
    static int flag = 0;
    
    public static boolean isEmpty(){
        return flag == 0;
    }
    
    public static boolean isFull(){
        return flag == count;
    }

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

@iSmokeJC · 17.01.2018, 17:48

Pantheonptz, задай еще одну переменную, с размером массива. При push и pop проверяй и соответственно увеличивай\уменьшай после операции.

@korvin_ · 18.01.2018, 00:45

Pantheonptz, например:

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
import java.util.OptionalInt;
 
public interface IntRingBuffer {
 
    boolean push(int value);
 
    OptionalInt pop();
 
    int size();
 
    int capacity();
 
    int[] items();
 
    int[] flush();
 
    static IntRingBuffer notOverwritableWithCapacity(int capacity) {
        return IntRingBufferWithoutOverwriting.withCapacity(capacity);
    }
 
    static IntRingBuffer overwritableWithCapacity(int capacity) {
        return IntRingBufferWithOverwriting.withCapacity(capacity);
    }
}

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
import java.util.Arrays;
import java.util.OptionalInt;
import java.util.stream.IntStream;
 
final class Demo {
 
    public static void main(String[] args) {
        final int capacity = 4;
        demo("Not overwritable buffer", IntRingBuffer.notOverwritableWithCapacity(capacity));
        demo("Overwritable buffer", IntRingBuffer.overwritableWithCapacity(capacity));
    }
 
    private static void demo(String title, IntRingBuffer buffer) {
        System.out.println("Demo " + title + ":\n");
        final int n = buffer.capacity() + 2;
 
        IntStream.range(1, n).forEach(value -> push(buffer, value));
        System.out.println();
 
        IntStream.range(1, n).forEach(value -> pop(buffer));
        System.out.println();
 
        flush(buffer);
        System.out.println();
 
        System.out.println("----------------------------------------------------------------\n");
    }
 
    private static void push(IntRingBuffer buffer, int value) {
        final boolean pushed = buffer.push(value);
        System.out.println("has" + (pushed ? "" : "n't") + " been pushed: " + value);
        items(buffer);
    }
 
    private static void pop(IntRingBuffer buffer) {
        final OptionalInt popped = buffer.pop();
        popped.ifPresentOrElse(
                value -> System.out.println("has been popped " + value),
                ()    -> System.out.println("hasn't been popped")
        );
        items(buffer);
    }
 
    private static void items(IntRingBuffer buffer) {
        System.out.println("\tbuffer[size=" + buffer.size() + "]: " + Arrays.toString(buffer.items()));
    }
 
    private static void flush(IntRingBuffer buffer) {
        push(buffer, 1);
        push(buffer, 2);
        final int[] items = buffer.flush();
        System.out.println("flushed: " + Arrays.toString(items));
        items(buffer);
    }
}

=>

Code
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
Demo Not overwritable buffer:
 
has been pushed: 1
    buffer[size=1]: [1]
has been pushed: 2
    buffer[size=2]: [1, 2]
has been pushed: 3
    buffer[size=3]: [1, 2, 3]
has been pushed: 4
    buffer[size=4]: [1, 2, 3, 4]
hasn't been pushed: 5
    buffer[size=4]: [1, 2, 3, 4]
 
has been popped 1
    buffer[size=3]: [2, 3, 4]
has been popped 2
    buffer[size=2]: [3, 4]
has been popped 3
    buffer[size=1]: [4]
has been popped 4
    buffer[size]: []
hasn't been popped
    buffer[size]: []
 
has been pushed: 1
    buffer[size=1]: [1]
has been pushed: 2
    buffer[size=2]: [1, 2]
flushed: [1, 2]
    buffer[size]: []
 
----------------------------------------------------------------
 
Demo Overwritable buffer:
 
has been pushed: 1
    buffer[size=1]: [1]
has been pushed: 2
    buffer[size=2]: [1, 2]
has been pushed: 3
    buffer[size=3]: [1, 2, 3]
has been pushed: 4
    buffer[size=4]: [1, 2, 3, 4]
has been pushed: 5
    buffer[size=4]: [2, 3, 4, 5]
 
has been popped 2
    buffer[size=3]: [3, 4, 5]
has been popped 3
    buffer[size=2]: [4, 5]
has been popped 4
    buffer[size=1]: [5]
has been popped 5
    buffer[size]: []
hasn't been popped
    buffer[size]: []
 
has been pushed: 1
    buffer[size=1]: [1]
has been pushed: 2
    buffer[size=2]: [1, 2]
flushed: [1, 2]
    buffer[size]: []
 
----------------------------------------------------------------

Implementation

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
final class IntRingBufferWithoutOverwriting extends AbstractIntRingBuffer {
 
    static IntRingBufferWithoutOverwriting withCapacity(int capacity) {
        Util.validateCapacity(capacity, MAX_CAPACITY);
        final int[] items = new int[capacity];
        return new IntRingBufferWithoutOverwriting(items);
    }
 
    private IntRingBufferWithoutOverwriting(int[] items) {
        super(items);
    }
 
    @Override
    public boolean push(int value) {
        if (size() == capacity()) {
            return false;
        }
        unsafePush(value);
        return true;
    }
}

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
final class IntRingBufferWithOverwriting extends AbstractIntRingBuffer {
 
    static IntRingBufferWithOverwriting withCapacity(int capacity) {
        Util.validateCapacity(capacity, MAX_CAPACITY);
        final int[] items = new int[capacity];
        return new IntRingBufferWithOverwriting(items);
    }
 
    private IntRingBufferWithOverwriting(int[] items) {
        super(items);
    }
 
    @Override
    public boolean push(int value) {
        if (size() == capacity()) {
            unsafePop();
        }
        unsafePush(value);
        return true;
    }
}

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
import java.util.Arrays;
import java.util.OptionalInt;
 
abstract class AbstractIntRingBuffer implements IntRingBuffer {
 
    static final int MAX_CAPACITY = Integer.MAX_VALUE / 4;
 
    private static final int[] EMPTY_ITEMS = {};
 
    private final int[] items;
 
    private int pushPosition;
    private int popPosition;
    private int size;
 
    AbstractIntRingBuffer(int[] items) {
        this.items = items;
        init();
    }
 
    @Override
    public final OptionalInt pop() {
        if (size == 0) {
            return OptionalInt.empty();
        }
        return OptionalInt.of(unsafePop());
    }
 
    @Override
    public final int size() {
        return size;
    }
 
    @Override
    public final int capacity() {
        return items.length;
    }
 
    @Override
    public final int[] items() {
        if (size == 0) {
            return EMPTY_ITEMS;
        }
        if (pushPosition > popPosition) {
            return Arrays.copyOfRange(items, popPosition, pushPosition);
        }
        final int firstPartLen = items.length - popPosition;
        final int lastPartLen = pushPosition;
        final int[] result = new int[firstPartLen + lastPartLen];
        System.arraycopy(items, popPosition, result, 0, firstPartLen);
        System.arraycopy(items, 0, result, firstPartLen, lastPartLen);
        return result;
    }
 
    @Override
    public final int[] flush() {
        final int[] result = items();
        init();
        return result;
    }
 
    final void unsafePush(int value) {
        items[pushPosition] = value;
        pushPosition = Util.nextPosition(pushPosition, items.length);
        size++;
    }
 
    final int unsafePop() {
        final int value = items[popPosition];
        popPosition = Util.nextPosition(popPosition, items.length);
        size--;
        return value;
    }
 
    private void init() {
        pushPosition = 0;
        popPosition = 0;
        size = 0;
    }
}

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
final class Util {
 
    static int nextPosition(int currentPosition, int maxPosition) {
        final int nextPosition = currentPosition + 1;
        if (nextPosition == maxPosition) {
            return 0;
        }
        return nextPosition;
    }
 
    static void validateCapacity(int capacity, int maxCapacity) {
        if (capacity < 1 || capacity > maxCapacity) {
            throw new IllegalArgumentException("Invalid queue capacity [0.." + maxCapacity + "]: " + capacity);
        }
    }
 
    private Util() {
    }
}

Новые блоги и статьи Все статьи Все блоги /
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(), которая. . .

@iSmokeJC 19530 / 11067 / 2931 Регистрация: 21.10.2017 Сообщений: 23,294
	17.01.2018, 17:48
	Pantheonptz, задай еще одну переменную, с размером массива. При push и pop проверяй и соответственно увеличивай\уменьшай после операции. 0