Вот мой ответ - где «поп» неэффективно.
Кажется, что все алгоритмы, которые приходят сразу в голову, имеют сложность N, где N - размер списка: выбираете ли вы работать над «поп» или «нажимать»
Алгоритм, в котором списки возвращаются назад, а четвертый может быть лучше,
так как вычисление размера не требуется, хотя вам все равно нужно выполнить цикл и сравнить с пустым.
Вы можете доказать, что этот алгоритм не может быть написан быстрее, чем N, отметив, что информация о последнем элементе в очереди доступна только через знание размера очереди, и что вы должны уничтожить данные, чтобы добраться до этого элемента, следовательно 2-я очередь.
Единственный способ сделать это быстрее - это вообще не использовать очереди.
from data_structures import queue
class stack(object):
def __init__(self):
q1= queue
q2= queue #only contains one item at most. a temp var. (bad?)
def push(self, item):
q1.enque(item) #just stick it in the first queue.
#Pop is inefficient
def pop(self):
#'spin' the queues until q1 is ready to pop the right value.
for N 0 to self.size-1
q2.enqueue(q1.dequeue)
q1.enqueue(q2.dequeue)
return q1.dequeue()
@property
def size(self):
return q1.size + q2.size
@property
def isempty(self):
if self.size > 0:
return True
else
return False