Veri Yapıları #06 | Yığın: Son Giren İlk Çıkar — Parantez, Sonek İfade ve Çağrı Yığını

Eğitmen: Dr. Süleyman Burak ÇELİK

Veri Yapıları dersinin altıncı videosu. Köşeli parantez, normal parantez, önce köşeli kapanış, sonra normal: sayılar tutuyor ama sıra yanlış. Bu hatayı tek bir yığınla bulan bir program yazıyoruz. Yığın, ekleme ve çıkarmanın yalnızca tepeden yapıldığı bir listedir: son giren ilk çıkar (LIFO). Ekleme (push), çıkarma (pop) ve tepeye bakma işlemlerini yigin.h arayüzüne yazıyor, yığını önce bir diziyle (tepe, son elemanın indisi; boşken −1), sonra bağlı listeyle gerçekleştiriyoruz; aynı deneme programı iki gerçekleştirmede de satır satır aynı çıktıyı veriyor. Ardından yığının üç büyük işini görüyoruz. Parantez dengesi: açılış gelince ekle, kapanış gelince çıkar ve eşini denetle; dört girdinin sonucunu gerçekten çalıştırıyoruz. Sonek ifade: 2 3 4 * + ifadesi 14, 2 3 + 4 * ifadesi 20 verir; işlem önceliğine ve paranteze gerek kalmaz. Çağrı yığını: kendini çağıran bir fonksiyonun yerel değişken adresleri her çağrıda 64 bayt aşağı iniyor; adresler çalıştırmadan çalıştırmaya değişse de adım değişmiyor. Son olarak bütün yığın işlemlerinin sabit zamanlı olduğunu ve iki gerçekleştirmenin farklarını karşılaştırıyoruz. Ekrandaki her çıktı, kodun gerçekten derlenip çalıştırılmasından geliyor. Bu derste: 1. Yığın soyut veri tipi: ekleme (push), çıkarma (pop), tepe; LIFO 2. Dizi ve bağlı liste ile gerçekleştirme, aynı yigin.h 3. Parantez dengesi: tek geçişte yığınla denetim 4. Sonek (postfix) ifade hesaplama 5. Çağrı yığını: yerel değişken adresleri ve yığın taşması Bölümler: 0:00 Yığın: yalnızca tepeden 0:22 Sayılar tutuyor, sıra yanlış 0:44 Ekleme, çıkarma, tepe: LIFO 1:09 Diziyle gerçekleştirme 1:39 Bağlı listeyle gerçekleştirme 2:06 Parantez dengesi 2:42 Sonek ifade hesaplama 3:23 Çağrı yığını 4:05 Maliyet ve seçim 4:31 Bugünün dört kuralı 4:54 Sonraki ders: kuyruk Kaynak kitap: Mark Allen Weiss — Data Structures and Algorithm Analysis in C++, 4. baskı (2014), §3.6 (yığın modeli, gerçekleştirmeleri ve uygulamaları: sembol dengesi, sonek ifadeler, fonksiyon çağrıları). Konu sırası ve kavramlar kaynak kitaptan izlenir; programlar ve örnekler C ile özgün yazıldı, anlatım ve ekranlar özgündür. Hedef kitle: veri yapılarına başlayan mühendislik ve bilgisayar/yazılım öğrencileri. Ön koşul: temel C ve bu serinin 2. ve 3. dersleri (soyut veri tipi, bağlı liste).

Bu videoyu izlemek için Premium üyelik gerekir.