Теоретический материал: стеки, очереди, деки (С++)

Стек, очередь, дек

Стек

Стеком (англ. 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: Очистить дек (удалить из него все элементы)

Упражнение G - простой дек

Аналогично заданиям A и D, но для дека. Количество элементов в деке в любой момент не превосходит 100. Все операции pop_front, pop_back, front, back всегда корректны.

Упражнение H - дек с обработкой ошибок

Аналогично заданиям B и E, но для дека. Количество элементов в деке в любой момент не превосходит 100. При выполнении некорректных операций необходимо вывести error.

Упражнение I - дек неограниченного размера

Аналогично заданиям C и F, но для дека. Необходимо увеличивать размер дека при увеличении числа элементов в нем. При выполнении некорректных операций необходимо вывести error.