Ich war durch einige Interview Fragen stöbern und stolperte darüber. Es brachte mich dazu, meine Haare auseinanderzureißen.Stack mit einer Warteschlange
Kann jemand einen Stapel mithilfe der Warteschlange implementieren ?.
drücken: das Element in den hinteren Bereich der Warteschlange einfügen.
pop: Entfernen Sie ein Element von der Vorderseite, fügen Sie es sofort auf der Rückseite ein, wiederholen Sie N-1 mal, wobei N die Größe der Warteschlange ist, entfernen Sie dann das letzte Element und geben Sie es zurück.
Ich aktualisiert die Seite direkt bevor ich anfing zu beantworten, nur um diese Antwort bereits veröffentlicht zu finden = (Gute Arbeit! =) – BeemerGuy
Version A:
Push:
enqueue in queue1
pop:
während Größe queue1 ist größer als 1 ist, aus der Warteschlange entfernt Rohr Artikel von queue1 in Queue2 dequeue und Rückkehr das letzte Element von queue1, dann die Namen von queue1 und queue2 wechseln
Version B:
Push:
enqueue in Queue2 enqueue alle Artikel queue1 in Queue2, dann wechseln die Namen von queue1 und Queue2
pop:
deqeue von queue1
Konzept des Verwendens Eine Warteschlange zum Implementieren des Stapels benötigt O (2n) oder (maschinenunabhängige) O (n) -Komplexität. Aber wenn Sie für ein großes Array arbeiten, ist die doppelte Größe möglicherweise nicht verfügbar, auch die Zeitkomplexität ist O (n^2) oder genau O (n * (n + 1)/2), falls Sie nur eine verwenden möchten Warteschlange.
Hier ist eine Frage zur Verwendung von zwei Warteschlangen: http://stackoverflow.com/questions/688276/implement-stack-using-two-queues – eldarerathis