Постановка задачи

Рассмотреть и реализовать:

1. Создание стека

Добавление элемента в стек.

Освобождение памяти, выделенное под данный элемент.

2. Создание очереди

Добавление элемента в очередь.

Освобождение памяти, выделенное под данный элемент.

3. Создание дека

Освобождение памяти, выделенное под данный элемент.

Удаление элемента из дека.

Анализ предметной области

Принципы работы стека

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

Наиболее простой из них является стек, представляющий собой последовательность объектов данных, связанных между собой с помощью указателей.

Организация структуры стека

Каждый объект стека связан с последующим с помощью указателя next. Если указатель next равен NULL, то достигнут конец стека. Особенность работы со стеком заключается в том, что новый объект всегда добавляется в начало списка. Удаление также возможно только для первого элемента. Таким образом, данная структура реализует очередь по принципу <первым вошел, последним вышел>. Такой принцип характерен при вызове функций в рекурсии, когда адрес каждой последующей функции записывается в стеке для корректной передачи управления при ее завершении.

Основные операции, которые используются при применении стека:

· Сделать пустым.

· Добавить элемент. Запись возможна только в верхнюю ячейку стека, при этом вся хранящаяся в стеке информация предварительно проталкивается на одну позицию вниз.

· Взять элемент. Чтение допустимо также только из вершины стека. Извлеченная информация удаляется из стека, а оставшееся его содержимое продвигается вверх.

· Стек пуст.

· Вершина стека: Т.

Процедура <сделать пустым> делает стек пустым, то есть <на дне стека ничего нет>.

Процедура <добавить элемент> добавляет элемент X, типа T, в начало последовательности.

Процедура <взять элемент> применима, если последовательность S

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

Выражение <стек пуст> истинно, если последовательность S пуста.

Выражение <вершина стека> определенно, если последовательность S не пустая, и равно последнему элементу последовательности S.

Особенно явно преимущества стековой организации проявляются при работе в сложных ситуациях, возникающих в программных системах, где на ограниченные ресурсы претендуют несколько конкурирующих задач. Такие ситуации могут встречаться в различных ЭВМ, начиная от небольших однопользовательских систем (при необходимости совместить выполнение фоновой задачи с вводом-выводом) до сложных мультипрограммных систем, управляющих комплексом пользовательских и системных программ. В любом случае от программного обеспечения требуется гибкость, экономия времени выполнения и используемой памяти.

В большинстве процессоров стек (т.е. память со стековым доступом) организован в участке обычной памяти с адресной организацией. Для этого в процессоре имеется специальный регистр - указатель стека Stack Pointer SP. Этот регистр содержит адрес памяти того участка, в который будет осуществляться стековый доступ, а, говоря более точно, адрес "верхушки стека". Указатель стека обычно программно доступен, то есть к нему можно производить обращение как к любому другому регистру.