Veri Yapıları ve Programlama

Ali ERBEY

9.06.2022 1
Diziler(Array)

• Dizi (array), aynı -pteki verilerin tek bir değişken al4nda tutulmasını sağlayan veri yapısıdır.

• Sabit bir değere sahip olan dizinin uzunluğu, dizi oluşturulurken belirlenir.

• Bir dizide bulunan verilerin her biri, o dizinin bir elemanı olarak adlandırılır. Dizinin elemanlarına erişim indis (index) adı
verilen sayısal değerler aracılığıyla sağlanır.

• İndislerin numaralandırılması 0 ile başlar, dizinin uzunluğunun 1 eksiğine kadar ardışık olarak artarak devam eder.

9.06.2022 2
Diziler

9.06.2022 3
Stack (Yığın)

• Yığın, programlamada yararlı bir veri yapısıdır.

• Tıpkı üst üste yerleş-rilmiş tabak yığını gibidir.

• Son Giren İlk Çıkar (Last in First Out) (LIFO)

9.06.2022 4
LIFO Prensibi

Programlama açısından, yığının en üstüne bir öğe koymaya push , bir öğeyi kaldırmaya ise pop denir .

Push : Bir yığının üstüne bir öğe ekler.

Pop : Bir yığının üstünden bir öğeyi kaldırır.
IsEmpty : Yığının boş olup olmadığını kontrol eder
IsFull : Yığının dolu olup olmadığını kontrol eder.
Peek : En üsFeki öğenin değerini, onu çıkarmadan alır.

9.06.2022 5
 Yığın Veri Yapısının Çalışması

1. TOP bir işaretçi yığındaki en üst öğeyi takip etmek için kullanılır.
2. Yığını başla4rken, karşılaş4rarak yığının boş olup olmadığını kontrol edebilmemiz için değerini -1 olarak ayarladık TOP == -1.
3. Bir öğeyi eklerken TOP değerini ar4rırız TOP ve yeni öğeyi TOP değeri gösteririz. (TOP++)
4. Bir öğeyi çıkarırken işaret ePği öğeyi döndürür ve TOP değerini düşürürüz. (TOP--)
5. Bir öğeyi eklemeden önce, yığının dolu olup olmadığını kontrol ederiz.
6. Çıkarmadan önce, yığının boş olup olmadığını kontrol ederiz

9.06.2022 6
Stack Time Complexity (Zaman Karmaşıklığı)

• Bir yığının dizi tabanlı uygulaması için, push ve pop işlemleri sabit zaman alır, yani O(1)

9.06.2022 7
Stack (Yığın) Veri Yapısının Uygulamaları

• Yığın, uygulanması basit bir veri yapısı olmasına rağmen, çok güçlüdür. Bir yığının en yaygın kullanımları şunlardır:

• Bir kelimeyi tersine çevirmek için - Tüm harfleri bir yığına koyun ve çıkarın. LIFO yığın sırası nedeniyle, harfleri ters
sırada alacaksınız.

• Derleyi(Compiler) yapılarında kullanılır. (Prefix ve PosPix dönüşümlerinde kullanılır.)

• Browserdaki veya Office programlarındaki geri butonu stack man4ğı ile çalışır.(En son yapmış olduğu işlemi geri
alır(Yani en üs\eki tabağı çıkarır.))

9.06.2022 8
Queue (Kuyruk)

9.06.2022 9
Queue(Kuyruk) Veri Yapısı

• Kuyruk, programlamada yararlı bir veri yapısıdır.

• Sinema salonunun dışındaki bilet kuyruğuna benzetebiliriz, burada sıraya ilk giren kişi bile- alır.

• Sıra, İlk Giren İlk Çıkar (FIFO) kuralını izler.

• Doğrusal bir veri saklama yapısıdır.

9.06.2022 10
Temel (Queue) Kuyruk İşlemleri

• Enqueue : Sıranın sonuna bir öğe ekler.

• Dequeue : Sıranın önünden bir öğeyi kaldırır.

• IsEmpty : Kuyruğun boş olup olmadığını kontrol eder.

• IsFull : Kuyruğun dolu olup olmadığını kontrol eder.

• Peek: Sıranın önündeki elemanın değerini çıkarmadan elde eder.

• Kuyruk işlemlerinde ;

