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

Тема: Stack & Queue

Стек (stack)

Выполните код для стека.

Стек может быть основан на динамическом массиве (std::vector, или своя реализация) или связном списке. Сделайте оба варианта.

Если никогда не делали сами динамический массив, рекомендую сделать и это. Пример есть здесь.

Стек отличается следующими операциями:

• bool isEmpty(const Stack* stack) проверяет если стек пустой;
• void push(Stack* stack, int value) добавляет поверх элементов стека;
• int* getLastElement(Stack* stack) (можете назвать как вам логичнее) дает адрес (или ссылку) элемента сверху, не удаляя его;
• void pop(Stack* stack) удаяет элемент сверху (последний добавленный).

Пример есть здесь. Пример немного отличается от требований, поскольку в примере стек фиксированного максимального размера.

Очередь (queue)

Выполните код для очереди.

Бесконечную очередь можно сделать довольно просто используя связной список, удаляя сначала, и добавляя в конец. Очередь фиксированного размера можно сделать через ring buffer, через динамический ring buffer ее можно тоже сделать бесконечной (тут можно придумать креативные подходы по расширению буфера)

Сделайте как минимум один из подходов (проще всего через список).

Очередь отличается следующими операциями:

• bool isEmpty(const Queue* queue) проверяет если очередь пустая;
• void enqueue(Queue* queue, int value) добавляет элемент в конец очереди;
• int* front(Queue* queue) дает адрес (или ссылку) первого элемента из очереди;
• void dequeue(Queue* queue) удаляет элемент с начала очереди.

Пример есть здесь. Но это по факту связный список с дополнительными функциями / другими именами функций, в своей базовой имплементации.