Comment mettre en œuvre trois piles à l'aide d'un tableau unique

Vous pouvez mettre en œuvre trois piles avec un liste:

• Vous avez besoin d'un pointeur pointant vers le prochain élément libre. Plus de trois pointeurs renvoie le dernier élément de chaque pile (ou la valeur null si la pile est vide).
• Lorsqu'une pile devient un autre élément ajouté, c'est le premier élément libre et le jeu de la libre pointeur vers le prochain élément (ou une erreur de dépassement de capacité sera élevé). Son propre pointeur a pour pointer vers le nouvel élément, de là vers l'élément suivant dans la pile.
• Lorsqu'une pile devient un élément retiré la main de nouveau dans la liste d'éléments. Le pointeur de la pile sera redirigé vers l'élément suivant dans la pile.

Un liste liée peut être mise en œuvre dans un tableau.

Comment (espace) efficace?

Il n'est pas un problème pour construire une liste liée par l'utilisation de deux cellules d'un tableau pour chaque élément de la liste (valeur + pointeur). En fonction de la spécification que vous pourriez même obtenir de pointeur et de la valeur à un élément de tableau (par exemple, le tableau est long, la valeur et le pointeur ne sont int).

Comparez cela à la solution de kgiannakakis ... où vous perdre jusqu'à 50% (seulement dans le pire des cas). Mais je pense que ma solution est un peu plus propre (et peut-être plus académique, qui devrait être pas un handicap pour une question d'entrevue ^^).

OriginalL'auteur tanascius

Nous pouvons utiliser à long tableau de bits représentant de, qui mettent à la i-ième de la matrice de cellule appartient.
On peut prendre des valeurs par modulo 3 (00 - vide, 01 - A, 10 - B, 11 - C). Il faudrait N/2 bits ou N/4 octets de la mémoire supplémentaire pour N tableau de taille.

Par exemple pour une résolution 1024 long int éléments (4096 octets) il faudra que 256 octets, ou de 6%.

Ce tableau de bits de la carte peut être placé dans le même tableau, au début ou à la fin, juste de la réduction de la taille du tableau donné par la constante de 6%!

OriginalL'auteur Vitamon

C'est intéressant à énigme, et je n'ai pas de vraie réponse, mais penser légèrement à l'extérieur de la boîte...

cela pourrait dépendre de ce que chaque élément de la pile se compose de. Si c'est trois piles de vrai/faux drapeaux, alors vous pouvez utiliser les trois premiers bits de l'entier éléments. C'est à dire. le bit 0 est la valeur de la première pile, le bit 1 est la valeur de la deuxième pile, le bit 2 est la valeur de la troisième pile. Ensuite, chaque pile peut se développer de façon indépendante jusqu'à ce que l'ensemble du tableau est complet pour la pile. C'est encore mieux que les autres piles peuvent continuer à croître, même si le premier de la pile est pleine.

Je sais que c'est de la triche un peu et de ne pas vraiment répondre à la question, mais il fonctionne pour un cas très spécifique et pas d'entrées dans la pile sont gaspillés. Je suis de regarder avec intérêt de voir si quelqu'un peut venir avec une réponse adéquate qui fonctionne pour plus d'éléments génériques.

OriginalL'auteur giles123

En supposant que toutes les positions de tableau doit être utilisé pour stocker des valeurs - je suppose que cela dépend de votre définition de l'efficacité.

Si vous ne les deux pile de solution, lieu de la troisième pile quelque part au milieu, et deux de ses bas et le haut, puis la plupart des opérations continuera à être efficace, à une peine d'une coûteuse opération de Déplacement (de la troisième pile vers où l'espace libre reste, se déplaçant vers le point à mi-chemin de l'espace libre) lorsqu'une collision se produit.

Ça va certainement être rapide au code et à comprendre. Quels sont nos objectifs d'efficacité?

OriginalL'auteur Damien_The_Unbeliever

1. Faire une table de hachage avec des clés à la fin et de début de postes par exemple < "B1" , 0 >, <"E1" , n/3 >

2. pour chaque Push(valeur) ajouter une condition pour vérifier si la position de la Bx est antérieur Ex ou il ya quelques autres "Par" entre les deux. -- appelons cela la condition (2)

