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

Очередь (queue) – эта динамическая структура данных, позволяющая добавлять элементы в конец и удалять из начала. Название этой структуры происходит от названия обычной очереди, например, в магазине, когда человек может встать только в конец очереди, а уходит из начала (мы не рассматриваем случай, когда человеку надоело стоять, и он ушел из середины). Очередь называют FIFO-структурой (Fist In – First Out, первым пришел – первым ушел).

Реализация очереди на основе массива во многом напоминает реализацию стека. Отличие заключается в операции удаления: поскольку удаляется первый элемент, то следующие элементы нужно сдвинуть так, чтобы второй элемент стал первым, третий – вторым и т.д. Операция же добавления не отличается, т.к. и в стек, и в очередь элементы добавляются в конец. По этой причине рассмотрим только операцию удаления.

void remove() {

if (n==0) {

cout << "Queue is empty\n";

} else {

//Сдвиг элементов

for (int i=0; i<n-1; i++) {

contents[i] = contents[i+1];

}

n--;

}

}

4.5.5Реализация списка на основе массива

Существуют разные списки, но их классификация не является целью нашего занятия, а важным является то, что список (list) – это такая структура данных, которая позволяет вставлять и удалять элементы в любое место. Идея реализации списка на основе массива напоминает реализации стека и очереди. Следует только учитывать, что при добавлении в произвольное место мы не можем раздвинуть элементы, но должны сдвинуть следующие элементы вправо, чтобы освободилось место для нового. При удалении же следует сдвинуть элементы влево, чтобы занять позицию удаленного элемента (как это сделано в очереди, где элементы сдвигались, чтобы занять позицию первого элемента).

void insert(double x, int pos) {

//Сдвиг элементов вправо

for (int i=n-1; i>=pos; i--) {

contents[i+1] = contents[i];

}

contents[pos] = x;

n++;

}

}

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

1. Что такое динамическая структура данных?

2. Как реализовать динамический массив, используя пометку элементов.

3. Какие операции поддерживает стек?

4. Какие операции поддерживает очередь?

5. Какие операции поддерживает список?

6. Что такое LIFO-структура и FIFO-структура?

7. Реализуйте динамический массив, используя пометку элементов и пометку элементов с оберткой.

8. Реализуйте стек на основе массива.

9. Реализуйте очередь на основе массива.

10. Реализуйте список на основе массива.

Глоссарий

Алгоритм – последовательность шагов (действий), позволяющая решить определенную задачу.

Аргументы фактические – аргументы, указываемые при вызове функции.

Аргументы формальные – аргументы, указываемые при объявлении функции.

Аргумент функции – параметр, который можно передать в тело функции извне.

Блок-схема – представление алгоритма в виде диаграммы.

Выражение смешанное – выражение, в котором присутствуют величины разных типов.

Декрементирование – уменьшение на 1.

Идентификатор – название какого-либо элемента программного кода, вводимого программистом.

Инкрементирование – увеличение на 1.

Инициализация переменной – присвоение значения переменной при ее объявлении.

Итерация – одно повторения команд, расположенных в теле цикла.

Ключевое слово – слова, зарезервированные

Комментарий – фрагмент исходного кода, игнорируемый компилятором.

Компиляция – процесс преобразования исходного кода в исполняемый файл.

Константа – постоянная величина.

Массив – это набор переменных одного типа, обращение к которым производится по имени массива и индексу элемента.

Матрица – двумерный массив.

Метод – это функция в объектно-ориентированном программировании.

Объявление функции – указание сигнатуры функции в программном коде.

Объявление переменной – указание типа и имени переменной в программном коде.

Операнд – величина, над которой производится операция.

Операция бинарная – операция, производящая действия над двумя операндами.

Операция логическая – операция, производящая действия над операндами логического типа. Логическими операциями являются «и», «или», «не», «xor».

Операция унарная – операция, производящая действия над одним операндом.

Определение функции – указание сигнатуры и тела функции.

Очередь (queue) – структура данных, поддерживающая две основные операции: добавление элемента в конец и удаление элемента из начала. Очередь по-другому называется FIFO-структурой.

Ошибка алгоритмическая – ошибка, которая заключается в том, что программа запускается (не содержит синтаксических ошибок), но не приводит к запланированному результату.

Ошибка времени исполнения (run-time error) – ошибка, которая возникает в момент работы программы.

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

Переменная (variable) – именованная ячейка памяти.

Переменная локальная – переменная, объявленная внутри тела цикла, функции, условного оператора и т.д.

Переменная глобальная – переменная, объявленная вне тела цикла, функции, условного оператора и т.д.

Приведение типа – явное преобразование типа величины в выражении.

Процедура (procedure) – это функция, которая не возвращает значения.

Псевдокод (pseudocode) – представление алгоритма на языке, напоминающем язык программирования.

Рекурсивная функция – функция, вызывающая сама себя.

Сигнатура функции – совокупность следующих свойств у функции: тип возвращаемого значения, имя и формальные аргументы.

Среда разработки интегрированная (integrated development environment) – приложение, включающее в себя редактор программного кода и набор инструментов, облегчающих разработка программ.

Стек (stack) – структура данных, поддерживающая две основные операции: добавление элемента в конец и удаление элемента из конца. Стек по-другому называется LIFO-структурой.

Строка (string) – последовательность символов.

Структура (structure) – набор переменных разных типов, объединенных общим именем.

Структура данных динамическая – структура данных, которая может изменять свой размер в процессе работы программы.

Тело цикла – совокупность команд, повторяемых в цикле.

Тело функции – совокупность команд, выполняемых функцией.

Тестирование – процесс поиска алгоритмических ошибок и ошибок времени исполнения в программе.

Тип переменной – множество возможных значений переменной.

Условный оператор – оператор, позволяющий выбирать путь выполнения программы в зависимости от некоторого условия.

Файл – именованная последовательность байтов

Функция (function) – это подпрограмма, которая выполняет отдельную задачу.

Функция логическая – функция, которая возвращает значение логического типа, принимающего два значения: «истина» и «ложь».

Цикл вложенный – цикл, расположенный в теле другого цикла.