Очередь с использованием двух стеков

Question

Я реализовал это как массив с двумя стеками, смежными друг с другом, но их вершины на обоих концах. То есть, если top (stack1) находится в начале ключей, top (stack2) находится в конце ключей. Нижний (Stack1) и Нижний (Stack2) должны быть смежными, но в любом месте между верхом (Stack1) и верхним (Stack2). Чтобы удалить, я выскакиваю сверху (Stack1), а для вставки я нажимаю сверху (stack2). Может ли кто-нибудь сказать мне, если это правильно сделать так?

Когда я читал CLRS, я решил путь таким образом, и у меня не было возможности узнать, был ли он в порядке или нет. Но это было задано на сегодняшнем экзамене, и все позже обсуждали способ, указанный официально (здесь и везде в сети), так что, похоже, я единственный, кто сделал это таким образом. Я действительно хочу знать, если это неправильно или правильно? Пожалуйста, помогите

Answer 1

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

Ваша идея использовать один массив для реализации двух стеков хороша.Но вставки и удаления должны происходить в обоих стеках.

Например,Допустим, у вас есть эта настройка

2 3 4 5 6

top (stack1) равен 2
bottom (stack1) равен 4
top (stack2) равен 6
bottom (stack2) равен 5

после выхода из stack1 3 раза вы достигли дна своего стека, т.е. 4 и больше не могли бы ничего вытолкнуть, даже если есть еще дваэлементы в вашей QUEUE реализации.Итак, необходимо внести некоторые исправления в вашу реализацию.

Итак, если бы я реализовал два стека, эмулирующих QUEUE, я бы так и сделал.

Stack1 : 2 3 4 5 6, который по сути является массивом
2 - это нижняя часть стека, а 6 - верхняя часть стека.

Stack2 : empty

Вставить элемент в очередь:
Это очень просто.Просто добавьте в конец массива, например, stack1
stack1 : 2 3 4 5 6 7
Теперь 7 является вершиной стека.

Удалить элемент изОчередь:
1. Вставьте все элементы в stack1 и вставьте их в stack2.Таким образом, ваш массив будет инвертирован
stack1 : empty
stack2 : 7 6 5 4 3 2.Теперь 2 находится на вершине стека.
2. Теперь ваша вершина (stack2) будет указывать на 2.Просто вставьте это.7 6 5 4 3
3. Теперь для оставшихся элементов в stack2 извлеките их из stack2 и вставьте их в stack1.
stack2 : empty
stack1 :3 4 5 6 7

PS: Приведенный выше алгоритм предполагает, что вы знаете, как управлять памятью для массивов по мере ее сжатия или расширения.

Answer 2

Вот пример в Python, использующий встроенный массив / список для двух стеков.

class Queue2Stacks(object):

    def __init__(self):
        self.in_stack = []
        self.out_stack = []

    def enqueue(self, element):
        self.in_stack.append(element)

    def dequeue(self):
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())
        return self.out_stack.pop()

Answer 3

Для тех, кто ищет решение, пример такой:

Допустим, у нас есть два stacks S1 и S2.
A queue имеет два следующих поведения:

1. Постановка в очередь: вставка элемента в очередь. Для этого просто нажмите на S1.
2. Dequeue: выталкивает все элементы из S1 один за другим, одновременно толкая их в S2. Теперь выскочите из S2. Выскочивший элемент - это желаемый результат Dequeue.

Читателям предлагается найти более оптимизированные решения для этого и опубликовать их здесь, если это возможно:)

Answer 4

Я думаю, что вы можете реализовать очередь, используя два смежных стека, как вы описали.Проблема в том, что вы не можете эффективно реализовать эти два соседних стека с помощью массива.Я имею в виду, что ваша очередь выглядит нормально, но когда вы пытаетесь использовать базовые стеки, вы сталкиваетесь с проблемой, как вставить новый элемент в начало массива (т.е. push to stack1)Вам нужно переместить (скопировать) все элементы в вашем массиве, чтобы поместить элемент в stack1.И это плохо дизайн.