Yığın Kullanma

Veriyi tabak yığını gibi son giren ilk çıkar saklayın.

Yaklaşık 4 dk okuma
  • Yığın Kullanma'yı kendi kelimelerinizle tanımlayın ve açıklayın
  • Yığın gibi temel terimleri doğru kullanın
  • Öğrendiklerinizi yeni örnek ve sorulara uygulayın
  • Bu konuda öğrencilerin yaptığı yaygın hatalardan kaçının

Bir liste her zaman doğru araç değildir: geri al düğmeleri, yazıcı kuyrukları, dosya sistemleri ve navigasyonların her biri veriyi düzenlemenin kendi yoluna ihtiyaç duyar. Veri yapıları bu özel kaplardır ve iyi seçim, çalışan kod ile zarif kodu ayıran şeydir. Bu bölüm, her A-level öğrencisinin bilmesi gereken dört yapıyı kurar.

Bu ders, Yığın Kullanma'ya odaklanır: veriyi tabak yığını gibi son giren ilk çıkar saklayın.

Tanım: Yığın Kullanma

Veriyi tabak yığını gibi son giren ilk çıkar saklayın.

Temel fikirler

LIFO ile FIFO her şeyi değiştirir

Yığınlar sırayı tersine çevirir — geri al, geri düğmeleri ve dengeli parantez kontrolü için mükemmel. Kuyruklar sırayı korur — yazıcı kuyruğu ve istekleri adilce işleme için mükemmel. İşlemler de farklıdır: yığınlar üstte iter ve çıkarır; kuyruklar arkaya ekler, önden çıkarır. Yanlışını seçmek sessizce yanlış cevaplar üretir.

Ağaçlar aramayı yarıya indirmeye dönüştürür

İkili arama ağacı, küçük değerleri solda, büyük değerleri sağda tutar; böylece her karşılaştırma ağacın yarısını atar — ikili arama ile aynı fikir, yapının içine gömülü. Dolaşmalar düğümleri farklı sıralarla ziyaret eder: ikili arama ağacında iç-sıra dolaşma değerleri sıralı verir. Ekleme sırası ağacı şekillendirir; kötü sıralı bir ekleme onu yavaş bir bağlı listeye dönüştürür.

Terim — yığın: Son giren ilk çıkar yapısı: öğeler üst denen aynı uçtan eklenir ve çıkarılır — yaylı tabak dağıtıcısı gibi.

Yığın İzleme

Boş bir yığınla başlayın. 4 it, 7 it, çıkar, 2 it, çıkar. Her çıkarma ne döndürür ve geriye ne kalır?

4 it: yığın [4] olur, 4 üstte. 7 it: yığın [4, 7] olur, 7 üstte. Çıkarma üstten çıkarır, bu yüzden ilk çıkarma 7 döndürür. Yığın [4] olur. 2 it: yığın [4, 2] olur, 2 üstte. Tekrar çıkarma üsttekini çıkarır, bu yüzden ikinci çıkarma 2 döndürür. Yığın [4] olur.

Cevap: Çıkarmalar sırayla 7 sonra 2 döndürür ve yığında yalnızca [4] kalır — son giren ilk çıkar.

Yaygın hatalar
  • Kuyruk gerekirken yığın kullanma Düzeltme: 'önce gelen önce mi hizmet almalı?' diye sorun — cevap evetse kuyruk gerekir; yığın, en son geleni önce hizmete alırdı.
  • Boş bir yapıdan çıkarma ya da kuyruktan çıkarma Düzeltme: önce yapının boş olmadığını her zaman kontrol edin — hiçlikten çıkarmak taşma hatasına neden olur.

Alıştırma

Bir web tarayıcısının geri düğmesini hangi yapı modeller: yığın mı kuyruk mu? Neden?
Ziyaret edilen son sayfa, geri döndüğünüz ilk sayfadır.

Yığın — her yeni sayfa itilir ve Geri, en son sayfayı çıkarır; bu, son giren ilk çıkar.

Doğru mu yanlış mı: bir yığın, bir ifadedeki parantezlerin dengeli olup olmadığını kontrol etmek için kullanılabilir.
Önce neyin kapanması gerektiğini düşünün.

Doğru — her açan parantezi itin ve her kapatan parantezde çıkarın; en son açılan ilk kapanmalıdır, bu tam olarak LIFO'dur.

Bir kuyruk, A önde olacak şekilde [A, B, C] tutuyor. Bir kuyruktan çıkarma ve bir D kuyruğa eklemeden sonra kuyruk ne olur?
Kuyruktan çıkarma önden çıkarır; kuyruğa ekleme arkaya ekler.

[B, C, D] — A önden ayrılır, D arkaya katılır.

5, 3, 8, 1'i bu sırayla boş bir ikili arama ağacına ekleyin. Kökün sol çocuğu nedir?
Küçük değerler her düğümün soluna gider.

3 — kök 5'in soluna gider, sonra 1 de 3'ün soluna gider.

Kısa kontrol

Yığın Kullanma — kısa kontrol

Aşağıdakilerden hangisi "yığın"ı en iyi tanımlar?

Son giren ilk çıkar yapısı: öğeler üst denen aynı uçtan eklenir ve çıkarılır — yaylı tabak dağıtıcısı gibi.

Bir yol ağı graf olarak modellenmişse düğümler, kenarlar ve ağırlıklar neyi temsil eder?

Düğümler kavşaklardır (ya da şehirler), kenarlar aralarındaki yollardır, ağırlıklar ise mesafeler ya da yolculuk süreleridir.

İkili arama ağacının iç-sıra dolaşması ne üretir?

Değerleri artan sıralı şekilde.
Önemli çıkarımlar
  • Yığın Kullanma: veriyi tabak yığını gibi son giren ilk çıkar saklayın.
  • LIFO ile FIFO her şeyi değiştirir: Yığınlar sırayı tersine çevirir — geri al, geri düğmeleri ve dengeli parantez kontrolü için mükemmel.
  • Düğüm: Ağaç ya da graftaki tek bir öğe; veri ve diğer düğümlere bağlantılar tutar.
  • Dikkat edin: kuyruk gerekirken yığın kullanma
11. Sınıf bölümlerine dönİlgili kaynaklar →