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

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

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

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

Ответы

Ответ 1

Сделаем несколько предположений:

  • Что это домашнее задание
  • Этот параграф является частью задания

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

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

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

Ответ 2

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

Ответ 3

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

Ответ 4

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