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