Задача "Дек"

@Кирион · Регистрация: 03.07.2011

Студворк — интернет-сервис помощи студентам

Уважаемые форумчане, добрый день!

Помогите пож-та с решением задачи, которая встречается у ресурсов Яндекса.
Я написал логику, но при проверке задачи есть комментарии, которые я не могу понять как разобраться.

Условия задачи под спойлером:

Кликните здесь для просмотра всего текста

Гоша реализовал структуру данных Дек, максимальный размер которого определяется заданным числом. Методы push_back(x), push_front(x), pop_back(), pop_front() работали корректно. Но, если в деке было много элементов, программа работала очень долго. Дело в том, что не все операции выполнялись за O(1). Помогите Гоше! Напишите эффективную реализацию.

Внимание: при реализации используйте кольцевой буфер.

Формат ввода
В первой строке записано количество команд n — целое число, не превосходящее 100000. Во второй строке записано число m — максимальный размер дека. Он не превосходит 50000. В следующих n строках записана одна из команд:

push_back(value) – добавить элемент в конец дека. Если в деке уже находится максимальное число элементов, вывести «error».
push_front(value) – добавить элемент в начало дека. Если в деке уже находится максимальное число элементов, вывести «error».
pop_front() – вывести первый элемент дека и удалить его. Если дек был пуст, то вывести «error».
pop_back() – вывести последний элемент дека и удалить его. Если дек был пуст, то вывести «error».
Value — целое число, по модулю не превосходящее 1000.

Формат вывода
Выведите результат выполнения каждой команды на отдельной строке. Для успешных запросов push_back(x) и push_front(x) ничего выводить не надо.

Пример

Ввод

4

push_front 861

push_front -819

pop_back

Вывод

861

-819

Сам код:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Dek:
    def __init__(self, max_size: int):
        self._elements = [None] * max_size
        self._max_size = max_size
        self._head = 0
        self._tail = 0
        self._size = 0
 
    def is_empty(self):
        return self._size == 0
 
    def push_back(self, value: int):
        if self._size != self._max_size:
            self._elements[self._tail] = value
            self._tail = (self._tail + 1) % self._max_size
            self._size += 1
        else:
            raise OverflowError
 
    def push_front(self, value: int):
        if self._size != self._max_size:
            self._elements[self._head - 1] = value
            self._head = (self._head - 1) % self._max_size
            self._size += 1
        else:
            raise OverflowError
 
    def pop_back(self):
        if self.is_empty():
            raise IndexError
        x = self._elements[self._tail - 1]
        self._elements[self._tail - 1] = None
        self._tail = (self._tail - 1) % self._max_size
        self._size -= 1
        return x
 
    def pop_front(self):
        if self.is_empty():
            raise IndexError
        x = self._elements[self._head]
        self._elements[self._head] = None
        self._head = (self._head + 1) % self._max_size
        self._size -= 1
        return x
 
 
def main() -> None:
    n: int = int(input())
    max_size: int = int(input())
    queue: Dek = Dek(max_size)
    for i in range(n):
        values: list = input().split()
        try:
            getattr(queue, values.pop(0))(*values)
        except Exception:
            print('error')
 
 
if __name__ == '__main__':
    main()

И вот какие замечания я получил:

Код:

Python
1
2
    def is_empty(self):
        return self._size == 0

Комментарий:
такие методы служебные, лучше инкапсулировать
Вопрос:
Что значит инкапсулировать? Как это можно реализовать?

Код:

Python
1
2
    def push_back(self, value: int):
        if self._size != self._max_size:

Комментарий:
для этого условия можно тоже отдельный метод сделать на подобие is_empty
Вопрос:
Как это реализовать в данном коде?

Код:

Python
1
2
3
4
5
6
commands = {
        'push_front': queue.push_front,
        'push_back': queue.push_back,
        'pop_front': queue.pop_front,
        'pop_back': queue.pop_back,
    }

Комментарий:
команды называются также как и методы класса, поэтому можно без словаря использовать getattr функцию
Вопрос:
То есть нет необходимости объявлять словарь? В таком случае куда воткнуть эту функцию и как это будет выглядеть?

Код:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
    for i in range(count_command):
        command = input()
        operation, *value = command.split()
        if value:
            try:
                result = commands[operation](int(*value))
                if result is not None:
                    print(result)
            except OverflowError:
                print('error')
        else:
            try:
                result = commands[operation]()
                print(result)
            except IndexError:
                print('error')

Комментарий:
много дублирующего кода, print('error'), print(result), два блока try except. Подумай, как можно от него избавиться.
Вопрос:
Не могу придумать как можно оптимизировать данный кусок кода....

Заранее всем спасибо за ответы и помощь, возможно проблемы супер простые для опытных пользователей, но для новичка это настоящая боль...

@Catstail · 07.04.2023, 19:40

Сообщение от Кирион

Внимание: при реализации используйте кольцевой буфер.

- я не обнаружил кольцевой буфер в приведенной реализации. Если используется список, то добавление в конец будет выполняться за O(n)...

@Red white socks · 08.04.2023, 11:03

Сообщение от Кирион

Что значит инкапсулировать?

В данном контексте означает спрятать от пользователя. То есть сделать private или protected. Вдогонку вопрос - поля класса у вас protected, not private. Есть тому причина, почему именно так?

Сообщение от Кирион

для этого условия можно тоже отдельный метод сделать на подобие is_empty

Python
1
def _is_full(self):

Сообщение от Кирион

команды называются также как и методы класса, поэтому можно без словаря использовать getattr функцию

Мог бы написать, нетрудно, но вам пора самому научиться работать с доками. Ищем getattr в документации и смотрим, что да как.

Сообщение от Кирион

Не могу придумать как можно оптимизировать данный кусок кода....

Ну подумайте, зачем тебе нужен if?

@eaa · 12.04.2023, 06:32

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from collections import deque
 
q = deque()
n = int(input())
m = int(input())
for _ in range(n):
    cmd, *a, = input().split()
    match cmd:
        case 'push_back':
            if len(q) == 4:
                print('error')
            else:
                q.append(int(a[0]))
        case 'push_front':
            if len(q) == 4:
                print('error')
            else:
                q.appendleft(int(a[0]))
        case 'pop_front':
            if not q:
                print('error')
            else:
                print(q.popleft())
        case 'pop_back':
            if not q:
                print('error')
            else:
                print(q.pop())
        case _:
            print('command error')

Не по теме:

чтобы было...

Новые блоги и статьи Все статьи Все блоги /
Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .