Как проверить правильный порядок элементов и удаление старых элементов в стеке с ограниченной емкостью?

Что проверяют

Правильно ли вы понимаете саму структуру: при переполнении такой стек выбрасывает самый старый элемент, то есть дно, а не вершину. И умеете ли вы превратить это требование в тесты с пограничными случаями. Следом просят реализацию и её сложность.

Как отвечать

Сначала зафиксируйте контракт: push кладёт на вершину, pop снимает с вершины (LIFO), при заполненном стеке новый push удаляет элемент со дна. Размер никогда не превышает capacity.

Готовая структура есть в стандартной библиотеке: collections.deque(maxlen=n). append и pop работают с правым концом за O(1), а при заполнении append сам отбрасывает элемент слева. Самописная версия на list с pop(0) тоже верна, но это O(n) на каждую вставку.

Тесты на pytest:

• вытеснение: ёмкость 3, кладём 1, 2, 3, 4, ожидаем list(stack) == [2, 3, 4];
• порядок снятия: после этого pop() возвращает 4, 3, 2, затем пустой стек бросает IndexError (или возвращает None, если так записано в контракте);
• границы: ёмкость 1, ёмкость 0, отрицательная ёмкость (deque тут бросает ValueError), pop из пустого стека, peek без изменения содержимого;
• инвариант: после любой последовательности операций len(stack) <= capacity.

Хороший плюс: тест на свойствах через Hypothesis. Генерируете случайную последовательность push и pop, параллельно ведёте эталонную модель на обычном списке, где после вставки остаются последние capacity элементов, и сравниваете состояния после каждого шага.

Где спотыкаются

При переполнении вызывают self.pop() и удаляют вершину. Из [1, 2, 3] после push(4) получается [1, 2, 4]: старые данные остаются, свежие теряются, а тест на одну длину этого не видит.

Проверку «порядка» делают через sorted(). Порядок в стеке это порядок вставки, а не сортировка значений, и стек [5, 3, 1] вполне корректен.

Пишут тесты, которые печатают состояние через print, вместо assert на точные значения. Такой тест не падает никогда.