Один стек, две очереди

фон

Несколько лет назад, когда я был студентом, нам дали домашнее задание по амортизированному анализу. Я не смог решить одну из проблем. Я спрашивал об этом в теории , но удовлетворительного результата не было. Я помню курс, на котором Т.А. настаивал на том, что он не смог доказать, и сказал, что забыл доказательство, и ... [вы знаете, что].

Сегодня я вспомнил проблему. Я все еще хотел знать, так что вот оно ...

Вопрос

Можно ли реализовать стек, используя две очереди , чтобы операции PUSH и POP выполнялись за амортизированное время O (1) ? Если да, подскажите как?

Примечание: Ситуация довольно легко , если мы хотим реализовать очередь с двумя стеками (с соответствующими операциями Епдиеей и DEQUEUE ). Пожалуйста, обратите внимание на разницу.

PS: вышеупомянутая проблема не сама домашняя работа. Домашняя работа не требует каких-либо нижних оценок; просто реализация и анализ времени выполнения.

У меня нет фактического ответа, но вот некоторые доказательства того, что проблема открыта:

• Это не упоминается в «Ming Li», «Luc Longpré» и «Paul MB Vitányi», «Сила очереди», Structures 1986, в которой рассматривается ряд других тесно связанных моделей

• Это не упоминается в Мартине Хюне, «О силе нескольких очередей», Теор. Комп. Sci. 1993, последующая статья.

• Это не упоминается в Holger Petersen, «Стеки против Deques», COCOON 2001.

• Бертон Розенберг, "Быстрое недетерминированное распознавание контекстно-свободных языков с использованием двух очередей", Информ. Proc. Lett. 1998, дает O (n log n) алгоритм с двумя очередями для распознавания любого КЛЛ с использованием двух очередей. Но недетерминированный пуш-автомат может распознавать КЛЛ за линейное время. Таким образом, если бы имитация стека с двумя очередями быстрее, чем O (log n) на операцию, Розенберг и его судьи должны были бы знать об этом.

Ответ ниже - «обман», поскольку он не использует пробел между операциями, но сами операции могут использовать больше, чем пробел. Смотрите в другом месте в этой теме ответ, у которого нет этой проблемы.$O(1)$

Хотя у меня нет ответа на ваш точный вопрос, я нашел алгоритм, который работает в время вместоO(n). Я считаю, что это жестко, хотя у меня нет доказательств. Во всяком случае, алгоритм показывает, что пытаться доказать нижнюю границуO(n)бесполезно, поэтому он может помочь в ответе на ваш вопрос.$O(\sqrt{n})$$O(n)$$O(n)$

