Algoritmalar bir kitap (Robert Sedgewick tarafındanAlgorithms, 4th Edition ve Kevin Wayne) bu soru ile karşılaştım.

Üç deste kuyruk. Her sıra operasyon yığın işlemleri (en kötü durum) sabit bir sayı alır böylece üç yığınları ile bir sıra uygulayın. Uyarı : zorluk derecesi yüksek.

2 yığınları ile bir sıra yapmayı biliyorum ama 3 yığınları ile çözüm bulamıyorum. Herhangi bir fikir ?

(oh, bu bir ödev değil :) )

ÖZET

• O(1) algoritması 6 yığınlar için bilinir
• O(1) algoritması 3 yığınları için bilinen, ama bir çözüm teşkil etmez, bu yüzden uygulamada ekstra iç veri yapılarına sahip olan bir kurs tembel değerlendirme kullanarak
• Sedgewick yakın insanlar özgün soru tüm kısıtlamaları içinde 3-yığın bir çözüm farkında olmadığını doğruladı

AYRINTILAR

İki uygulamaları bu linki arkasında vardır: http://www.eecs.usma.edu/webs/people/okasaki/jfp95/index.html

Bunlardan biri O(1) üç deste AMA uygulamada ekstra ara veri yapıları (kilitler) yaratan tembel yürütme kullanır.

Bunlardan başka O(1) olur ama ALTI yığınları kullanır. Ancak, tembel yürütme olmadan çalışır.

GÜNCELLEME: Okasaki kağıt işte: http://www.eecs.usma.edu/webs/people/okasaki/jfp95.ps ve gerçekten tembel değerlendirme(1) O sürüm için. sadece 2 yığınlar kullanan görünüyor Sorun gerçekten tembel değerlendirme dayalı olmasıdır. Soru 3-yığın tembel değerlendirme olmadan algoritma bir tercüme edilebilir.

GÜNCELLEME: Başka bir algoritma ile ilgili yazıda anlatılan "Yığınlara karşı güvertelerde ağır" tarafından Holger Petersen, 7'de yayınlanan Bilişim ve Kombinasyon için Yıllık Konferans. Google Kitaplardan makale bulabilirsiniz. Sayfa 225-226 kontrol edin. Ancak algoritma aslında gerçek zamanlı değil, simülasyon, üç yığınları üzerinde çift uçlu bir kuyruğu var doğrusal-zaman simülasyon.

gusbro: @Leonel birkaç gün önce dedi ki, eğer bir çözüm bilse Prof. Sedgewick ile kontrol etmek adil olur diye düşündüm ya da bir yanlışlık varmış Gibi". Onun için yazdım. Ben sizinle paylaşmak istiyorum bu yüzden bir yanıt da değil, Princeton'da bir meslektaşım kendisinden ama) aldı.O temelde hiçbir algoritmaları üç yığınları kullanarak biliyordu VE diğer kısıtlamaları (tembel değerlendirme kullanmamak gibi) empoze söyledi. Bir algoritma, bildiğimiz kadarıyla 6 yığınları kullanarak cevapları buraya bakarak tanıyor. Sorun hala çözülmemiş bir algoritma (veya bulunamıyor ispat) bulmak için sanırım bu kadar."