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

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3773
3	Radewoosh	3646
4	ecnerwala	3624
5	jqdai0815	3620
5	Benq	3620
7	orzdevinwang	3612
8	Geothermal	3569
8	cnnfls_csy	3569
10	Um_nik	3396

№	Пользователь	Вклад
1	Um_nik	163
2	cry	161
3	maomao90	160
4	-is-this-fft-	159
5	awoo	158
6	atcoder_official	157
7	adamant	155
8	nor	154
9	maroonrk	152
10	Dominater069	148

Пускай у нас есть два стека, которые за О(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 лет назад, # |