Лабораторная работа № 4
Структура даних „ЧЕРГА”
Змоделюйте чергу (або дек) згідно з завданням. Перепишіть модуль, що містить набір основних операцій для роботи з чергою (деком), і продемонструйте його застосування для операцій додавання і вилучення елементів в чергу (дек). Для цього задайте послідовність з N цілих чисел. Всі додатні числа послідовно заносяться в чергу (дек), кожне від’ємне число вилучає з черги (деку) один елемент (при роботі з деком, парні числа працюють з одним кінцем деку, а непарні – з іншим). Показувати всі зміни, що будуть відбуватись у черзі (деку).
Змоделюйте циклічну чергу, в якій реалізований такий механізм додавання нового елемента: якщо досягнутий кінець масиву, то новий елемент додається в перший елемент масиву, якщо це можливо.
Змоделюйте структуру даних ДЕК з обмеженим виходом (тобто додавати в дек можна з обох кінців, а вилучати тільки з одного). Дек представити за допомогою вказівників.
Змоделюйте чергу, в якій кінець черги вказує не на останній елемент черги, а на перший вільний елемент масиву.
Змоделюйте чергу, в якій реалізований такий механізм вилучення елемента з черги: початок черги завжди знаходиться в першому елементі масиву; при вилученні одного елемента з черги, всі решта елементів пересуваються на одну позицію ближче до початку масиву.
Змоделюйте структуру даних ДЕК з обмеженим входом (тобто вилучати з дека можна з обох кінців, а додавати тільки з одного). Дек представити за допомогою вказівників.
Змоделюйте чергу, в якій задається початок черги і довжина черги (замість кінця черги). Чергу представити за допомогою масиву.
Змоделюйте структуру даних ДЕК (тобто додавати i вилучати елементи можна з обох кінців). Дек представити за допомогою вказівників.
Змоделюйте чергу, в якій реалізований такий механізм додавання нового елемента: якщо досягнутий кінець масиву, то всі елементи черги пересуваються на початок масиву.
Змоделюйте чергу за допомогою масиву INFO, де INFO[0] (а не окрема змiнна) використовуєтся для зберiгання початку черги, INFO[QueueSize+1] (а не окрема змiнна) використовуєтся для зберiгання кінця черги, а решта елементів масиву можуть містити елементи самої черги.
Змоделюйте структуру даних ДЕК (тобто додавати i вилучати елементи можна з обох кінців). Дек представити за допомогою масиву.
Змоделюйте чергу, в якій до опису черги додана ще одна змінна EMPTY, замість функції EMPTY. Чергу представити за допомогою вказівників.
Змоделюйте структуру даних ДЕК з обмеженим входом (тобто вилучати з дека можна з обох кінців, а додавати тільки з одного). Дек представити за допомогою масиву.
Змоделюйте чергу, в якій до опису черги додано ще дві змінні EMPTY i FULL, замість функцій EMPTY і FULL. Чергу представити за допомогою вказівників.
Змоделюйте структуру даних ДЕК з обмеженим виходом (тобто додавати в дек можна з обох кінців, а вилучати тільки з одного). Дек представити за допомогою масиву.
Змоделюйте чергу за допомогою двух стеків, представлених за допомогою вказівників. Додавання елементу до черги зводиться до додавання до одному зі стеков, а перевірка, чи черга порожня - до перевірки, чи порожні обидва стеки. При вилученні елемента з черги можливі два випадки. Якщо стек, де знаходиться початок черги, не порожній, то вилучається з нього елемент. Якщо він порожній, то попередньо в нього переписуються всі елементи другого стеку, змінюючи порядок (це відбувається саме при перекладанні зі стеку в стек) і далі задача зводиться до першого випадку.