• Front = Kuyruğun önündeki elemanı temsil eder. -1 ise kuyruk boştur.

• Rear = Kuyruğun sonundaki elemanı temsil eder.

9.06.2022 11
Kuyruğun çalışması

• İki tane pointer belirliyoruz FRONT and REAR

• FRONT ilk elemanı izler

• REAR son elemanı izler

• Enqueue İşlemi • Dequeue İşlemi

• Kuyruğun dolu olup olmadığını kontrol eder. • Kuyruğun boş olup olmadığını kontrol eder.

• İlk eleman için FRONT = 0 olur • İlk gösterilen değeri döndürür.

• REAR 1 artar. • FRONT 1 artar.

• Her bir eleman eklendiğinde REAR yeni pozisyonunu • Son eleman için FRONT ve REAR -1 e konumlanır.
alır.

9.06.2022 12
9.06.2022 13
Kuyruk Sınırlamaları

• Aşağıdaki görselde görebileceğiniz gibi, kuyruğa alma ve kuyruğundan çıkarma işleminden sonra, kuyruğun boyutu
küçültülmüştür.

• Sadece sıra sıcrlandığında (tüm elemanlar kuyruktan çıkarıldığında) 0 ve 1 dizinlerini kullanılabilir.

• Bu, döngüsel kuyruk adı verilen değiş-rilmiş bir kuyruk taracndan gerçekleş-rilir .

9.06.2022 14
Queue Karmaşıklığı

• Bir dizi kullanıldığından bir kuyruktaki kuyruğa alma ve kuyruktan çıkarma işlemlerinin karmaşıklığı

O(1)

9.06.2022 15
Kuyruk Uygulamaları

• Çağrı Merkezi telefon sistemleri, onları arayan kişileri sırayla tutmak için Kuyrukları kullanır.

• CPU scheduling, Disk Scheduling

• IO Buffers, pipes, file IO ... (Senkron gerçekleşmesi gereken işlemlerde)

• Real -me sistemlerde interrupt planlanmasında…

• Bir klavye/fare girdisinin okunması (ardışık işlemler sırasıyla ele alınır!)

9.06.2022 16
Kuyruk Tipleri

• Farklı kuyruk -pleri vardır

1. Simple Queue

2. Circular Queue

3. Priority Queue

9.06.2022 17
1. Simple Queue

• FIFO kuralını takip eder.

• Çıkarma işlemi önde gerçekleşir.

• Ekleme işlemi sonda gerçekleşir.

9.06.2022 18
2. Circular Queue

• Dairesel bir kuyrukta, son öğe, dairesel bir bağlan4 oluşturan ilk öğeye işaret eder.

• Dairesel bir kuyruğun basit bir kuyruğa göre ana avantajı, daha iyi bellek kullanımıdır.

• Son konum doluysa ve ilk konum boşsa, ilk konuma bir eleman ekleyebiliriz. Bu işlem basit bir kuyrukta mümkün değildir.

• Basit kuyrukta karşılaşılan ve kuyruğun başında kalan kullanılamayan alan problemini çözmek için döngüsel kuyruk veri
yapısı geliş-rilmiş-r.

9.06.2022 19
[Link] Queue

• Standart kuyruk veri yapısı önceliklendirme eksikliği nedeniyle, birçok durumda (problemde) kullanılmak için uygun
olmayabilir.

• .

9.06.2022 20
[Link] Queue

[0] [1] [2] [3] [4]

12 Ekle Front : 0
12 Rear : 0

[0] [1] [2] [3] [4]

17 Ekle
Front : 1
17>12 12 17 Rear : 0

9.06.2022 21
[Link] Queue

[0] [1] [2] [3] [4]

23 Ekle Front : 2
23>17 olduğu için eklenir 12 17 23 Rear : 0

[0] [1] [2] [3] [4]

14 Ekle
Front : 3
14>23 olduğu içi 23 sağa kayar
12 14 17 23 Rear : 0
14>17 olduğu içi 17 sağa kayar
14>12 olmadığı için 1 indisli yere yerleşir

9.06.2022 22
[Link] Queue

[0] [1] [2] [3] [4]

Silme Front : 2
Front eleman silinir 12 14 17 Rear : 0

9.06.2022 23
 Ders Tamamlanmış5r.
KaMlımınız için Teşekkür Ederim.

9.06.2022 24