İçeriğe geç

İki stack'li kuyruk işlemleri

Kolay#two-stacks#amortized~15 dk

Görev tanımı

Problem

Yalnız tepeye push, tepeden pop ve tepeyi okumayı kullanarak iki stack'ten ilk giren ilk çıkar bir kuyruk kur. Bir işlem listesini işle: ["push", x] x'i ekler, ["pop"] en eski değeri çıkarır ve bildirir, ["peek"] de onu çıkarmadan bildirir. Bildirilen değerleri sırasıyla döndür; pop ya da peek kuyruğu boş bulursa None bildir. Her işlem amortize (amortized) O(1) zamana mal olmalı.

Örnekler

Input:  ops = [["push", 1], ["push", 2], ["peek"], ["pop"],
               ["push", 3], ["pop"], ["pop"]]
Output: [1, 1, 2, 3]
Neden: değerler geldikleri sırayla çıkıyor
Input:  ops = [["push", 7], ["pop"], ["push", 8], ["push", 9], ["peek"]]
Output: [7, 8]
Neden: 7 çıktıktan sonra kalan en eski değer 8
Input:  ops = [["pop"], ["push", 4], ["peek"]]
Output: [None, 4]
Neden: edge case: boş bir kuyruğu pop etmek None bildirir

İpuçları

0 / 3

Hedef zaman
O(m)
Hedef alan
O(m)

Kısıtlar

  • O(1) amortized time per operation
  • stacks allow only push, pop and top

Kodda değil de fikirde mi takıldın? İki stack'ten kuyruk bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır
Özel test case