Est-ce que trois piles peuvent être implémentées dans une seule baie, avec O (1) push / pop time?

Deux piles peuvent être mises en œuvre efficacement en utilisant un tableau de taille fixe: la pile # 1 commence à partir de l'extrémité gauche et croît vers la droite, et la pile # 2 commence à partir de l'extrémité droite et croît vers la gauche. Est-ce la même chose possible pour trois piles?

Plus précisément, est-il possible d'implémenter trois piles dans les conditions suivantes:

Vous disposez d'un tableau de taille fixe pouvant contenir N objets.
Tant que la somme des trois tailles de pile est <N, push () ne devrait pas échouer.
Les opérations push () et pop () devraient prendre O (1).
En plus du tableau, vous ne pouvez utiliser que O (1) d'espace supplémentaire.

Voici des exemples de solutions qui ne répondent pas à ces exigences:

Diviser le tableau en 3 parties fixes et utiliser chaque partie pour une pile (viole 2).
Similaire à ce qui précède mais avec des limites mobiles entre les piles (viole 3).
Implémentations simples basées sur des listes chaînées (viole 4).

J'accepte des algorithmes non triviaux ou des preuves d'impossibilité même s'ils ne remplissent pas toutes les conditions (1) - (4) exactement, par exemple, un algorithme où push / pop prend O (1) en temps amorti, ou où le la mémoire supplémentaire est inférieure à O (N), par exemple O (log N). Ou une preuve d'impossibilité qui montre que par exemple, l'accès à moins de 5 éléments du tableau par push / pop est impossible.

ds.data-structures lower-bounds user1020406
la source

Je ne sais pas si vous considérez cela comme une violation de l'exigence 4, mais si chaque "objet" dans votre tableau N objets peut inclure un champ supplémentaire tel qu'un index entier, alors vous pouvez implémenter les "listes liées" dans votre tableau . Vous pouvez maintenir l'index du haut de chacune des 3 piles en utilisant 3 variables externes, et chaque "objet" peut pointer vers l'élément précédent dans sa pile.

Avi Tal

Par «objets», je voulais dire des choses que push () accepte et pop () retourne. Du point de vue de l'implémentation de la pile, ce ne sont que des taches de données opaques (par exemple, un objet peut être un entier 32 bits). L'implémentation de la pile ne doit en aucun cas modifier ces objets.

user1020406

N

$N$

O (\sqrt{N})

$O(\sqrt{N})$

O (\sqrt{N})

$O(\sqrt N)$

Réponses:

$\Theta(n^\varepsilon)$ $\Theta(\sqrt{n})$ $\sqrt{n}$ $\sqrt{n}$

jbapple
la source

Soit N la longueur du tableau sous-jacent. Je peux imaginer les piles comme des listes liées de gros morceaux, de sorte que le nombre total de morceaux ne dépasse pas O (log2 (N)). Placez la troisième pile entre les deux premières, à l'indice de N / 2. Nous avons donc 3 zones occupées et 2 libres. Lorsqu'une pile ne peut pas accepter l'élément suivant, cela signifie qu'une zone libre est épuisée. Si l'autre aussi est épuisé, alors toute la mémoire est épuisée. Sinon, il existe une autre zone libre dont la taille ne dépasse pas N / 2. Continuez la pile débordée dans cette zone libre. de sorte que toute la configuration ressemble à la disposition initiale des piles. Puisque la mémoire libre ne représente plus que la moitié de la valeur initiale, il n'y aura plus que log2 (N) de telles opérations de liaison. Chaque opération de liaison nécessite une quantité de mémoire fixe pour enregistrer l'état précédent de la pile. Donc,

Alexei Kaigorodov
la source

Comment recyclez-vous la mémoire obtenue en faisant sauter des choses à partir d'un des gros morceaux?

Emil Jeřábek

Bonne question. La réponse rapide est que le morceau qui devient libre retourne sa mémoire dans la zone libre d'où il était précédemment prélevé. Mais que se passe-t-il si la zone libre s'est rétrécie depuis le temps d'allocation de mémoire pour ce bloc, et que le bloc n'est plus adjacent à lui? Cela conduit à la fragmentation de la mémoire libre, il peut y avoir plus de 2 zones libres, ce qui ruine toute ma construction.

Alexei Kaigorodov

Le saut est en effet le problème ici, mais la construction d'Alexei fournit une belle limite supérieure pour la version du problème que Dmitri a posée dans les commentaires: que se passe-t-il si nous exigeons que toutes les poussées se produisent avant toutes les pops? Je me demande si quelque chose de mieux que O (log N) est possible dans ce cas.

user1020406