Задачи этого раздела подразумевают реализацию стеков (stack), очередей (queue) и дек (deque) на базе массивов и связных списков. Для тестирования решений используются материалы сайта ecrayon-olimp.com. После того как Вы убедились, что программа работает, необходимо отправить решение на сайт e-olimp.com для тестирования. Решение должно пройти все тесты. Программа не должна использовать каких=либо библиотечных структур данных явно или неявно предоставляющих функциональность стека или очереди. Можно использовать только массивы и связные списки.
Стек = Stack
- Простой стек. Для решения задачи необходимо использовать массив.
- Стек с защитой от ошибок. Для решения задачи необходимо использовать массив.
- Стек неограниченного размера Возможно использовать один из трех вариантов реализации:
- Связный список. Недостатки: отсутствие прямого доступа к значению элемента массива по его индексу; дополнительный расход памяти на хранение ссылки на следующий элемент списка.
- Пример простой реализации с ООП.
- Пример реализации с генерацией исключений
- Динамические массивы с переносом значений в новый расширенный массив при переполнении исходного. Недостатки: вычислительные затраты на копирование массива; более чем удвоенный объем памяти на момент расширения хранилища.
- Кластерная реализация: список массивов. Простая реализация стека в виде массива фиксированного размера, но с добавлением нового массива при переполнении предыдущего. Для каждого массива в списке хранится номер первого элемента в нем. Наиболее эффективный по соотношению расхода памяти и скорости работы при правильном выборе размера массивов.
- Связный список. Недостатки: отсутствие прямого доступа к значению элемента массива по его индексу; дополнительный расход памяти на хранение ссылки на следующий элемент списка.
Очередь = Queue
- Простая очередь. Для решения задачи необходимо использовать массив.
- Очередь с защитой от ошибок. Для решения задачи необходимо использовать массив.
- Очередь неограниченного размера Возможно использовать один из трех вариантов реализации:
- Связный список. Недостатки: отсутствие прямого доступа к значению элемента массива по его индексу; дополнительный расход памяти на хранение ссылки на следующий элемент списка.
- Динамические массивы с переносом значений в новый расширенный массив при переполнении исходного. Недостатки: вычислительные затраты на копирование массива; более чем удвоенный объем памяти на момент расширения хранилища.
- Кластерная реализация: список массивов. Простая реализация стека в виде массива фиксированного размера, но с добавлением нового массива при переполнении предыдущего. Для каждого массива в списке хранится номер первого элемента в нем. Наиболее эффективный по соотношению расхода памяти и скорости работы при правильном выборе размера массивов.
Дек (дека) = Deque
- Простой дек. Для решения задачи необходимо использовать массив.
- Дек с защитой от ошибок. Для решения задачи необходимо использовать массив.
- Дек неограниченного размера Возможно использовать один из трех вариантов реализации:
- Двунаправленный связный список. Недостатки: отсутствие прямого доступа к значению элемента массива по его индексу; дополнительный расход памяти на хранение ссылки на следующий элемент списка.
- Динамические массивы с переносом значений в новый расширенный массив при переполнении исходного. Недостатки: вычислительные затраты на копирование массива; более чем удвоенный объем памяти на момент расширения хранилища.
- Кластерная реализация: двунаправленный список массивов. Простая реализация стека в виде массива фиксированного размера, но с добавлением нового массива при переполнении предыдущего. Для каждого массива в списке хранится номер первого элемента в нем. Наиболее эффективный по соотношению расхода памяти и скорости работы при правильном выборе размера массивов.
Решения задач
Решения задач
- 6130. Дек неограниченного размера
Опубликовал 21/05/2017Валентина АндриешУсловие задачи: Реализуйте структуру данных «дек». Напишите программу, содержащую описание дека и моделирующую работу дека, реализовав все указанные здесь методы. Программа ...
- A1048
Опубликовал 11/06/2015Кваша Дар`я МихайлівнаЗадача. Одним из наиболее часто встречающихся видов списка является стек-список, в котором все включения и исключения элементов делаются только на ...
- A302. Количество различных цифр числа в его десятичной записи
Опубликовал 09/05/2017Андреев ДаниилЗадача Дано натуральное число . Сколько различных цифр встречается в его десятичной записи? Входные данные Натуральное число . Выходные данные Количество различных цифр . Тесты Входные данные Выходные ...
- A303. Вычисления с хранением последовательности значений
Опубликовал 10/12/2017Сытников ДанУсловие задачи Даны действительные числа , где ...
- AL13
Опубликовал 31/03/2016Молоканов ЮрийУсловие Имеется черных и белых карточек, сложенных в стопку. Карточки раскладываются на стол в одну линию следующим образом: первая кладется ...
- AL15. Лабиринт
Опубликовал 11/04/2016Сплошнов КириллУсловие Матрица размера определяет свободное место. В первой строке ...
- AL6
Опубликовал 26/05/2016Андрей ЯроцкийЗадача AL6 Условие Дана конечная последовательность, состоящая из левых и правых скобок различных заданных типов. Как определить, можно ли добавить в нее цифры ...
- e-olimp 1098. Ходи ферзем!
Опубликовал 01/05/2015Денисова ОльгаЗадача. На шахматной доске 8х8 произвольным образом расставлено 8 ферзей, по одному на каждой вертикали, других фигур на доске нет. Ферзь ...
- e-olimp 122. Горные маршруты
Опубликовал 02/04/2015Вустянюк Ігор ДмитровичЗадача. Горный туристический комплекс состоит из n турбаз, соединенных между собой k горными переходами (другие маршруты в горах опасны). Любой ...
- e-olimp 1667. Конденсация графа
Опубликовал 29/03/2015Ілларіонова Марія ВалеріївнаЗадача e-olimp.com №1667. Ссылка на засчитанное решение. Вам задан связный ориентированный граф с \left(1\leq N\leq 20000, 1\leq M\leq ...
- e-olimp 2510. Сортировка очередями
Опубликовал 02/04/2015Іванов Вячеслав Володимировичe-olimp 2510. Сортировка очередями Постановка задачи Рассматривается специальное устройство, содержащее входной поток, выходной поток и k очередей, пронумерованных числами от до ...
- e-olimp 3809. ГАС Очередь
Опубликовал 02/04/2015Ілларіонова Марія ВалеріївнаЗадача e-olimp.com №3809. Ссылка на засчитанное решение. За последние несколько лет электронные очереди прочно вошли в повседневную жизнь. Во многих государственных ...
- e-olimp 3837. Выражения
Опубликовал 05/04/2015Вустянюк Ігор ДмитровичЗадача Арифметические выражения, как правило, записываются с операторами между двумя операндами (такая запись называется инфиксной нотацией). Например, (x + y) * ...
- e-olimp 4000. Обход в глубину
Опубликовал 30/04/2015Ковальський Олександр ДмитровичЗадача e-olimp 4000 Дан неориентированный невзвешенный граф, в котором выделена вершина. Вам необходимо найти количество вершин, лежащих с ней в одной компоненте ...
- e-olimp 4004. Есть ли цикл?
Опубликовал 22/03/2015Карташов Денис ГеннадійовичЗадача: Дан ориентированный граф. Требуется определить, есть ли в нём цикл. Технические условия: Входные данные: В первой строке вводится натуральное число N ( ...
- e-olimp 4513. Сортировка вагонов — B
Опубликовал 28/04/2015Кібакова Надія ОлександрівнаСортировка вагонов — B К тупику со стороны пути 1 (см. рисунок) подъехал поезд. Разрешается отцепить от поезда один или сразу несколько ...
- e-olimp 4847. Очередь с приоритетами
Опубликовал 07/04/2015Швандт Максим АльбертовичУсловие: Реализуйте структуру «очередь с приоритетами», поддерживающую следующие операции: Добавление элемента в очередь. Удаление из очереди элемента с наибольшим приоритетом. Изменение приоритета для ...
- e-olimp 553. Рекурсия
Опубликовал 20/03/2015Бронфен-Бова РоманЗадача: Рекурсия Решение ссылка на ideone, засчитанное решение на e-olimp Решение C++ #include<iostream> #include<vector> #include<set> #include<map> #include<string> using namespace std; map<string,set<string>> G; map<string,bool> used; map<string,bool> rec; vector<string> V; void dfs(string cur, string aim){ if(used ...
- e-olimp 6124. Стек неограниченного размера
Опубликовал 18/03/2015Ілларіонова Марія ВалеріївнаСтек неограниченного размера Реализуйте структуру данных «стек«. Напишите программу, содержащую описание стека и моделирующую работу стека, реализовав все указанные здесь методы. ...
- e-olimp 6129. Дек с защитой от ошибок
Опубликовал 26/05/2016Радик СиденкоЗадача: Реализуйте структуру данных «дек«. Напишите программу, содержащую описание дека и моделирующую работу дека, реализовав все указанные здесь методы. Программа считывает ...
- e-olimp 6130. Дек неограниченного размера (как список деков)
Опубликовал 26/03/2015Вустянюк Ігор ДмитровичКак пишет Википедия в статье Double-Ended Queue, есть три основных способа реализации двухсторонней очереди (она же — дек, дека и ...
- e-olimp 6130. Дек неограниченного размера.
Опубликовал 01/04/2015Карташов Денис ГеннадійовичЗадача: Реализуйте структуру данных «дек«. Напишите программу, содержащую описание дека и моделирующую работу дека, реализовав все указанные здесь методы. Программа считывает ...
- e-olimp 693. Минимум в стеке
Опубликовал 19/03/2015Ілларіонова Марія ВалеріївнаЗадача e-olimp.com №693. На вход программы подается набор операций со стеком. Каждая операция состоит в добавлении или удалении элемента из ...
- e-olimp 695. Range Variation Query
Опубликовал 30/04/2015Недомовний ВладиславЗадача e-olimp 695. Последовательность . Требуется много раз отвечать на запросы следующего вида: найти разность ...
- e-olimp: 694. Минимум в очереди
Опубликовал 27/03/2015Іванов Вячеслав Володимировичe-olimp: 694 — Минимум в очереди Постановка задачи На вход программы подается набор операций с очередью. Каждая операция состоит в добавлении или ...
- e-olymp 1060. Линии
Опубликовал 28/06/2016Кондратюк НастяЗадача взята с сайта e-olymp.com. Условие задачи В таблице из столбцов некоторые клетки заняты шариками, другие свободны. Выбран шарик, ...
- e-olymp 1061. Покраска лабиринта
Опубликовал 19/05/2015Сорокина ПолинаЗадача e-olimp 1061. Лабиринт представляет собой квадрат, состоящий из N×N сегментов. Каждый из сегментов может быть либо пустым, либо заполненным камнем. Гарантируется, ...
- e-olymp 1266. CD
Опубликовал 18/06/2015Байков ДмитроВам предстоит длительное путешествие на автомобиле. К сожалению, у Вас в машине есть только магнитофон, а лучшая музыка записана на ...
- e-olymp 1776. Рельсы
Опубликовал 29/06/2015Куленюк Денис ВіталійовичСсылка на условие задачи: http://www.e-olymp.com/ru/problems/1776. Ссылка на засчитанное решение. В городе PopPush находится известная железнодорожная станция. Страна, в котором находится город, невероятно ...
- e-olymp 1872. Снеговики
Опубликовал 18/06/2015Карагяур Мілан СергійовичЗадача: Зима. 2012 год. На фоне грядущего Апокалипсиса и конца света незамеченной прошла новость об очередном прорыве в областях клонирования и ...
- e-olymp 1948. Топологическая сортировка
Опубликовал 06/06/2016Грешилов КонстантинУсловие: Дан ориентированный невзвешенный граф. Необходимо топологически отсортировать его вершины. Входные данные В первой строке содержатся количество вершин ≤ ...
- e-olymp 2270. Поиск цикла
Опубликовал 02/12/2019Наташа ПисаревскаяЗадача Дан ориентированный невзвешенный граф. Необходимо определить есть ли в нём циклы, и если есть, то вывести любой из них. Входные данные В ...
- e-olymp 2479. Баланс скобок
Опубликовал 13/06/2015Царев Николай АлександровичУсловие (Ссылка на задачу в e-olymp) Имеется строка, содержащая скобки () и . Скобочное выражение считается правильным, если: оно является пустым если A и ...
- e-olymp 2820. Перемещение коня
Опубликовал 31/03/2016Молоканов ЮрийУсловие Ваш друг проводит научные исследования по проблеме Конского Минимального Путешествия (КМП), которая состоит в том, чтобы найти кратчайший замкнутый тур ...
- e-olymp 2820. Перемещение коня
Опубликовал 30/06/2015Янішевська Альона РусланівнаЗадача с сайта e-olimp №2820. Перемещение коня Ваш друг проводит научные исследования по проблеме Конского Минимального Путешествия (КМП), которая состоит в том, ...
- e-olymp 4002. Down with cheating!
Опубликовал 10/04/2016Таран ТаняDuring the test, Professor Floyd noticed that some students exchanged notes. At first, he wanted to put a bad mark ...
- e-olymp 4050. Забавная игра
Опубликовал 29/06/2015Зелінський Вячеслав ОлександровичСсылка на задачу. Засчитанное решение. В одной стране есть несколько аэропортов, между некоторыми аэропортами есть рейсы. Можно перелететь из любого аэропорта в ...
- e-olymp 432. Подземелье
Опубликовал 20/05/2015Царев Николай АлександровичПодземелье Вы попали в 3D подземный лабиринт и необходимо найти быстрый выход! Карта подземелья составлена из единичных кубических комнат, по ...
- e-olymp 4514. Сортировка вагонов — А
Опубликовал 26/06/2015Сіренко Валерія СергіївнаЗадача К тупику со стороны пути 1 (см. рисунок) подъехал поезд. Разрешается отцепить от поезда один или сразу несколько первых вагонов ...
- e-olymp 6122. Простой стек
Опубликовал 20/03/2016Таня КорниловаЗадача. Реализуйте структуру данных «стек». Напишите программу, содержащую описание стека и моделирующую работу стека, реализовав все указанные здесь методы. Программа ...
- e-olymp 6122. Простой стек
Опубликовал 13/12/2017Курьянов ПавелЗадача Реализуйте структуру данных «стек». Напишите программу, содержащую описание стека и моделирующую работу стека, реализовав все указанные здесь методы. Программа считывает ...
- e-olymp 6123. Стек с защитой от ошибок
Опубликовал 01/06/2016Максим НосовЗадача Стек с защитой от ошибок Реализуйте структуру данных «стек«. Напишите программу, содержащую описание стека и моделирующую работу стека, реализовав все указанные ...
- e-olymp 6124. Стек неограниченного размера
Опубликовал 27/05/2016Станислав КоциевскийЗадача Реализуйте структуру данных «стек«. Напишите программу, содержащую описание стека и моделирующую работу стека, реализовав все указанные здесь методы. Программа считывает ...
- e-olymp 6125. Простая очередь
Опубликовал 31/03/2016Антон ЛоктевЗадача Реализуйте структуру данных «очередь«. Напишите программу, содержащую описание очереди и моделирующую работу очереди, реализовав все указанные здесь методы. Программа считывает ...
- e-olymp 6127. Очередь неограниченного размера
Опубликовал 15/04/2016Катя ПисоваЗадача Реализуйте структуру данных «очередь«. Напишите программу, содержащую описание очереди и моделирующую работу очереди, реализовав все указанные здесь методы. Программа считывает ...
- e-olymp 6128. Простой дек
Опубликовал 01/06/2017Сабиров ИльдарЗадача. Простой дек Реализуйте структуру данных «дек». Напишите программу, содержащую описание дека и моделирующую работу дека, реализовав все указанные здесь методы. ...
- e-olymp 6128. Простой дек
Опубликовал 04/04/2016Кудымовская ВикаЗадача. Простой дек Условие задачи Реализуйте структуру данных «дек«. Напишите программу, содержащую описание дека и моделирующую работу дека, реализовав все указанные здесь методы. ...
- e-olymp 6128. Простой дек
Опубликовал 08/05/2017Андреев ДаниилЗадача Реализуйте структуру данных «дек». Напишите программу, содержащую описание дека и моделирующую работу дека, реализовав все указанные здесь методы. Программа считывает ...
- e-olymp 8669. Все делители
Опубликовал 14/12/2019Катя РоманцоваУсловие задачи Найдите все делители натурального числа $n$. Входные данные Одно натуральное число $ n ( n \leqslant 10^9 ) $. Выходные данные Выведите в ...
- e-olymp 982. Связность
Опубликовал 15/05/2016Женя МаксимоваЗадача. Проверить, является ли заданный неориентированный граф связным, то есть что из любой вершины можно по рёбрам этого графа попасть ...
- Алгоритмы поиска
Опубликовал 16/11/2019Мазурок Игорь ЕвгеньевичХочу предложить простой, но достаточно общий взгляд на алгоритмы поиска в ширину BFS (Breadth-first Search), в глубину DFS (Depth-first Search) ...
- Стек, дек и очередь неограниченного размера
Опубликовал 19/03/2015Бронфен-Бова РоманЗадачи: Стек, Очередь и Дек Решение: Код для задачи на неограниченный стек: 6124 C++ #include <iostream> #include <string> using namespace std; struct Node{ Node * prev; int x; Node(){prev = nullptr; ...