Стопка реализации с помощью Двух Очередей

Вот мой ответ - где 'поп' неэффективен. Кажется, что все алгоритмы, которые приходят на ум сразу, имеют сложность 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

Самое легкое (и возможно только) способ сделать это путем продвижения новых элементов в пустую очередь и затем исключения из очереди другого и enqeuing в ранее пустую очередь. С этим путем последнее всегда впереди очереди. Это было бы версией B для версии A, Вы просто инвертируете процесс путем исключения элементов из очереди во вторую очередь за исключением последней.

Шаг 0:

"Stack"
+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+

Queue A                Queue B
+---+---+---+---+---+  +---+---+---+---+---+
|   |   |   |   |   |  |   |   |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+

Шаг 1:

"Stack"
+---+---+---+---+---+
| 1 |   |   |   |   |
+---+---+---+---+---+

Queue A                Queue B
+---+---+---+---+---+  +---+---+---+---+---+
| 1 |   |   |   |   |  |   |   |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+

Шаг 2:

"Stack"
+---+---+---+---+---+
| 2 | 1 |   |   |   |
+---+---+---+---+---+

Queue A                Queue B
+---+---+---+---+---+  +---+---+---+---+---+
|   |   |   |   |   |  | 2 | 1 |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+

Шаг 3:

"Stack"
+---+---+---+---+---+
| 3 | 2 | 1 |   |   |
+---+---+---+---+---+

Queue A                Queue B
+---+---+---+---+---+  +---+---+---+---+---+
| 3 | 2 | 1 |   |   |  |   |   |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+