Очередь на двух стеках

@Teikook · Регистрация: 13.10.2019

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

Очередь на двух стеках
Входные данные: Последовательность запросов popFront(), pushBack(), max().
Выходные данные: Для каждого запроса max() выводить максимальный элемент, а для каждого запроса popFront() выводить элемент из начала очереди.
Подробное условие задачи.
Заведём два стека: s1 и s2; разумеется, имеются в виду стеки с поддержкой минимума (максимума). Добавлять новые элементы будем всегда в стек s1, а извлекать элементы - только из стека s2. При этом, если при попытке извлечения элемента из стека s2 он оказался пустым, просто перенесём все элементы из стека s1 в стек s2 (при этом элементы в стеке s2 получатся уже в обратном порядке, что нам и нужно для извлечения элементов; стек s1 же станет пустым). Наконец, нахождение минимума в очереди будет фактически заключаться в нахождении минимума из минимума в стеке s1 и минимума в стеке s2.
Тем самым, мы выполняем все операции по-прежнему за O (1) (по той простой причине, что каждый элемент в худшем случае 1 раз добавляется в стек s1, 1 раз переносится в стек s2 и 1 раз извлекается из стека s2).

Примеры.
Входные данные
3
pushBack 1
pushBack 7
popFront
Выходные данные
1

Входные данные
5
pushBack 4
pushBack 35
max
popFront
max
Выходные данные
35
35
35

Добавлено через 31 минуту

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Queue:
 
    def _init_(self):
        self.s1 = []
        self.s2 = []
 
    def push(self, elem):
        self.s1.push(elem)
 
    def pop(self):
        if not self.s2:
            while self.s1:
                self.s2.push(self.s1.pop())
        return self.s2.pop()
 
    def get_min(self):
        return max(self.s1.get_max(), self.s2.get_max())

что делать дальше?

@Fudthhh · 11.03.2020, 08:14

Teikook, ты хоть пробовал запускать этот код?

@TomsonAnastasia · 11.03.2020, 10:01

Сообщение от Teikook

def get_min(self):
return max(self.s1.get_max(), self.s2.get_max())

Вот здесь, ничего не понятно.
Можете расписать конкретнее с переносами из одного стека в другой и команда у Вас называется max, а метод get_min, как-то не вяжется.

Конструктор класса записан не верно, init должен быть с двумя нижними подчеркиваниями в начале и в конце.

Python
1
2
3
def __init__(self):
        self.s1 = []
        self.s2 = []

Что-бы добавить в список нужно не self.s1.push(elem), a

Python
1
self.s1.append(elem)

Ну и везде добавление в список нужно делать через append.

На вопрос что делать дальше, я так понимаю это, как вызвать эти методы у объекта класса?
Если да, то вот так.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
count_command = int(input())
queue = Queue()
line = []
for count in range(count_command):
    command = str(input()).split(' ')
    if command[0] == 'max':
        line.append(queue.get_max())
    elif len(command) == 2 and command[0] == 'pushBack':
        queue.push(command[1])
    elif command[0] == 'popFront':
        line.append(queue.pop())
    else:
        print('Такой команды нет')
print(i for i in line)

Команда max не работает, если распишете более понятно, что от нее требуется - помогу.

Добавлено через 12 минут

Сообщение от TomsonAnastasia

print(i for i in line)

Не так записала.
Нужно

Python
1
[print(i) for i in line]

Новые блоги и статьи Все статьи Все блоги /
Жизнь в неопределённости kumehtar 23.03.2026 Жизнь — это постоянное существование в неопределённости. Например, даже если у тебя есть список дел, невозможно дойти до точки, где всё окончательно завершено и больше ничего не осталось. В принципе,. . .	Модель здравоСохранения: работники работают быстрее после её введения. anaschu 23.03.2026 geJalZw1fLo Корпорация до введения программа здравоохранения имела много невыполненных работниками заданий, после введения программы количество заданий выросло. Но на выплатах по больничным это. . .	1С: Контроль уникальности заводского номера Maks 23.03.2026 Алгоритм контроля уникальности заводского (или серийного) номера на примере документа выдачи шин для спецтехники с табличной частью. Данные берутся из регистра сведений, по которому настроено. . .	Хочу заставить корпорации вкладываться в здоровье сотрудников: делаю мат модель здравосохранения anaschu 22.03.2026 e7EYtONaj8Y Z4Tv2zpXVVo https:/ / github. com/ shumilovas/ med2. git
1С: Программный отбор элементов справочника по группе Maks 22.03.2026 Установка программного отбора элементов справочника "Номенклатура" из модуля формы документа. В качестве фильтра для отбора справочника служит группа номенклатуры. Отбор по наименованию группы. . .	Как я обхитрил таблицу Word Alexander-7 21.03.2026 Когда мигает курсор у внешнего края таблицы, и нам надо перейти на новую строку, а при нажатии Enter создается новый ряд таблицы с ячейками, то мы вместо нервных нажатий Энтеров мы пишем любые буквы. . .	Krabik - рыболовный бот для WoW 3.3.5a AmbA 21.03.2026 без регистрации и смс. Это не торговля, приложение не содержит рекламы. Выполняет свою непосредственную задачу - автоматизацию рыбалки в WoW - и ничего более. Однако если админы будут против -. . .	1С: Программный отбор элементов справочника по значению перечисления Maks 21.03.2026 Установка программного отбора элементов справочника "Сотрудники" из модуля формы документа. В качестве фильтра для отбора служит значение перечислений. / / Событие "НачалоВыбора" реквизита на форме. . .

@Fudthhh Модератор 2695 / 1601 / 513 Регистрация: 21.02.2017 Сообщений: 4,210 Записей в блоге: 1
	11.03.2020, 08:14
	Teikook, ты хоть пробовал запускать этот код? 0