Я представляю два алгоритма, первый из которых представляет собой простой алгоритм с временем выполнения для Pop, а второй - с O ( $O(n)$время работы для поп. Я описываю первый в основном из-за его простоты, так что второй легче понять.$O(\sqrt{n})$

Более подробно: первый не использует дополнительного пробела, имеет толчок в худшем случае (и амортизированный) и O ( n ) в худшем случае (и амортизированный), но поведение в худшем случае не всегда срабатывает. Поскольку он не использует никакого дополнительного пространства за пределами двух очередей, он немного «лучше», чем решение, предложенное Россом Снайдером.$O(1)$$O(n)$

Второе использует одно целочисленное поле (таким образом, дополнительный пробел), имеет O ( 1 ) худший случай (и амортизируется) Push и O ( $O(1)$$O(1)$амортизированный поп. Поэтому время его выполнения значительно лучше, чем у «простого» подхода, но все же использует дополнительное пространство.$O(\sqrt{n})$

Первый алгоритм

Мы имеем две очереди: очередь и очереди ы е гр ö н д . е я г с т будет наша «толчок очереди», а с е с о н д будет очередь уже «порядка стека».$first$$second$$first$$second$

• Нажатие делаются просто enqueueing параметра на .$first$
• Поппинг делается следующим образом. Если пусто, мы просто Dequeue с е с о н д и возвращает результат. В противном случае, мы обратные е я R сек т , Append всех ы е гр ö н д к е я R сек т и подкачки е я г с т и с е с о н д . Затем мы Dequeue с е с $first$$second$$first$$second$$first$$first$$second$ и вернуть результат удаления из очереди.$second$

C # код для первого алгоритма

Это может быть вполне читабельно, даже если вы никогда раньше не видели C #. Если вы не знаете, что такое дженерики, просто замените все экземпляры 'T' на 'string' в своем уме для набора строк.

public class Stack<T> {
    private Queue<T> first = new Queue<T>();
    private Queue<T> second = new Queue<T>();
    public void Push(T value) {
        first.Enqueue(value);
    }
    public T Pop() {
        if (first.Count == 0) {
            if (second.Count > 0)
                return second.Dequeue();
            else
                throw new InvalidOperationException("Empty stack.");
        } else {
            int nrOfItemsInFirst = first.Count;
            T[] reverser = new T[nrOfItemsInFirst];

            // Reverse first
            for (int i = 0; i < nrOfItemsInFirst; i++)
                reverser[i] = first.Dequeue();    
            for (int i = nrOfItemsInFirst - 1; i >= 0; i--)
                first.Enqueue(reverser[i]);

            // Append second to first
            while (second.Count > 0)
                first.Enqueue(second.Dequeue());

            // Swap first and second
            Queue<T> temp = first; first = second; second = temp;

            return second.Dequeue();
        }
    }
}

Анализ

Очевидно, Push работает за раз. Поп может касаться все внутри е я г с т и с е с о п d величины постоянного раза, поэтому мы имеем O ( п ) в худшем случае. Алгоритм демонстрирует это поведение (например), если один помещает n элементов в стек, а затем многократно выполняет одну операцию Push и одну операцию Pop подряд.$O(1)$$first$$second$$O(n)$$n$

Второй алгоритм

Мы имеем две очереди: очередь и очереди ы е гр ö н д . е я г с т будет наша «толчок очереди», а с е с о н д будет очередь уже «порядка стека».$first$$second$$first$$second$

Это адаптированная версия первого алгоритма, в котором мы не сразу «перетасовка» содержимое в ы е гр ö н д . Вместо этого, если е я г ы т содержит достаточно малое количество элементов по сравнению с ами е гр ö н д (а именно квадратный корень из числа элементов в ы е с ô п г ), мы только Реорганизовать е я г с т в порядке стека и не сливать его с$first$$second$$first$$second$$second$$first$ .$second$

• Нажатие все еще сделано, просто enqueueing параметра на .$first$
• Поппинг делается следующим образом. Если пусто, мы просто Dequeue с е с о н д и возвращает результат. В противном случае, мы реорганизовать содержимое е я ¨R сек т так , что они в порядке стека. Если | е я R сек т | < $first$$second$$first$мы просто DEQUEUEFяRсекти возвращает результат. В противном случае, мы AppendсесонднафяRсект, свопеяRытиыегрöнд, DEQUEUEыегрöнди возвращает результат.$|first| < \sqrt{|second|}$$first$$second$$first$$first$$second$$second$

C # код для первого алгоритма

Это может быть вполне читабельно, даже если вы никогда раньше не видели C #. Если вы не знаете, что такое дженерики, просто замените все экземпляры 'T' на 'string' в своем уме для набора строк.

public class Stack<T> {
    private Queue<T> first = new Queue<T>();
    private Queue<T> second = new Queue<T>();
    int unsortedPart = 0;
    public void Push(T value) {
        unsortedPart++;
        first.Enqueue(value);
    }
    public T Pop() {
        if (first.Count == 0) {
            if (second.Count > 0)
                return second.Dequeue();
            else
                throw new InvalidOperationException("Empty stack.");
        } else {
            int nrOfItemsInFirst = first.Count;
            T[] reverser = new T[nrOfItemsInFirst];

            for (int i = nrOfItemsInFirst - unsortedPart - 1; i >= 0; i--)
                reverser[i] = first.Dequeue();

            for (int i = nrOfItemsInFirst - unsortedPart; i < nrOfItemsInFirst; i++)
                reverser[i] = first.Dequeue();

            for (int i = nrOfItemsInFirst - 1; i >= 0; i--)
                first.Enqueue(reverser[i]);

            unsortedPart = 0;
            if (first.Count * first.Count < second.Count)
                return first.Dequeue();
            else {
                while (second.Count > 0)
                    first.Enqueue(second.Dequeue());

                Queue<T> temp = first; first = second; second = temp;

                return second.Dequeue();
            }
        }
    }
}

Анализ

Очевидно, Push работает за раз.$O(1)$

Поп работает в амортизированное время Есть два случая: если| еяRсект| <$O(\sqrt{n})$, затем мы перетасовываемfirstв порядок стеков вO(|first|)=O($|first| < \sqrt{|second|}$$first$время Если| еяRсект| ≥$O(|first|) = O(\sqrt{n})$тогда у нас должно было быть как минимум$|first| \geq \sqrt{|second|}$ призывает толкать. Следовательно, мы можем ударить только в этом случае каждый$\sqrt{n}$ звонки в Push и Pop. Фактическое время работы для этого случая -O(n), поэтому амортизированное время -O($\sqrt{n}$$O(n)$.$O(\frac{n}{\sqrt{n}}) = O(\sqrt{n})$

Конечная нота

Это можно исключить дополнительную переменную за счет создания Pop операции, при наличии Pop РеорганизоватьфяRсектпри каждом вызове вместо тогоНажмите делать всю работу.$O(\sqrt{n})$$first$

После некоторых комментариев к моему предыдущему ответу мне стало ясно, что я более или менее изменяю: я использовал дополнительное пространство ( дополнительное место во втором алгоритме) во время выполнения моего метода Pop.$O(\sqrt{n})$

Следующий алгоритм не использует никакого дополнительного пробела между методами и только дополнительного пробела во время выполнения Push и Pop. Push имеет O ( $O(1)$амортизированное время выполнения, и Pop имеетO(1)наихудшее (и амортизированное) время выполнения.$O(\sqrt{n})$$O(1)$

Примечание для модераторов: я не совсем уверен, является ли мое решение сделать это отдельным ответом правильным. Я думал, что не должен удалять свой первоначальный ответ, так как он все еще может иметь какое-то отношение к вопросу.

Алгоритм

Мы имеем две очереди: очередь и очереди ы е гр ö н д . е я г с т будет наш «кэш», а с е с о н д будет нашим основным «хранения». Обе очереди всегда будут в «порядке стека». е я г с т будет содержать в верхней части стека и элементы ы е гр ö н д будет содержать в нижней части стека элементов. Размер е я $first$$second$$first$$second$$first$$second$ всегда будет не более квадратного корня из s e c o n d .$first$$second$

• Нажмите делается путем «вставки» параметра в начале очереди следующим образом : мы епдиеие параметр к , а затем Dequeue и повторно епдиеие все другие элементы в е я R сек т . Таким образом, параметр заканчивается в начале е я R сек т .$first$$first$$first$
• Если становится больше , чем квадратный корень из ы е с о н д , мы епдиеие все элементы ы е с õ н д на е я R сек т один за другим , а затем подкачки е я г с т и с е с о н д . Таким образом, элементы е я R ы т ( в верхней части стека) в конечном итоге во главе ы $first$$second$$second$$first$$first$$second$$first$ .$second$
• Поп осуществляется освобождение пакета из очереди и возвращает результат , если е я R сек т не пусто, а в ином случае освобождения пакета из очереди ы е гр ö н г и возвратом результата.$first$$first$$second$

C # код для первого алгоритма

Этот код должен быть достаточно читабельным, даже если вы никогда раньше не видели C #. Если вы не знаете, что такое дженерики, просто замените все экземпляры 'T' на 'string' в своем уме для набора строк.

public class Stack<T> {
    private Queue<T> first = new Queue<T>();
    private Queue<T> second = new Queue<T>();
    public void Push(T value) {
        // I'll explain what's happening in these comments. Assume we pushed
        // integers onto the stack in increasing order: ie, we pushed 1 first,
        // then 2, then 3 and so on.

        // Suppose our queues look like this:
        // first: in 5 6 out
        // second: in 1 2 3 4 out
        // Note they are both in stack order and first contains the top of
        // the stack.

        // Suppose value == 7:
        first.Enqueue(value);
        // first: in 7 5 6 out
        // second: in 1 2 3 4 out

        // We restore the stack order in first:
        for (int i = 0; i < first.Count - 1; i++)
            first.Enqueue(first.Dequeue());
        // first.Enqueue(first.Dequeue()); is executed twice for this example, the 
        // following happens:
        // first: in 6 7 5 out
        // second: in 1 2 3 4 out
        // first: in 5 6 7 out
        // second: in 1 2 3 4 out

        // first exeeded its capacity, so we merge first and second.
        if (first.Count * first.Count > second.Count) {
            while (second.Count > 0)
                first.Enqueue(second.Dequeue());
            // first: in 4 5 6 7 out
            // second: in 1 2 3 out
            // first: in 3 4 5 6 7 out
            // second: in 1 2 out
            // first: in 2 3 4 5 6 7 out
            // second: in 1 out
            // first: in 1 2 3 4 5 6 7 out
            // second: in out

            Queue<T> temp = first; first = second; second = temp;
            // first: in out
            // second: in 1 2 3 4 5 6 7 out
        }
    }
    public T Pop() {
        if (first.Count == 0) {
            if (second.Count > 0)
                return second.Dequeue();
            else
                throw new InvalidOperationException("Empty stack.");
        } else
            return first.Dequeue();
    }
}

Анализ

Очевидно, что Pop работает за раз в худшем случае.$O(1)$

Push работает в амортизированное время Есть два случая: если| еяRсект| <$O(\sqrt{n})$затем Push принимаетO($|first| < \sqrt{|second|}$время Если| еяRсект| ≥$O(\sqrt{n})$Затем нажмите занимаетO(п)время, но после этой операциифяRсектбудет пустым. Это займетO($|first| \geq \sqrt{|second|}$$O(n)$$first$время, прежде чем мы получим этот случай снова, поэтому амортизированное время равноO($O(\sqrt{n})$время$O(\frac{n}{\sqrt{n}}) = O(\sqrt{n})$

Я утверждаю, что у нас есть амортизированная стоимость за операцию. Алгоритм Алекса дает верхнюю границу. Чтобы доказать нижнюю границу, я приведу наихудшую последовательность ходов PUSH и POP.$\Theta(\sqrt{N})$

$N$$\sqrt{N}$$\sqrt{N}$$\sqrt{N}$$\sqrt{N}$

$PUSH^N (PUSH^{\sqrt{N}} POP^{\sqrt{N}})^{\sqrt{N}}$

$N$$N/2$

$\sqrt{N}$

$N/2$$N/2$

$\sqrt{N}/2$$2\sqrt{N}$

$N/2$$2\sqrt{N}$$\sqrt{N}$$N\sqrt{N}/2$$3N$$\Omega(\sqrt{N})$

$O(\lg n)$$push$$pop$$pop$$O(\lg n)$$pop$ запрашивается и выходная очередь пуста, вы выполняете последовательность совершенных перемешиваний, чтобы обратить вспять входную очередь и сохранить ее в выходной очереди.

$O(1)$

Насколько я знаю, это новая идея ...

Не используя дополнительное пространство, возможно, используя приоритетную очередь и заставляя каждое новое нажатие придавать ей больший приоритет, чем предыдущее? Тем не менее, не будет O (1), хотя.

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

• $A$$B$ .
• Каждый раз, когда происходит операция push, переворачивайте бит и вставляйте элемент в очередь, бит теперь разграничивает. Извлеките все из другой очереди и поместите в текущую очередь.
• Операция pop снимает начало текущей очереди и не затрагивает бит внешнего состояния.

Конечно, мы можем добавить еще один бит внешнего состояния, которое сообщает нам, была ли последняя операция push или pop. Мы можем отложить перемещение всего из одной очереди в другую, пока не получим две операции push подряд. Это также делает операцию pop немного более сложной. Это дает нам O (1) амортизируемую сложность для операции pop. К сожалению, толчок остается линейным.

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

Если вы хотите амортизировать операции с постоянным временем, вам, вероятно, придется сделать что-то более умное.

Существует тривиальное решение, если ваша очередь допускает фронтальную загрузку, для которой требуется только одна очередь (или, более конкретно, deque.) Возможно, именно такой тип очереди имел в виду курс TA в исходном вопросе?

Без разрешения фронтальной загрузки вот еще одно решение:

Этот алгоритм требует две очереди и два указателя, мы будем называть их Q1, Q2, основной и дополнительный, соответственно. После инициализации Q1 и Q2 пусты, первичные точки указывают на Q1, а вторичные указывают на Q2.

Операция PUSH тривиальна, она состоит только из:

*primary.enqueue(value);

Операция POP немного более сложна; это требует спулинга всех, кроме последнего элемента первичной очереди, во вторичную очередь, замены указателей и возврата последнего оставшегося элемента из исходной очереди:

while(*primary.size() > 1)
{
    *secondary.enqueue(*primary.dequeue());
}

swap(primary, secondary);
return(*secondary.dequeue());

Проверка границ не выполняется, и это не O (1).

Когда я набираю это, я вижу, что это можно сделать с одной очередью, используя цикл for вместо цикла while, как это сделал Алекс. В любом случае, операция PUSH - это O (1), а операция POP - O (n).

Вот еще одно решение, использующее две очереди и один указатель, называемые Q1, Q2 и queue_p соответственно:

После инициализации Q1 и Q2 пусты и queue_p указывает на Q1.

Опять же, операция PUSH тривиальна, но требует еще одного дополнительного шага - наведения queue_p на другую очередь:

*queue_p.enqueue(value);
queue_p = (queue_p == &Q1) ? &Q2 : &Q1;

Операция POP аналогична предыдущей, но теперь есть n / 2 элементов, которые необходимо повернуть через очередь:

queue_p = (queue_p == &Q1) ? &Q2 : &Q1;
for(i=0, i<(*queue_p.size()-1, i++)
{
    *queue_p.enqueue(*queue_p.dequeue());
}
return(*queue_p.dequeue());

Операция PUSH по-прежнему O (1), но теперь операция POP - O (n / 2).

Лично для этой проблемы я предпочитаю идею реализации единой двусторонней очереди (deque) и при необходимости называть ее стеком.

$k$$Θ(n^{1/k})$

$k$
$n$
$O(1)$ или нет.

$i$$Θ(n^{i/k})$$Θ(n^{i/k})$$O(1)$$i+1$$O(n^{1/k})$$i-1$$Θ(n^{1/k})$

$m$$m$$Ω(mn^{1/k})$$o(n^{1/k})$$Ω(n^{1/k})$$o(n^{2/k})$$k$$o(n)$

$Θ(\log n)$

Стек может быть реализован с использованием двух очередей, используя в качестве второй очереди вторую очередь. Когда элементы помещаются в стек, они добавляются в конец очереди. Каждый раз, когда элемент извлекается, n - 1 элементов первой очереди должны быть перемещены во вторую, а оставшийся элемент возвращается. открытый класс QueueStack реализует IStack {private IQueue q1 = new Queue (); private IQueue q2 = новая очередь (); public void push (E e) {q1.enqueue (e) // O (1)} public E pop (E e) {while (1 <q1.size ()) // O (n) {q2.enqueue ( q1.dequeue ()); } sw apQueues (); return q2.dequeue (); } частный void swapQueues () {IQueue Q = q2; q2 = q1; q1 = Q; }}