Задание

1. Приведите пример очереди.

2. Объясните, что означает понятие максимальная длина очереди.

3. Какие основные действия проводятся с очередью?

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

1.4.3 Стек

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

Стек – частный случай линейного списка, для которого разрешено добавлять или убирать элементы только с одного конца списка, который называется вершиной (головой) стека.

(рис)

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

Основные действия над стеком

Для того, чтобы посмотреть какие действия мы можем проводить с данными, которые организованны в стек введем так же несколько определений.

Максимальная глубина стека – Максимально возможное количество элементов которое может находиться в стеке одновременно.

Глубина стека - характеризует количество элементов находящихся в стеке в данный конкретный момент.

Пустой стек - Стек в котором нет элементов, глубина стека равна нулю.

Первое действие поместить элемент в стек:

Взять элемент из стека:

Дек

Дек - Линейный список, в котором все добавления и удаления элементов делаются на обоих концах списка

(рис)

Дек называют очередью с двумя концами или двухсторонней очередью.

Задание

1. Приведите пример стека.

2. Объясните, что означает понятие максимальная глубина стека.

3. Какие основные действия проводятся со стеком?

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

Структурное программирование. Объектно-ориентированное программирование. Визуальное программирование.

При рассмотрении процесса составления структуриро­ванных программ я придерживаюсь понятия «умозрительная» машина, предложенного Э. Дейкстрой. Допустим, нам необходимо выполнить некоторые действия, например: нам необходимо, чтобы она смогла приготовить нам чай. Если она достаточно умна, то после команды «Приготовь чай», сама выполнит необхо­димые действия. Но пока такой машины нет в нашем распоряжении, мы вынуждены давать более подробные инструкции:

Шаг 1.

1. Подготовить материалы для приготовления чая.

2. Приготовить чай.

3. Закончить работу.

Шаг 2.

1. Подготовить материалы для приготовления чая.

1.1. Определить есть ли емкость для воды.

1.2. Определить есть ли вода.

1.3. Определить наличие заварки.

1.4. Определить есть ли чем нагреть воду.

2. Приготовить чай.

2.1. Набрать в емкость воду.

2.2. Довести воду до кипения.

2.3. Заварить чай.

3. Закончить работу.

............................

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

Обратите внимание, что при детализации необходимых действий мы не стремимся сразу оговаривать, как де­лать, а говорим о том, что необходимо делать. При про­ведении детализации существует следующее правило: Не принимайте ответственных решений. То есть, старайтесь не взваливать всю работу на «умозрительную» машину верхнего уровня, передавайте большую часть работы на «умозрительную» машину более низкого уровня. Так, пока неизвестно, какая емкость для воды у нас имеется на вто­ром шаге, мы не говорим, что именно берем. Для сравнения - Случай 2 - что бы мы делали, если бы у нас не было чай­ника.

Детализация (подключение «умозрительных» машин более низкого уровня) проводится до тех пор, пока реальная машина не сможет выполнить указание. Более того, если следовать этому подходу в случае написания программы, в конечном итоге Вы получите готовый текст программы.

В чем преимущества структурного подхода к програм­мированию?

1. Можно ожидать, что логика работы программы будет более понятна программирующему.

2. Если Вы пока не знаете, как реализовать какой-либо модуль, всегда можно поставить «умозрительную» машину, которая ничего не делает (см. Случай 1)

3. Возможность «работать» (программировать) с отдель­ным модулем.

4. Независимость «умозрительных» машин одного уровня позволяет независимо модифицировать блоки про­граммы без затрагивания других блоков. Как отмечал Э. Дейкстра - “..модификации программ могут быть теперь представлены заменой одной (умозрительной) машины дру­гой подходящей машиной”.

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

6. Можно ожидать, что это оградит нас от ненужной ра­боты. Если нет заварки, наша программа просто завершит работу, а программа «Случай 2» проведет все действия от 1 до 5-го - пока выяснится, что нет заварки.

7. “Структурный подход” позволяет проводить целена­правленную подготовку учащихся к решению олимпиадных задач. Если модули независимы друг от друга, то можно заранее подготовить “машины нижнего уровня”, например: блок сортировки, блок поиска в глубину, поиска в ширину, блок обработки входной информации и т.д. и исходя из задачи использовать их в том или ином сочетании.

Небольшое замечание. Часто сравнивая языки программирования, говорят, что Паскаль структурированный язык, а, например Бейсик - нет. Что один язык лучше дру­гого. Хочется напомнить таким спорщикам следующее - каждый язык программирования наиболее удобен для опре­деленного круга задач. Например, для задач связанных с искусственным интеллектом, возможно, более подходит язык Пролог, для задач связанных с вычислениями лучше Фор­трана вряд ли что можно предложить и т.д. И на “структурированном” Паскале можно писать "неструктури­рованные" программы и на “неструктурированном” Бейсике хорошо "структурированную" программу.

Иногда сравнивая структурное программирование с объектно-ориентированным и визуальным программированием, представляют последние как более высокую ступень программирования. Это не так, объектно-ориентированное программирование, как и визуальное программирование, это лишь способы программирования, тогда как структурное программирование это методология и идеология программирования.