Стек, очередь, декСтекСтеком (англ. stack) называется хранилище данных, в котором можно работать только с одним элементом: тем, который был добавлен в стек последним. Стек должен поддерживать следующие операции:
Хранить элементы стека мы будем в массиве. Для начала будем считать, что максимальное количество элементов в стеке не может превосходить константы Объявим структуру данных типа
const int MAX_SIZE=1000;
struct stack {
int m_size; // Количество элементов в стеке
int m_elems[MAX_SIZE]; // Массив для хранения элементов
stack(); // Конструктор
~stack(); // Деструктор
void push(int d); // Добавить в стек новый элемент
int pop(); // Удалить из стека последний элемент
// и вернуть его значение
int back(); // Вернуть значение последнего элемента
int size(); // Вернуть количество элементов в стеке
void clear(); // Очистить стек
};
Объявленная здесь структура данных Упражнение A - простой стекРеализуйте структуру данных "стек", реализовав все указанные здесь методы. Напишите программу (функцию
Гарантируется, что набор входных команд удовлетворяет следующим требованиям: максимальное количество элементов в стеке в любой момент не превосходит 100, все команды Пример протокола работы программы Ввод Вывод push 2 ok push 3 ok push 5 ok back 5 size 3 pop 5 size 2 push 7 ok pop 7 clear ok size 0 exit bye Упражнение B - стек с обработкой ошибокАналогично предыдущему заданию, только снимается ограничение на корректность вызовов методов При этом должна быть реализована двойная защита: вызов методов Пример протокола работы программы Ввод Вывод push 2 ok back 2 pop 2 size 0 pop error push 1 ok size 1 exit bye Упражнение C - стек без ограничения на размерРеализуйте стек динамического размера, то есть ограниченный только объемом свободной оперативной памяти. Для этого используйте указатели и динамически распределяемую память. Если для полностью заполненного стека вызывается метод ОчередьОчередью (aнгл. queue)) называется структура данных, в которой элементы кладутся в конец, а извлекаются из начала. Таким образом, первым из очереди будет извлечен тот элемент, который будет добавлен раньше других. Элементы очереди будем также хранить в массиве. При этом из очереди удаляется первый элемент, и, чтобы не сдвигать все элементы очереди, будем в отдельном поле Описание структуры очередь:
const int MAX_SIZE=1000;
struct queue {
int m_size; // Количество элементов в очереди
int m_start; // Номер элемента, с которого начинается очередь
int m_elems[MAX_SIZE]; // Массив для хранения элементов
queue(); // Конструктор
~queue(); // Деструктор
void push(int d); // Добавить в очередь новый элемент
int pop(); // Удалить из очереди первый элемент
// и вернуть его значение
int front(); // Вернуть значение первого элемента
int size(); // Вернуть количество элементов в очереди
void clear(); // Очистить очередь
};
Упражнение D - простая очередьРеализуйте простейшую очередь, размер которой не превосходит 100 элементов. Очередь поддерживает те же операции, что и стек, за исключением операции Упражнение E - очередь с обработкой ошибокАналогично заданию B, но для очереди. Операции Программа должна содержать "двойную защиту" от некорректных операций: как в функции Упражнение F - очередь без ограничений на размерАналогично заданию C, но для очереди. Необходимо реализовать очередь, память для которой динамически выделяется при увеличении количества элементов в ней. ДекДеком (англ. deque – аббревиатура от double-ended queue, двухсторонняя очередь) называется структура данных, в которую можно удалять и добавлять элементы как в начало, так и в конец. Дек хранится в памяти так же, как и очередь. Система команд дека:
|
