Réalisez une file d'attente avec deux piles
Bonsoir.
Merci pour votre soutien. Il semble que mon article soit utile à tout le monde Je suis très content (≧ ▽ ≦)
Résumer sa propre compréhension organise aussi sa propre compréhension Deux oiseaux avec une pierre! (* ´ 艸 ｀)
Maintenant pour le titre, C'est un sujet intéressant, non? Faisons-le tout de suite. Quel genre de libération avez-vous imaginé?
Je pensais que cela pouvait être réalisé en préparant une pile dédiée pour Push et Pop respectivement. Par exemple, lorsque vous poussez, stockez-le dans la zone dédiée à Push. Dans le cas de Pop, les données sont transférées de Push uniquement vers Pop uniquement. C'est cool! ????? Pour le moment, créons une image étape par étape.
** 1. Pour Push **
Les données sont stockées dans la machine dédiée Push.
Les données ont été poussées dans l'ordre de A => B => C => D => E => F.
Il n'y a pas de problème.
Jetons un coup d'œil à la machine Pop-only.
L'adresse est attribuée de 0 à 5 au cas où, mais elle est vide pour le moment.
** 2. Pour Pop **
Extraire les données de la machine dédiée Push à la manière d'une pile,
Je vais pousser vers la machine dédiée à Pop.
Dans cet état, vu depuis la machine dédiée Pop, dans l'ordre F => E => D => C => B => A
Puisque vous allez pousser, n'est-ce pas comme ça?
Après cela, si vous sortez de la machine dédiée à Pop comme une pile,
Le mouvement est une pile, mais la sortie du système n'est-elle pas la même que la file d'attente?
D'une manière ou d'une autre, j'ai une image, alors écrivons-la. La base est basée sur l'article précédent. https://qiita.com/AKpirion/items/b1bad123aebe72f35a77
stack_x2_queue.py
def __init__(self,size):
self.INstr = [] #Push machine dédiée
self.OUTstr = [] #Machine dédiée à la pop
self.size = size
Cela n'a pas d'importance du tout, ensuite. Pour le moment, laissez la détente de côté Pousser les données de machine dédiée (ou machine dédiée Pop) Je voulais utiliser la description pour transférer vers la machine dédiée Pop déracinée (ou la machine dédiée Push).
stack_x2_queue.py
#Passer d'une machine Push-only à une machine Pop-only
def trans_IN2OUT(self):
#Déplacement déraciné de la longueur de données stockée existante
for _ in range(len(self.INstr)):
self.OUTstr.append(self.INstr.pop())
#Passer d'une machine Pop-only à une machine Push-only
def trans_OUT2IN(self):
#Déplacement déraciné de la longueur de données stockée existante
for _ in range(len(self.OUTstr)):
self.INstr.append(self.OUTstr.pop())
Pour le moment, vous pouvez écrire ce que vous voulez écrire, Que dois-je faire (* ´ω ｀) Il n'y a pas d'autre choix que de faire correspondre Tsuji 褄 (rires)
Commençons par Push. Quelle que soit la quantité de données dont dispose la machine dédiée Push, Si la longueur des données de la machine dédiée Pop est de 0, j'ai pensé que ce serait bien si je pouvais pousser vers la machine dédiée Push. Si la longueur des données de la machine dédiée Pop n'est pas 0, Utilisez def trans_OUT2IN (self) pour passer de la machine Pop-only à Push-only machine Déplacez tout. Après cela, je l'ai fait pour pouvoir pousser en utilisant la récurrence.
stack_x2_queue.py
def push(self,value):
#Vérifiez si la machine dédiée Push est pleine
if len(self.INstr) >= self.size:
#Traitement des exceptions si plein
raise Stack.full
#Jugez si la machine dédiée à Pop est vide
if len(self.OUTstr) == 0:
#S'il est vide, poussez vers une machine Push dédiée!
self.INstr.append(value)
else:
#S'il n'est pas vide, déplacez toutes les données de la machine dédiée Pop vers la machine dédiée Push
Stack.trans_OUT2IN(self)
#Si len utilise récursif(self.OUTstr) ==Remplacez les données par 0 et appuyez sur
Stack.push(self,value)
Ajoutez la fonction que vous souhaitez ajouter avec def, Remplissez les blancs en ajustant la description dans chaque définition. .. Est-ce que ça va? (ﾟ Ω ﾟ) Pokhan (ﾟ Д ﾟ y) y! ?? Je suis sûr qu'il y a une manière logique de gérer ça, je veux étudier
Eh bien, tu veux aller ensuite, pop.
C'est fondamentalement l'opposé de push. Si la longueur des données stockées dans la machine dédiée Push est 0, Pop à partir d'une machine Pop dédiée. Dans les cas autres que ceux ci-dessus, toutes les données de la machine dédiée Push Passez à la machine dédiée à Pop. Je pense que cela ressemblera à ce qui suit.
stack_x2_queue.py
def pop(self):
#Si la machine dédiée Push est vide, sortez de la machine dédiée Pop
if len(self.INstr) == 0:
print(f"pop data is {self.OUTstr.pop()}")
else:
#Déplacer toutes les données de la machine dédiée Push vers la machine dédiée Pop
Stack.trans_IN2OUT(self)
#Si len utilise récursif(self.INstr) ==Rappelez la condition de 0
Stack.pop(self)
Le tout ressemble à ceci.
stack_x2_queue.py
class Stack:
class full(Exception):
pass
def __init__(self,size):
self.INstr = []
self.OUTstr = []
self.size = size
def push(self,value):
if len(self.INstr) >= self.size:
raise Stack.full
if len(self.OUTstr) == 0:
self.INstr.append(value)
else:
Stack.trans_OUT2IN(self)
Stack.push(self,value)
def pop(self):
if len(self.INstr) == 0:
print(f"pop data is {self.OUTstr.pop()}")
else:
Stack.trans_IN2OUT(self)
Stack.pop(self)
def view(self):
print(self.INstr)
print(self.OUTstr)
def trans_IN2OUT(self):
for _ in range(len(self.INstr)):
self.OUTstr.append(self.INstr.pop())
def trans_OUT2IN(self):
for _ in range(len(self.OUTstr)):
self.INstr.append(self.OUTstr.pop())
x = int(input("stack size is "))
test = Stack(x)
while True:
num = int(input("1.push 2.pop: "))
if num == 1:
x = int(input("push data is "))
try:
test.push(x)
test.view()
except:
print("Full!")
elif num == 2:
try:
test.pop()
test.view()
except:
print("Empty!")
else:
break
Le résultat de l'exécution est également affiché.
stack size is 4
1.push 2.pop: 1
push data is 1 #Pousser 1
[1] #Push machine dédiée
[] #Machine dédiée à la pop
1.push 2.pop: 1
push data is 2 #Pousser 2
[1, 2] #Push machine dédiée
[] #Machine dédiée à la pop
1.push 2.pop: 1
push data is 3 #Pousser 3
[1, 2, 3] #Push machine dédiée
[] #Machine dédiée à la pop
1.push 2.pop: 1
push data is 4 #Pousser 4
[1, 2, 3, 4] #Push machine dédiée
[] #Machine dédiée à la pop
1.push 2.pop: 2
pop data is 1 #Pop 1 depuis une machine Pop dédiée
[] #Push machine dédiée
[4, 3, 2] #Machine dédiée à la pop
1.push 2.pop: 2
pop data is 2 #Pop 2 depuis une machine Pop dédiée
[] #Push machine dédiée
[4, 3] #Machine dédiée à la pop
1.push 2.pop: 1
push data is 2 #Appuyez sur Renvoyer les données à la machine dédiée et appuyez sur 2
[3, 4, 2] #Push machine dédiée
[] #Machine dédiée à la pop
1.push 2.pop: 1
push data is 1
[3, 4, 2, 1]
[]
1.push 2.pop: 2
pop data is 3
[]
[1, 2, 4]
1.push 2.pop: 2
pop data is 4
[]
[1, 2]
1.push 2.pop: 2
pop data is 2
[]
[1]
1.push 2.pop: 2
pop data is 1
[]
[]
J'ai arrêté de compléter en chemin, Après avoir envoyé toutes les données à chaque machine dédiée à chaque fois Push and Pop Il semble difficile de maintenir la polyvalence sans passer aux actions Push et Pop (= ω =) y─┛ ○ o.
De plus, si une erreur se produit en plein ou en vide dans le mouvement défini par la machine Push-only ou Pop-only, le traitement des exceptions sera lancé, il n'est donc pas nécessaire de changer quoi que ce soit.
Merci pour votre travail acharné ^^) _ Dan ~~
Recommended Posts