Очередь из двух стеков

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

№	Пользователь	Вклад
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

Пускай у нас есть два стека, которые за О(1) могут корректным образом выполнять операции добавки в конец, взятия значения последнего элемента, удаления последнего элемента, нахождения количества элементов в стеке.

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

Спасибо за внимание. Задача из уст Ставровского Андрея Борисовича.

Мне в голову пришло только решение, которое выполняет добавку за константу и извлечение за линию.

stack<int> top, tail; int q_size() { return top.size() + tail.size(); } int q_push(int x) { tail.push(x); } void q_transform() { if (top.empty()) { while (!tail.empty()) { top.push(tail.top()); tail.pop(); } } } void q_pop() { q_transform(); top.pop(); } int q_front() { q_transform(); return top.top(); }

Комментарии (8)

Написать комментарий?

andreyv

11 лет назад, # |