Stack-Implementierung der Trollface-Weg

Question

In meinem Software-Engineering-Kurs, stieß ich auf die folgende Eigenschaft eines Stapels, kondensiert von mir: Was Sie schieben, ist was Sie Pop. Die voll axiomatische Version I Uled here.
Als ein geborener Troll habe ich sofort den Troll Stack erfunden. Wenn bereits mehr als 1 Element vorhanden ist, führt Push zu einer zufälligen Permutation dieser Elemente. Prompt kam ich mit den Dozenten in Streit, ob diese Nonsense-Implementierung tatsächlich gegen die Axiome verstößt. Ich sagte nein, das oberste Element bleibt wo es ist. Sie sagten ja, irgendwie können Sie das Push-Pop-Axiom rekursiv anwenden, um "tiefer" zu werden. Was ich nicht sehe. Wer hat Recht?

Answer 1

Das verletzte Axiom ist pop(push(s,x)) = s. Nehmen Sie einen Stapel s mit n > 1 eindeutigen Einträgen. Wenn Sie push so implementieren, dass push(s,x) ist s'x mit s' eine zufällige Permutation von s ist, dann wird, da pop eine Funktion ist, haben Sie ein Problem: Wie Reverse Sie random_permutation() so dass pop(push(s,x)) = s? Das Urbild von s' könnte eine der n! > 1 Permutationen von s gewesen sein, und egal, welchem ​​Sie zuordnen, gibt es n! - 1 > 0 andere ursprüngliche Permutationen s'' für die pop(push(s'',x)) != s''.

Answer 2

In Fällen wie diesem, die für jeden sehr leicht zu sehen sind, aber nicht für Sie (daher Ihre Verwendung des "Troll" -Wortes), hilft es immer, das "Programm" einfach auf einem Blatt Papier auszuführen.

Notieren Sie, was passiert, wenn Sie ein paar Mal drücken und pop, und Sie werden sehen.

Sie sollten auch sehen können, wie diese Axiome dem tatsächlichen Verhalten Ihres Stacks sehr ähnlich sind; Sie sind nicht nur zum Spaß da, sondern sie geben (in mehreren Bedeutungen des Wortes) die Datenstruktur mit ihren Methoden an. Man könnte sie sogar als ein "formales System" betrachten, das die Vor- und Nachteile von Stacks beschreibt.

Beachten Sie, dass es immer noch gut für Sie ist, skeptisch zu sein; Dies führt zu a) besseren Einblick und b) Erkennung von Fehlern Ihrer Vorgesetzten. In diesem Fall haben sie Recht, aber es gibt Fälle, in denen Sie viel Zeit sparen können (zB bei der Suche nach der Lösung für das "MU" Rätsel in "Gödel, Escher, Bach", was eine ausgezeichnete Lektüre für Sie wäre, Ich denke).