Стеки и очереди (на базе массивов)
Два способа хранения элементов
- Стек и очередь оба хранят последовательность элементов, но они различаются тем, какой элемент выйдет следующим.
- Стек работает по принципу LIFO: Last In, First Out (последним пришёл — первым вышел) — как стопка тарелок.
- Очередь работает по принципу FIFO: First In, First Out (первым пришёл — первым вышел) — как очередь людей.
Стек работает по принципу LIFO
- push добавляет элемент сверху. pop удаляет и возвращает верхний элемент. peek смотрит на верхний элемент, не удаляя его.
- Последний элемент, который вы положили в стек, будет первым, который вы из него достанете.
- Мы храним элементы в массиве
dataи индексеtop, который считает, сколько их находится внутри.
Стек на основе массива
- При
topкак счетчик, верхний элемент находится по индексуdata[top - 1]. - push: запишите в
data[top], затем увеличьтеtop++. pop: уменьшитеtop--, затем вернитеdata[top]. - (Для этих задач массив достаточно велик; вам не нужно проверять условие «полный».)
Очередь работает по принципу FIFO
- enqueue добавляет элемент в конец. dequeue удаляет и возвращает элемент в начале.
- Первый элемент, который вы поместили в очередь, будет первым, который вы из неё достанете.
- Мы храним два индекса:
front(следующий для удаления) иback(следующая свободная ячейка).
Очередь на основе массива
- enqueue: запишите в
data[back], затем увеличьтеback++. dequeue: прочитайте изdata[front], затем увеличьтеfront++и верните значение. frontотслеживает positionbackпо мере поступления и удаления элементов.- (Для этих задач массив достаточно велик; вам не нужно делать цикл (wrap around) или проверять условие «пусто».)
Распространенные ошибки
- Стек работает по принципу last-in-first-out; очередь — first-in-first-out.
- Проверяйте, что структура не пуста, перед тем как вызывать pop или dequeue.
Теперь попробуйте сами
- Структуры
StackиQueueпредоставлены в шаблоне. Используйтеs->top,q->frontиq->back. - Не пишите
main— проверяющая система предоставит его.
Стеки и очереди
Стек работает по принципу LIFO; очередь — FIFO. Разберите последовательность операций.
Сложность 4/5 · 280 монет + небольшой бонус за первое завершение сегодня
Структура Stack (со data и счетчиком top) задана. Заполните void push(Stack *s, int v) и int pop(Stack *s), чтобы стек работал по принципу LIFO. Не пишите main.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 4/5 · 280 монет + небольшой бонус за первое завершение сегодня
Структура Stack задана. Завершите int peek(const Stack *s) так, чтобы она возвращала верхний элемент без его удаления. Предположите, что стек не пуст. Не пишите код для main.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 4/5 · 280 монет + небольшой бонус за первое завершение сегодня
Структура Queue (с полями data, front и back) задана. Завершите void enqueue(Queue *q, int v) и int dequeue(Queue *q) так, чтобы очередь работала по принципу FIFO. Не пишите код для main.
Нажмите Запустить, чтобы увидеть результат здесь.