Três pilhas podem ser implementadas em uma matriz, com O (1) push / pop time?

Duas pilhas podem ser implementadas com eficiência usando uma matriz de tamanho fixo: a pilha nº 1 começa na extremidade esquerda e cresce para a direita e a pilha nº 2 começa na extremidade direita e cresce para a esquerda. O mesmo é possível para três pilhas?

Mais especificamente, é possível implementar três pilhas, dadas as seguintes condições:

Você tem uma matriz de tamanho fixo que pode conter N objetos.
Contanto que a soma dos três tamanhos de pilha seja <N, push () não deve falhar.
As operações push () e pop () devem levar tempo O (1).
Além da matriz, você pode usar apenas O (1) espaço adicional.

Aqui estão exemplos de soluções que não atendem a esses requisitos:

Dividir a matriz em 3 partes fixas e usar cada parte de uma pilha (viola 2).
Semelhante ao anterior, mas com limites móveis entre as pilhas (viola 3).
Implementações simples baseadas em lista vinculada (viola 4).

Aceitarei algoritmos não triviais ou provas de impossibilidade, mesmo que eles não atendam a todas as condições (1) - (4) exatamente, por exemplo, um algoritmo em que push / pop leve O (1) tempo amortizado ou onde o a memória adicional é menor que O (N), por exemplo, O (log N). Ou uma prova de impossibilidade que mostre que, por exemplo, acessar menos de 5 elementos da matriz por push / pop é impossível.

ds.data-structures lower-bounds user1020406
fonte

Não sei se você considera isso uma violação do requisito 4, mas se cada "objeto" em sua matriz de objetos N puder incluir um campo adicional, como um índice inteiro, poderá implementar as "listas vinculadas" em sua matriz . Você pode manter o índice da parte superior de cada uma das 3 pilhas usando 3 variáveis externas, e cada "objeto" pode apontar para o elemento anterior na sua pilha.

Avi Tal

Por "objetos", eu quis dizer coisas que push () aceitam e pop () retornam. Do ponto de vista da implementação da pilha, eles são apenas blobs opacos de dados (por exemplo, um objeto pode ser um número inteiro de 32 bits). A implementação da pilha não deve modificar esses objetos de forma alguma.

User1020406

Considere primeiro fazer uma sequência de operações push e, em seguida, executar apenas operações pop. Existe algo conhecido sobre esta versão do problema?

N

$N$

Dmitri Urbanowicz 13/05/19

Seria de espaço adicional satisfazê-lo?

O (\sqrt{N})

$O(\sqrt{N})$

Dmitri Urbanowicz 13/05/19

Re: "N empurra e depois N aparece" versão: Eu não sei, mas mesmo identificando isso como um subproblema interessante é útil porque mesmo lá não está claro se uma solução O (1) é possível. Veja a resposta de @ Alexei e seu tópico de comentários para o limite superior. Quanto a uma solução , sim, eu aceito. Sou novo em postar perguntas sobre o stackexchange, por isso não sei como lidar com casos em que soluções cada vez melhores podem ser fornecidas ao longo do tempo. Uma abordagem que eu vi foi esperar um dia ou mais antes de aceitar uma resposta, caso algo melhor fosse publicado, então farei isso.

O (\sqrt{N})

$O(\sqrt N)$

User1020406

Respostas:

Fredman e Goldsmith mostraram em "Três pilhas" (Journal of Algorithms, 1994) que bits de espaço desperdiçado são alcançáveis. Também é o mínimo necessário para matrizes de tamanho de pelo menos 16 quattuordecillion yottabytes. Descrevi um algoritmo simples que desperdiçou palavras de espaço na minha resposta StackOverflow a esta pergunta . Como @ dmitri-urbanowicz mencionado nos comentários, isso basicamente trata apenas a matriz como blocos de tamanho , onde cada bloco é usado para exatamente uma pilha e contém um único ponteiro para o próximo bloco nessa pilha. $\Theta(n^\varepsilon)$ $\Theta(\sqrt{n})$ $\sqrt{n}$ $\sqrt{n}$

jbapple
fonte

Seja N o comprimento da matriz subjacente. Posso imaginar pilhas como listas vinculadas de grandes pedaços, de modo que o número geral de pedaços não seja maior que O (log2 (N)). Coloque a terceira pilha entre as duas primeiras, no índice de N / 2. Portanto, temos 3 áreas ocupadas e 2 gratuitas. Quando uma pilha não pode aceitar o próximo elemento, isso significa que uma área livre está esgotada. Se o outro também estiver exausto, toda a memória estará exausta. Caso contrário, há outra área livre com tamanho não superior a N / 2. Continue a pilha excedida para essa área livre. para que toda a configuração se assemelhe ao layout inicial das pilhas. Como a memória livre agora não passa da metade da inicial, não haverá mais que o log2 (N) dessas operações de vinculação. Cada operação de vinculação requer uma quantidade fixa de memória para salvar o estado anterior da pilha. Assim,

Alexei Kaigorodov
fonte

Como você recicla a memória obtida retirando coisas de um dos grandes pedaços?

Emil Jeřábek 11/05/19

Boa pergunta. A resposta rápida é aquela parte que fica livre retorna sua memória para a área livre de onde foi tirada anteriormente. Mas e se a área livre encolheu desde o tempo de alocação de memória para esse pedaço, e o pedaço agora não está adjacente a ele? Isso leva à fragmentação da memória livre, pode haver mais de 2 áreas livres, o que arruina toda a minha construção.

Alexei Kaigorodov

Popping é realmente o problema aqui, mas a construção de Alexei fornece um bom limite superior para a versão do problema que Dmitri perguntou nos comentários: e se exigirmos que todos os pushs aconteçam antes de todos os pops? Gostaria de saber se algo melhor que O (log N) é possível neste caso.

User1020406 14/05/19