Реализация очереди в массиве.

@t-mac2010 · Регистрация: 15.12.2010

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

Приветствую форумчан. Помогите с задачкой

"Реализовать операции с очередью в массиве. Пусть очередь прирастает справа, убывает слева. Длина массива должна соответствовать длине очереди."

Заранее благодарен.

@Unril · 15.12.2010, 19:33

C#
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
#region using
 
using System;
using System.Collections.Generic;
 
#endregion
 
namespace ConsoleApplicationTest
{
    public static class Program
    {
        private static void Main()
        {
            // Применение
            var myQueue = new MyQueue<int>();
 
            // Добавляем элементы
            myQueue.Enqueue(1);
            myQueue.Enqueue(2);
            myQueue.Enqueue(3);
            myQueue.Enqueue(4);
 
            // Преобразуем в массив и печатаем элементы из него.
            foreach (int i in myQueue.ToArray())
                Console.WriteLine(i);
 
            Console.WriteLine();
 
            // Извлекаем элементы
            while (myQueue.Count > 0)
                Console.WriteLine(myQueue.Dequeue());
 
            Console.ReadKey();
        }
    }
 
    public class MyQueue<T>
    {
        // Поля
        private T[] _array;
        private int _head;
        private int _tail;
 
        // Методы
        /// <summary>
        /// Создаём очередь. Ёмкость по умолнчанию - 0;
        /// </summary>
        public MyQueue()
        {
            _array = new T[0];
        }
 
        /// <summary>
        /// Создаём очередь на основе коллекции.
        /// </summary>
        /// <param name="collection">Исходная коллекция.</param>
        public MyQueue(IEnumerable<T> collection)
        {
            if (collection == null)
                throw new ArgumentNullException();
            _array = new T[4];
            Count = 0;
            foreach (T variable in collection)
                Enqueue(variable);
        }
 
        /// <summary>
        /// Создаём очередь с заданной начальной ёмкостью. 
        /// Если количество добавленных элементов превысит заданную ёмкость, то она будет автоматически увеличена.
        /// </summary>
        /// <param name="capacity">Начальная ёмкость.</param>
        public MyQueue(int capacity)
        {
            if (capacity < 0)
                throw new ArgumentOutOfRangeException();
            _array = new T[capacity];
            _head = 0;
            _tail = 0;
            Count = 0;
        }
 
        /// <summary>
        /// Количество элементов в очереди.
        /// </summary>
        public int Count { get; private set; }
 
        /// <summary>
        /// Очистка очереди.
        /// </summary>
        public void Clear()
        {
            if (_head < _tail)
                Array.Clear(_array, _head, Count);
            else
            {
                Array.Clear(_array, _head, _array.Length - _head);
                Array.Clear(_array, 0, _tail);
            }
            _head = 0;
            _tail = 0;
            Count = 0;
        }
 
        /// <summary>
        /// Проверка на нахождении элемента в очереди.
        /// </summary>
        /// <param name="item">Элемент.</param>
        /// <returns>true, если элемент содержится в очереди.</returns>
        public bool Contains(T item)
        {
            int index = _head;
            int num2 = Count;
            EqualityComparer<T> comparer = EqualityComparer<T>.Default;
            while (num2-- > 0)
            {
                if (item == null)
                {
                    if (_array[index] == null)
                        return true;
                }
                else if ((_array[index] != null) && comparer.Equals(_array[index], item))
                    return true;
                index = (index + 1)%_array.Length;
            }
            return false;
        }
 
        /// <summary>
        /// Извлечение элемента из очереди.
        /// </summary>
        /// <returns>Извлечённый элемент.</returns>
        public T Dequeue()
        {
            if (Count == 0)
                throw new InvalidOperationException();
            T local = _array[_head];
            _array[_head] = default(T);
            _head = (_head + 1)%_array.Length;
            Count--;
            return local;
        }
 
        /// <summary>
        /// Добавление элемента в очередь.
        /// </summary>
        /// <param name="item">Добавляемый элемент.</param>
        public void Enqueue(T item)
        {
            if (Count == _array.Length)
            {
                var capacity = (int) ((_array.Length*200L)/100L);
                if (capacity < (_array.Length + 4))
                    capacity = _array.Length + 4;
                SetCapacity(capacity);
            }
            _array[_tail] = item;
            _tail = (_tail + 1)%_array.Length;
            Count++;
        }
 
