Разработать стек, который также может выгружать в O (1) амортизированное время?

Question

У меня есть абстрактный тип данных, который можно просматривать в виде списка, хранящегося слева направо, со следующими возможными операциями: Нажмите: добавить новый элемент в левый конец списка Pop: удалить элемент в левом конце списка Вытащить: удалить элемент в правом конце списка

Реализуйте это, используя три стека и постоянную дополнительную память, чтобы амортизированное время для любой операции push, pop или pull было постоянным. Стеки имеют базовые операции: isEmpty, Push и Pop.

Амортизированное время означает: «Если я потрачу это количество времени, я могу потратить еще один его блок и сохранить его в банке времени, чтобы использовать его позже» Как и для каждой операции push, тратить три блока постоянного времени, поэтому для каждого элемента push у вас есть 2 дополнительных блока постоянного времени.

Answer 1

Делая несколько предположений:

1. Что это домашнее задание
2. , что этот параграф является частью задания

Реализуйте это, используя три стека и постоянная дополнительная память, так что амортизированное время для любого толчка, поп, или операция вытягивания постоянна. стеки имеют базовые операции, isEmpty, Нажмите и Pop.

Тогда мой первый совет - игнорировать людей, разговаривающих с вами о связанных списках. Правда, именно так любой разумный человек мог бы реализовать это без требования трех стеков , но ключевой фактор в домашней работе - это не то, как разумный человек, а то, как этого хочет ваш инструктор.

Мой второй совет - взять несколько блоков, колоду карт или набор чашек из пенопласта и назначить три стопки (например, с подставками или чем-то еще). Начните играть с тем, что происходит, когда вы переносите содержимое одного стека в другой, и это должно дать вам представление.

Answer 2

Вы можете сделать что-то, что использует только 3 стека. Подумайте Ханойская башня .

Answer 3

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

Answer 4

Начните с реализации очереди в терминах двух стеков (довольно стандартная проблема) и обобщите.