Стеком (англ. stack) называется хранилище данных, в котором можно работать только с одним элементом: тем, который был добавлен в стек последним. Стек должен поддерживать следующие операции:
Хранить элементы стека мы будем в массиве. Для начала будем считать, что максимальное количество
элементов в стеке не может превосходить константы MAX_SIZE
, тогда для хранения элементов
массива необходимо создать массив размера MAX_SIZE
.
Объявим структуру данных типа 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(); // Очистить стек };
Объявленная здесь структура данных stack
реализует стек целых чисел. Поле структуры
m_size
хранит количество элементов в стеке в настоящее время, сами элементы хранятся
в элементах массива m_elems
с индексами 0..m_size-1
. Элементы, добавленные позже,
получают большие номера.
Реализуйте структуру данных "стек", релизовав все указанные здесь методы.
Напишите программу (функцию main
), содержащую описание стека и моделирующую работу стека.
Функция main
считывает последовательность команд и в зависимости от команды выполняет
ту или иную операцию. После выполнения одной команды программа должна вывести одну строчку.
Возможные команды для программы:
ok
.
ok
.
bye
и завершить работу.
Гарантируется, что набор входных команд удовлетворяет следующим требованиям: максимальное количество элементов
в стеке в любой момент не превосходит 100, все команды pop_back
и back
корректны, то есть при их исполнении
в стеке содержится хотя бы один элемент.
Пример протокола работы программы
Ввод Вывод 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
Аналогично предыдущему заданию, только снимается ограничение на корректность вызовов методов back
и pop
.
Данные операции должны перед исполнением проверять, содержится ли в стеке хотя бы один элемент. Если во входных данных
встречается операция back
или pop
, при этом стек пуст, то программа должна вместо числового значения вывести
строку error
.
При этом должна быть реализована двойная защита: вызов методов forward
и pop
для пустого стека
не должен приводить к обращению к несуществующим элементам массива m_elems
, а функция main
должна
выводить сообщение error
, при считывании некорректной операции.
Пример протокола работы программы
Ввод Вывод push 2 ok back 2 pop 2 size 0 pop error push 1 ok size 1 exit bye
Реализуйте стек динамического размера, то есть ограниченный только объемом свободной оперативной памяти.
Для этого используйте указатели и динамически распределяемую память. Если для полностью заполненного стека
вызывается метод push
размер динамического массива, отведенного для хранения стека, должен увеличиваться.
Очередью (aнгл. queue)) называется структура данных, в которой элементы кладутся в конец, а извлекаются из начала. Таким образом, первым из очереди будет извлечен тот элемент, который будет добавлен раньше других.
Элементы очереди будем также хранить в массиве. При этом из очереди удаляется первый элемент, и, чтобы не сдвигать
все элементы очереди, будем в отдельном поле m_start
хранить индекс элемента массива, с которого начинается
очередь. При удалении элементов, очередь будет "ползти" дальше от начала массива. Чтобы при этом не происходил выход
за границы массива, замкнем массив в кольцо: будем считать, что за последним элементом массива следует первый.
Описание структуры очередь:
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(); // Очистить стек };
Реализуйте простейшую очередь, размер которой не превосходит 100 элементов.
Очередь поддерживает те же операции, что и стек, за исключением операции back
,
которая заменена операцией front
. Операции front
и pop
всегда корректны.
Аналогично заданию B, но для очереди. Операции front
и pop
могут
быть некорректными, в этом случае необходимо вывести error
.
Программа должна содержать "двойную защиту" от некорректных операций:
как в функции main
, так и в самих методах pop
и front
.
Аналогично заданию C, но для очереди. Необходимо реализовать очередь, память для которой динамически выделяется при увеличении количества элементов в ней.
Деком (англ. deque – аббревиатура от double-ended queue, двухсторонняя очередь) называется структура данных, в которую можно удалять и добавлять элементы как в начало, так и в конец. Дек хранится в памяти так же, как и очередь. Система команд дека:
Аналогично заданиям A и D, но для дека. Количество элементов в деке в любой момент не превосходит 100.
Все операции pop_front
, pop_back
, front
, back
всегда корректны.
Аналогично заданиям B и E, но для дека. Количество элементов в деке в любой момент не превосходит 100.
При выполнении некорректных операций необходимо вывести error
.
Аналогично заданиям C и F, но для дека. Необходимо увеличивать размер дека при увеличении числа элементов в нем.
При выполнении некорректных операций необходимо вывести error
.