        /// <summary>
        /// Просмотр элемента на вершине очереди.
        /// </summary>
        /// <returns>Верхний элемент.</returns>
        public T Peek()
        {
            if (Count == 0)
                throw new InvalidOperationException();
            return _array[_head];
        }
 
        // Изменение ёмкости очереди.
        private void SetCapacity(int capacity)
        {
            var destinationArray = new T[capacity];
            if (Count > 0)
            {
                if (_head < _tail)
                    Array.Copy(_array, _head, destinationArray, 0, Count);
                else
                {
                    Array.Copy(_array, _head, destinationArray, 0, _array.Length - _head);
                    Array.Copy(_array, 0, destinationArray, _array.Length - _head, _tail);
                }
            }
            _array = destinationArray;
            _head = 0;
            _tail = (Count == capacity) ? 0 : Count;
        }
 
        /// <summary>
        /// Преобразование очереди в массив.
        /// </summary>
        /// <returns>Массив с элементами из очереди.</returns>
        public T[] ToArray()
        {
            var destinationArray = new T[Count];
            if (Count != 0)
            {
                if (_head < _tail)
                {
                    Array.Copy(_array, _head, destinationArray, 0, Count);
                    return destinationArray;
                }
                Array.Copy(_array, _head, destinationArray, 0, _array.Length - _head);
                Array.Copy(_array, 0, destinationArray, _array.Length - _head, _tail);
            }
            return destinationArray;
        }
    }
}

@t-mac2010 · 16.12.2010, 10:06 **[ТС]**

Вопрос, это Вы сами писали?) Или же мб шаблон?

@Unril · 16.12.2010, 11:29

Это, если честно, немного упрощённая реализация встроенной очереди System.Collections.Generic.Queue<T>, вытащенной с помощью рефлектора.

@t-mac2010 · 16.12.2010, 12:04 **[ТС]**

ясно...ну по сути, для моего задания этот листинг подойдет? Или же нет?

@sigmov · 16.12.2010, 13:53

Сообщение от t-mac2010

ясно...ну по сути, для моего задания этот листинг подойдет? Или же нет?

Думаю учитывая что Вы писали:

Длина массива должна соответствовать длине очереди

То могу сказать что память для очереди(размер массива) перевыделяется с запасом(чтоб не перевыделять каждое добавление элемента)

@t-mac2010 · 19.12.2010, 16:07 **[ТС]**

Так на вопрос и не ответили...., я могу этот код использовать для конкретного моего задания? Просто в результате после Ctrl+F5 просто дважды по вертикали написаны числа:
1
2
3
4

1
2
3
4

И что это?)

@t-mac2010 · 22.12.2010, 15:30 **[ТС]**

Народ, кто-нибудь может пояснить листинг программы? Пожалуйста, срочно!

@Unril · 22.12.2010, 15:46

Надеюсь, что так будет понятнее.

C#
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#region using
 
using System;
 
#endregion
 
namespace ConsoleApplicationTest
{
    public static class Program
    {
        private static void Main()
        {
            // Применение
            var myQueue = new MyQueue();
 
            // Добавляем элементы
            myQueue.Enqueue(1);
            myQueue.Enqueue(2);
            myQueue.Enqueue(3);
            myQueue.Enqueue(4);
            myQueue.Enqueue(5);
            myQueue.Enqueue(6);
 
            // Извлекаем элементы
            while (myQueue.Count > 0)
                Console.WriteLine(myQueue.Dequeue());
 
            Console.ReadKey();
        }
    }
 
    public class MyQueue
    {
        // Массив с элементами
        private int[] _array;
        // Индекс начального элемента.
        private int _head;
        // Индекс конечного элемента.
        private int _tail;
 
        /// <summary>
        /// Создаём очередь. Начальная ёмкость - 4;
        /// </summary>
        public MyQueue()
        {
            _array = new int[4];
        }
 
        /// <summary>
        /// Количество элементов в очереди.
        /// </summary>
        public int Count { get; private set; }
 
        /// <summary>
        /// Очистка очереди.
        /// </summary>
        public void Clear()
        {
            // Очищаем все поля.
            _array = new int[4];
            _head = 0;
            _tail = 0;
            Count = 0;
        }
 
