Представление динамической очереди

 

В динамической памяти очередь можно представить:

а) линейным односвязным списком с двумя указателями:

struct list1

{ type pole1;

list1 *pole2; }

 

struct ch3

{ list1 *beg, *end; }

Задать динамическую очередь - это определить переменную типа ch3:

ch3 Q1; Чтобы инициировать очередь достаточно указателю на начало Q1.beg и/или на конец Q1.end присвоить значение NULL. При взятии единственного элемента из очереди она должна стать пустой;

 

б) линейным двусвязным циклическим списком с одним указателем:

struct list2

{ type pole1;

list2 *pole1, *pole2; }

 

Здесь начало или конец очереди можно сделать как в начале, так и в конце списка.

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

Основные операции над очередью аналогичны операциям со стеком (с учетом особенностей этой структуры).

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

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

- дек с ограниченным выходом (только одна позиция доступна для взятия элемента из дека).

Контрольные вопросы

 

1. Понятие структуры данных стек, очередь, дек.

2. Представление в памяти структур данных стек, очередь, дек.

3. Задание структур данных стек, очередь, дек.

4. Основные операции над структурами данных стек, очередь, дек.

5. Достоинства и недостатки различного представления в памяти структур данных стек, очередь, дек.

6. Использование структур данных стек, очередь для решения задач.

Задания для практической работы

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

3. Реализовать  на основе базовых операций основные операции над динамическим стеком.

4. Реализовать  на основе базовых операций операцию “принадлежит ли заданный элемент ” статическому стеку.

5. Реализовать  на основе базовых операций операцию “принадлежит ли заданный элемент ” динамическому стеку.

6. Реализовать  на основе базовых операций основные операции над статической очередью (вид очереди: а, б, в, г).

7. Реализовать  на основе базовых операций основные операции над динамической очередью (вид очереди: а, б).

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

9. Реализовать  на основе базовых операций операцию “добавить элемент в очередь” для динамической очереди с приоритетом (вид очереди: а, б) см. 8.

10. Реализовать  на основе базовых операций операцию “принадлежит ли заданный элемент ” статической очереди (вид очереди а, б, в, г).

11. Реализовать  на основе базовых операций операцию “принадлежит ли заданный элемент ” динамической очереди (вид очереди: а, б).

12. Реализовать  на основе базовых операций основные операции над статическим деком.

13. Реализовать  на основе базовых операций основные операции над динамическим деком.

14. Проверьте на равенство две очереди.

1. Найдите среди трех (4, 5) очередей две одинаковые.
2. Организовать три очереди с одинаковым количеством элементов, содержащие соответственно имена, отчества и фамилии людей. Составьте очередь из элементов, содержащих наиболее полную информацию о людях, воспользовавшись уже созданными очередями и запросив какую-то дополнительную информацию.
3. Создайте файл символьного типа. Организовывая очереди по N элементов, создайте файл слов по N символов в каждом.
4. Создайте файл целого типа. Проанализировав в программе содержимое файла, создайте одну очередь однозначных чисел, а вторую очередь двузначных чисел. Перемножьте соответственные элементы двух очередей и организуйте третью очередь. Результат выведите в текстовый файл.
5. Используя очередь, проверьте, какие строки текстового файла являются симметричными.
6. Используя очередь, проверьте на равенство два текстовых файла.
7. Создать текстовый файл, содержащий текстовую и числовую информацию. Используя стек, создать другой текстовый файл, в котором числа были бы записаны в обратном порядке.
8. Создать текстовый файл, содержащий текстовую информацию. Используя стек, создать другой текстовый файл, в котором слова были бы записаны в обратном порядке.
9. Создать текстовый файл, содержащий некоторую информацию. Используя стек, создать другой текстовый файл, в котором строки были бы записаны в обратном порядке.
10. Создать текстовые файлы, содержащие один текстовую, а другой числовую информацию (количество слов и чисел должно быть одинаковым). Используя стек, создать другой текстовый файл, в котором числа и слова чередовались и были бы записаны в обратном порядке.
11. Создать текстовые файлы, содержащие один текстовую, а другой числовую информацию (количество слов и чисел должно быть одинаковым). Используя стек, создать другой текстовый файл, в котором числа и слова чередовались, а порядок чисел и слов был бы сохранен.
12. Создать текстовые файлы, содержащие один текстовую, а другой числовую информацию (количество слов и чисел может быть неодинаковым). Используя стек, создать другой текстовый файл, в котором числа и слова чередовались и были бы записаны в обратном порядке ("лишние" числа или слова были бы записаны в конец файла).
13. В файле находится текст программы на Си++. Используя стек, проверить правильность вложений операторных скобок ({ }) в этой программе.
14. В файле записан текст, сбалансированный по круглым скобкам. Требуется для каждой пары соответствующих открывающей и закрывающей скобок напечатать номера их позиций в тексте, упорядочив пары номеров по возрастанию номеров позиций закрывающих скобок. Например, для текста a+(45-f(x)*(b-c)) надо напечатать 8 10, 12 16, 3 17.

 

Структуры данных: деревья