3. avec la condition ci-dessus à l'esprit,
   si ci-dessus (2) est vraie //si B1 et E1 sont dans l'ordre
   { if ( S1.Push()), alors E1 ++ ;
   else //condition de débordement ,
   { commencer à pousser à la fin de l'E2 ou E3 (selon ce qui a un espace) et mise à jour de E1 à E2-- ou E3-- ; }
   }

   si au-dessus de (2) est fausse
   { if ( S1.Push()), alors E1 -- ;
   else //condition de débordement ,
   { commencer à pousser à la fin de l'E2 ou E3 (selon ce qui a un espace) et mise à jour de E1 à E2-- ou E3-- ; }
   }

OriginalL'auteur AAW

première pile croît à 3n,
deuxième pile augmente à 3n+1,
troisième pousse à 3n+2

pour n={0...N}

OriginalL'auteur Gunjan

Dans cette approche, toute pile peut croître aussi longtemps qu'il y a une place libre dans le tableau.
Nous séquentiellement allouer de l'espace pour les piles et de nous lier de nouveaux blocs pour le bloc précédent. Cela signifie que tout élément nouveau dans une pile conserve un pointeur vers le haut précédents élément de la pile.

int stackSize = 300;
int indexUsed = 0;
int[] stackPointer = { -1,-1,-1};
StackNode[] buffer = new StackNode[stackSize * 3];

void push(int stackNum, int value) {
    int lastIndex = stackPointer[stackNum];
    stackPointer[stackNum] = indexUsed;
    indexUsed++;
    buffer[stackPointer[stackNum]]=new StackNode(lastIndex,value);
}

int pop(int stackNum) {
    int value = buffer[stackPointer[stackNum]].value;
    int lastIndex = stackPointer[stackNum];
    stackPointer[stackNum] = buffer[stackPointer[stackNum]].previous;
    buffer[lastIndex] = null;
    indexUsed--;
    return value;
}

int peek(int stack) { return buffer[stackPointer[stack]].value; }

boolean isEmpty(int stackNum) { return stackPointer[stackNum] == -1; }

class StackNode {
    public int previous;
    public int value;

    public StackNode(int p, int v){
        value = v;
        previous = p;
    }
}

OriginalL'auteur maxpayne

Une autre solution en PYTHON, s'il vous plaît laissez-moi savoir si cela fonctionne comme ce que vous en pensez.

    class Stack(object):

    def __init__(self):
        self.stack = list()

        self.first_length = 0
        self.second_length = 0
        self.third_length = 0

        self.first_pointer = 0
        self.second_pointer = 1

    def push(self, stack_num, item):

        if stack_num == 1:
            self.first_pointer += 1
            self.second_pointer += 1
            self.first_length += 1
            self.stack.insert(0, item)

        elif stack_num == 2:
            self.second_length += 1
            self.second_pointer += 1
            self.stack.insert(self.first_pointer, item)
        elif stack_num == 3:
            self.third_length += 1
            self.stack.insert(self.second_pointer - 1, item)
        else:
            raise Exception('Push failed, stack number %d is not allowd' % stack_num)

    def pop(self, stack_num):
        if stack_num == 1:
            if self.first_length == 0:
                raise Exception('No more element in first stack')
            self.first_pointer -= 1
            self.first_length -= 1
            self.second_pointer -= 1
            return self.stack.pop(0)
        elif stack_num == 2:
            if self.second_length == 0:
                raise Exception('No more element in second stack')
            self.second_length -= 1
            self.second_pointer -= 1
            return self.stack.pop(self.first_pointer)
        elif stack_num == 3:
            if self.third_length == 0:
                raise Exception('No more element in third stack')
            self.third_length -= 1
            return self.stack.pop(self.second_pointer - 1)

    def peek(self, stack_num):
        if stack_num == 1:
            return self.stack[0]
        elif stack_num == 2:
            return self.stack[self.first_pointer]
        elif stack_num == 3:
            return self.stack[self.second_pointer]
        else:
            raise Exception('Peek failed, stack number %d is not allowd' % stack_num)

    def size(self):
        return len(self.items)

s = Stack()

# push item into stack 1
s.push(1, '1st_stack_1')
s.push(1, '2nd_stack_1')
s.push(1, '3rd_stack_1')
#
## push item into stack 2
s.push(2, 'first_stack_2')
s.push(2, 'second_stack_2')
s.push(2, 'third_stack_2')
#
## push item into stack 3
s.push(3, 'FIRST_stack_3')
s.push(3, 'SECOND_stack_3')
s.push(3, 'THIRD_stack_3')
#
print 'Before pop out: '
for i, elm in enumerate(s.stack):
    print '\t\t%d)' % i, elm

#
s.pop(1)
s.pop(1)
#s.pop(1)
s.pop(2)
s.pop(2)
#s.pop(2)
#s.pop(3)
s.pop(3)
s.pop(3)
#s.pop(3)
#
print 'After pop out: '
#
for i, elm in enumerate(s.stack):
    print '\t\t%d)' % i, elm

OriginalL'auteur James Sapam