        /// <summary>
        /// Извлечение элемента из очереди.
        /// </summary>
        /// <returns>Извлечённый элемент.</returns>
        public int Dequeue()
        {
            // Проверяем, можно ли что-либо достать из очереди.
            if (Count == 0)
                throw new InvalidOperationException();
            // Достаём первый элемент.
            int local = _array[_head];
            // Обнуляем первый элемент.
            _array[_head] = 0;
            // Изменяем индекс начала элементов в массиве.
            _head = (_head + 1)%_array.Length;
            // Убавляем количество элементов.
            Count--;
            return local;
        }
 
        /// <summary>
        /// Добавление элемента в очередь.
        /// </summary>
        /// <param name="item">Добавляемый элемент.</param>
        public void Enqueue(int item)
        {
            // Проверяем ёмкость массива, если недостаточна - удваиваем.
            if (Count == _array.Length)
            {
                var capacity = _array.Length*2;
                SetCapacity(capacity);
            }
            // Устанавливаем последний элемент.
            _array[_tail] = item;
            // Изменяем индекс конца массива.
            _tail = (_tail + 1)%_array.Length;
            // Прибавляем количество элементов.
            Count++;
        }
 
        /// <summary>
        /// Просмотр элемента на вершине очереди.
        /// </summary>
        /// <returns>Верхний элемент.</returns>
        public int Peek()
        {
            if (Count == 0)
                throw new InvalidOperationException();
            // Возвращаем верхний элемент без его удаления.
            return _array[_head];
        }
 
        // Изменение ёмкости очереди.
        private void SetCapacity(int capacity)
        {
            // Новый массив заданного объёма.
            int[] destinationArray = new int[capacity];
            if (Count > 0)
            {
                // Копируем старый массив в новый.
                if (_head < _tail)
                    Array.Copy(_array, _head, destinationArray, 0, Count);
                else
                {
                    Array.Copy(_array, _head, destinationArray, 0, _array.Length - _head);
                    Array.Copy(_array, 0, destinationArray, _array.Length - _head, _tail);
                }
            }
            _array = destinationArray;
            // Новые значения индексов начала и конца массива.
            _head = 0;
            if (Count == capacity)
                _tail = 0;
            else
                _tail = Count;
        }
    }
}

И прочитай, что такое очередь.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@t-mac2010 0 / 0 / 1 Регистрация: 15.12.2010 Сообщений: 10

	Реализация очереди в массиве. 15.12.2010, 17:34. Показов 24889. Ответов 8 Метки нет (Все метки) Приветствую форумчан. Помогите с задачкой "Реализовать операции с очередью в массиве. Пусть очередь прирастает справа, убывает слева. Длина массива должна соответствовать длине очереди." Заранее благодарен. 0

@t-mac2010 0 / 0 / 1 Регистрация: 15.12.2010 Сообщений: 10
	16.12.2010, 10:06 [ТС]
	Вопрос, это Вы сами писали?) Или же мб шаблон? 0

@Unril 826 / 717 / 110 Регистрация: 06.10.2010 Сообщений: 825 Записей в блоге: 1
	16.12.2010, 11:29
	Это, если честно, немного упрощённая реализация встроенной очереди System.Collections.Generic.Queue<T>, вытащенной с помощью рефлектора. 0

@t-mac2010 0 / 0 / 1 Регистрация: 15.12.2010 Сообщений: 10
	16.12.2010, 12:04 [ТС]
	ясно...ну по сути, для моего задания этот листинг подойдет? Или же нет? 0

@t-mac2010 0 / 0 / 1 Регистрация: 15.12.2010 Сообщений: 10
	19.12.2010, 16:07 [ТС]
	Так на вопрос и не ответили...., я могу этот код использовать для конкретного моего задания? Просто в результате после Ctrl+F5 просто дважды по вертикали написаны числа: 1 2 3 4 1 2 3 4 И что это?) 0

@t-mac2010 0 / 0 / 1 Регистрация: 15.12.2010 Сообщений: 10
	22.12.2010, 15:30 [ТС]
	Народ, кто-нибудь может пояснить листинг программы? Пожалуйста, срочно! 0