Задача "Дек"

@Кирион · Регистрация: 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')

Не по теме:

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

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .

Опции темы