Polito DSA'da stack veya queue kodunu yazmak, yalnız son elemanı doğru çıkarmak değildir. Koleksiyon doluysa ne olacak, bellek ayırma başarısızsa hangi veri korunacak, nesneyi kim yok edecek? Bu sorular cevaplanmadığında küçük bir örnek çalışabilir; aynı nesne başka bir istemciden kullanıldığında hatalar ortaya çıkar. ADT yaklaşımı, davranış sözleşmesini iç temsilin önüne koyar.
Bu rehberde iki özgün C17 projesi kuracağız: array tabanlı bounded stack ve bağlı düğümlü bounded FIFO queue. Her projede header, implementation ve client ayrı dosyadır. Sakladığımız değerler yalnız int kopyalarıdır; generic pointer, ödünç string veya çok iş parçacıklı erişim tasarlamıyoruz. Amaç, başarılı işlem kadar başarısız işlemin de neyi değiştirmediğini göstermek.
Ders bağlamı: 'da kontrol edilen 01URN Algorithms and Data Structures 2026/27 resmî kılavuzu, implementation–interface–client ayrımını, çok dosyalı C programlarını, ADT ve bağlı stack/FIFO yapılarını kapsar. Tam ders kodu ve grup bilgisi için Polito DSA ders rehberini kullanın. Aşağıdaki projeler bağımsız alıştırmalardır; resmî sınav soruları veya değerlendirilecek teslim çözümleri değildir.
1. ADT'yi davranışla tanımlayın
Abstract Data Type, istemcinin hangi işlemleri yapabileceğini ve bu işlemlerin anlamını tanımlar. Stack için LIFO, son giren değerin önce çıkmasıdır. Queue için FIFO, ilk giren değerin önce çıkmasıdır. 10 ardından 20 eklediğimizde stack'ten 20,10, queue'dan 10,20 bekleriz. Kullanıcı açısından önemli fark budur; içerdeki struct alanlarının adları değildir.
Stack mutlaka array, queue mutlaka linked list olmak zorunda değildir. Burada iki farklı temsil seçerek arayüzle temsil ayrımını görünür kılıyoruz. Kapasite, hata sonucu ve sahiplik de sözleşmenin parçasıdır. “Pop çalışıyor” demek yerine “boş stack'te pop false döndürür; eleman sayısı ve çağıranın çıktı değişkeni korunur” diyebilmelisiniz.
İşlem seçimini küçük bir bağlamla sınayın: son eklediğiniz görev kimliğine önce dönmek istiyorsanız stack; bekleyen başvuruları geliş sırasıyla işlemek istiyorsanız queue uygundur. Öncelik puanına göre seçim gerekiyorsa bu FIFO sözleşmesi yeterli değildir. Temsili değiştirmeden önce kullanıcıya vaat ettiğiniz sıralama kuralını değiştirip değiştirmediğinizi kontrol edin. Aynı değerlerin depolanması, aynı problem davranışının sağlandığı anlamına gelmez.
2. Header, implementation ve client sınırını kurun
Header, public türün adını ve fonksiyon bildirimlerini taşır. Implementation, türün gerçek alanlarını ve işlemlerin gövdesini tanımlar. Client yalnız header'ı kullanarak nesneyi oluşturur, işlem yapar ve yok eder. İstemciye implementation dosyasını include etmek yerine iki C dosyasını ayrı derleme birimleri olarak bağlayacağız.
typedef struct Stack Stack;, iç alanları header'da açıklamadan tür adını bildirir. İstemci Stack * tutabilir fakat yalnız bu header ile nesneyi değer olarak oluşturamaz veya sizeof(Stack) hesaplayamaz. Buna opaque tür denir. Bu bir bellek güvenliği sistemi değildir; geçerli nesne, yaşam süresi ve sahiplik yükümlülükleri devam eder.
İki projeyi ayrı klasörlerde tutun. Stack klasöründe stack.h, stack.c, stack_client.c; queue klasöründe queue.h, queue.c, queue_client.c bulunsun. Header guard, aynı header bir derleme biriminde birden fazla include edildiğinde bildirimlerin tekrar açılmasını önler. Alanları header'a taşımak, istemciyi temsilin ayrıntılarına yeniden bağlar.
3. Stack arayüzünü önce okuyun
#ifndef STACK_H#define STACK_H#include <stdbool.h>#include <stddef.h>typedef struct Stack Stack;Stack *stack_create(size_t capacity);void stack_destroy(Stack *stack);bool stack_push(Stack *stack, int value);bool stack_pop(Stack *stack, int *out);bool stack_peek(const Stack *stack, int *out);size_t stack_size(const Stack *stack);#endifKapasite için 1 ile 64 arası değer kabul edilir; sıfır kapasite “boş stack oluştur” anlamına gelmez. Başarılı create boş bir nesne döndürür; geçersiz kapasite veya bellek yetersizliği NULL sonucunu verir. stack_size(NULL) sıfırdır, fakat bu NULL handle'ı geçerli nesne yapmaz. İstemci create sonucunu ayrıca kontrol etmelidir.
Push, verilen int değerini kopyalar. Pop silerek, peek silmeden bir kopyayı out üzerinden verir. Pozitif sonuç için out, ADT'nin iç belleğinden ayrı, geçerli ve yazılabilir bir int nesnesini göstermelidir. NULL handle veya NULL çıktı ile bool işlemler false döner; state ve mevcut çıktı değişmez. Dolu push ve boş pop/peek de aynı koruma kuralına uyar.
Bu küçük arayüzde false, hata nedenini tek başına sınıflandırmaz. İstemci her başarısızlığı “koleksiyon boş” diye yorumlamamalıdır: yanlış çıktı parametresi de aynı sonucu verebilir. Daha geniş bir uygulamada ayrı durum kodları tasarlayabilirsiniz; burada öğrenme hedefi, bütün başarısızlıklarda korunan state ve çıktı sözleşmesidir. Hata mesajı politikasını bu örneklerin sunduğu davranışla karıştırmayın.
4. Stack uygulamasında sahipliği ve aktif aralığı koruyun
#include "stack.h"#include <stdint.h>#include <stdlib.h>struct Stack { int *items; size_t size; size_t capacity;};Stack *stack_create(size_t capacity){ if (capacity == 0 || capacity > 64 || capacity > SIZE_MAX / sizeof(int)) { return NULL; } Stack *stack = malloc(sizeof *stack); if (stack == NULL) { return NULL; } stack->items = malloc(capacity * sizeof stack->items[0]); if (stack->items == NULL) { free(stack); return NULL; } stack->size = 0; stack->capacity = capacity; return stack;}void stack_destroy(Stack *stack){ if (stack == NULL) { return; } free(stack->items); free(stack);}bool stack_push(Stack *stack, int value){ if (stack == NULL || stack->size == stack->capacity) { return false; } stack->items[stack->size] = value; ++stack->size; return true;}bool stack_pop(Stack *stack, int *out){ if (stack == NULL || out == NULL || stack->size == 0) { return false; } int value = stack->items[stack->size - 1]; --stack->size; *out = value; return true;}bool stack_peek(const Stack *stack, int *out){ if (stack == NULL || out == NULL || stack->size == 0) { return false; } *out = stack->items[stack->size - 1]; return true;}size_t stack_size(const Stack *stack){ return stack == NULL ? 0 : stack->size;}Stack nesnesi ile int alanı iki ayrı allocation'dır. İkinci malloc başarısız olursa ilk alınan nesne serbest bırakılır; istemciye yarım nesne verilmez. Çarpma yapılmadan önce kapasitenin byte boyutuna sığıp sığmadığı denetlenir. Başarılı create bütün int alanını başlatmaz; yalnız eleman sayısını sıfır yapar. Henüz push ile yazılmamış alan okunmaz.
Invariant, 0 <= size <= capacity ve geçerli değerlerin [0,size) aralığında olmasıdır. Push önce doluluğu kontrol eder, sonra bir eleman yazar. Pop yalnız aktif son elemanı okur ve sayıyı azaltır. Başarısızlık kontrolü mutasyondan önce olduğu için NULL out, elemanı kaybettiren bir pop'a dönüşmez.
İç alanın ve handle nesnesinin sahibi ADT'dir; istemci bunları doğrudan free etmez. Başarılı create'in sahibi, destroy'u tam bir kez çağırır. stack_destroy(NULL) hiçbir işlem yapmaz. Yok edilmiş handle'ı yeniden kullanmak veya ikinci kez destroy etmek bu iznin kapsamına girmez; NULL kontrolü sarkan pointer'ı doğrulayamaz.
5. Stack istemcisinde LIFO ve başarısız işlemi sınayın
#include "stack.h"#include <stdio.h>int main(void){ Stack *stack = stack_create(2); if (stack == NULL) { return 1; } if (!stack_push(stack, 10) || !stack_push(stack, 20)) { stack_destroy(stack); return 1; } bool full_insert = stack_push(stack, 30); printf("full=%d\n", full_insert); int first = 0; int second = 0; if (!stack_pop(stack, &first) || !stack_pop(stack, &second)) { stack_destroy(stack); return 1; } printf("%d %d\n", first, second); int out = 77; bool empty_remove = stack_pop(stack, &out); printf("empty=%d out=%d size=%zu\n", empty_remove, out, stack_size(stack)); stack_destroy(stack); stack = NULL; return 0;}Çıktı sırasıyla full=0, 20 10 ve empty=0 out=77 size=0'dır. Full satırındaki sıfır, dolu koleksiyona ekleme denemesinin sonucudur; stack'in dolu olmadığı iddiası değildir. Otuz reddedildiği için önce yirmi, sonra on çıkar. Son başarısız pop, sentinel olarak seçtiğimiz 77'yi korur.
Stack klasöründe cc -std=c17 -Wall -Wextra -Wpedantic -Werror stack.c stack_client.c -o stack_client komutunu çalıştırın; sonra ./stack_client ile programı yürütün. Header ayrı executable değildir. Yalnız istemci C dosyasını derlemek bildirimleri görmenizi sağlar ama implementation bağlanmadığında fonksiyon tanımları eksik kalır. Compile hatasıyla linker hatasını bu ayrımla okuyun.
6. Queue arayüzünü FIFO sözleşmesiyle eşleştirin
#ifndef QUEUE_H#define QUEUE_H#include <stdbool.h>#include <stddef.h>typedef struct Queue Queue;Queue *queue_create(size_t capacity);void queue_destroy(Queue *queue);bool queue_enqueue(Queue *queue, int value);bool queue_dequeue(Queue *queue, int *out);bool queue_front(const Queue *queue, int *out);size_t queue_size(const Queue *queue);#endifEnqueue sona ekler, dequeue baştan çıkarır, front baştaki değeri silmeden kopyalar. Create, size ve destroy için stack'teki kapasite/NULL politikası geçerlidir. Ancak opaque türler ayrıdır: Queue handle'ını Stack API'sine vermek veya cast ile bu ayrımı zorlamak doğru kullanım değildir. Aynı hata politikası, iç temsillerin aynı olduğu anlamına gelmez.
Bağlı queue'yu yine bounded yapıyoruz: linked temsil, sınırsız bellek garantisi vermez. Capacity en fazla kaç aktif eleman tutulacağını belirler; bütün düğümler create sırasında ayrılmaz. Her başarılı enqueue yeni bir düğüm alır. Dolu koleksiyona ekleme reddedilir; malloc başarısızlığı da false verir. Her iki durumda sıra ve eleman sayısı korunmalıdır.
7. FIFO bağlantılarını ve hata sözleşmesini birlikte koruyun
#include "queue.h"#include <stdlib.h>typedef struct Node { int value; struct Node *next;} Node;struct Queue { Node *head; Node *tail; size_t size; size_t capacity;};Queue *queue_create(size_t capacity){ if (capacity == 0 || capacity > 64) { return NULL; } Queue *queue = malloc(sizeof *queue); if (queue == NULL) { return NULL; } queue->head = NULL; queue->tail = NULL; queue->size = 0; queue->capacity = capacity; return queue;}void queue_destroy(Queue *queue){ if (queue == NULL) { return; } Node *node = queue->head; while (node != NULL) { Node *next = node->next; free(node); node = next; } free(queue);}bool queue_enqueue(Queue *queue, int value){ if (queue == NULL || queue->size == queue->capacity) { return false; } Node *node = malloc(sizeof *node); if (node == NULL) { return false; } node->value = value; node->next = NULL; if (queue->tail == NULL) { queue->head = node; } else { queue->tail->next = node; } queue->tail = node; ++queue->size; return true;}bool queue_dequeue(Queue *queue, int *out){ if (queue == NULL || out == NULL || queue->head == NULL) { return false; } Node *old_head = queue->head; int value = old_head->value; queue->head = old_head->next; if (queue->head == NULL) { queue->tail = NULL; } --queue->size; free(old_head); *out = value; return true;}bool queue_front(const Queue *queue, int *out){ if (queue == NULL || out == NULL || queue->head == NULL) { return false; } *out = queue->head->value; return true;}size_t queue_size(const Queue *queue){ return queue == NULL ? 0 : queue->size;}Boş queue'da size=0 ve hem head hem tail NULL'dır. Pozitif boyutta head ilk, tail son düğümü gösterir; tail'in next alanı NULL kalır. Yeni düğümün değeri ve next alanı, mevcut zincire bağlanmadan önce hazırlanır. Böylece malloc başarısızlığında hiçbir bağlantı veya sayaç değişmez.
Dequeue önce çıktı koşulunu denetler, değeri yerel int'e alır, head'i ilerletir ve eski düğümü serbest bırakır. Son eleman çıktıysa tail de NULL yapılır. Bu satırı unutmak, sonraki enqueue'nun yok edilmiş düğüme yazmasına yol açabilir. Çıktı, ADT belleğinden ayrı nesneye yerel değer kopyasından yazılır; free edilmiş düğüm tekrar okunmaz.
Queue destroy, sıradaki adresi düğümü serbest bırakmadan önce saklar; kalan bütün düğümleri ve sonunda handle'ı bırakır. İstemcinin başlangıçtaki int değişkeni bu sahiplik zincirine girmez. Sakladığımız pointer değil, değer kopyasıdır. String veya başka nesne adresi eklemek isterseniz bu API'yi yalnız tür adını değiştirerek genelleştirmeyin; yeni kopyalama, yaşam süresi ve yok etme kuralları gerekir.
8. Boş kuyruğu yeniden kullanarak son düğüm durumunu sınayın
#include "queue.h"#include <stdio.h>int main(void){ Queue *queue = queue_create(2); if (queue == NULL) { return 1; } if (!queue_enqueue(queue, 10) || !queue_enqueue(queue, 20)) { queue_destroy(queue); return 1; } bool full_insert = queue_enqueue(queue, 30); printf("full=%d\n", full_insert); int first = 0; int second = 0; if (!queue_dequeue(queue, &first) || !queue_dequeue(queue, &second)) { queue_destroy(queue); return 1; } printf("%d %d\n", first, second); int out = 77; bool empty_remove = queue_dequeue(queue, &out); printf("empty=%d out=%d size=%zu\n", empty_remove, out, queue_size(queue)); if (!queue_enqueue(queue, 30) || !queue_dequeue(queue, &out)) { queue_destroy(queue); return 1; } printf("again=%d size=%zu\n", out, queue_size(queue)); queue_destroy(queue); queue = NULL; return 0;}Çıktı full=0, 10 20, empty=0 out=77 size=0 ve again=30 size=0'dır. Queue FIFO sırasını korur; doluyken otuz eklenmemiştir. İki dequeue'dan sonra boş nesneye otuz ekleyip tekrar çıkarmak, son düğümden boş queue'ya geçişi ve yeniden başlangıcı aynı testte kapsar.
Queue klasöründe cc -std=c17 -Wall -Wextra -Wpedantic -Werror queue.c queue_client.c -o queue_client ile derleyin, ardından ./queue_client çalıştırın. Handle'ı destroy sonrasında NULL yapmak yalnız o değişkeni değiştirir. Daha önce aynı adresi başka bir handle değişkenine kopyaladıysanız o alias da artık kullanılmamalıdır; destroy bütün alias'ları otomatik NULL yapmaz.
9. Bağımsız testte hata korumasını ve maliyeti ölçün
Kapasite bir ve 64 için oluşturma, doldurma, taşan ekleme, boşaltma ve yeniden ekleme yapın. Tekrarlanan, negatif ve int sınırlarındaki değerlerin kopyasını kontrol edin. Pop/dequeue/peek/front için NULL çıktı verdiğinizde sonradan doğru değerin hâlâ okunabildiğini gösterin. Boş işlemde dönüş değerini, sentinel'i ve boyutu birlikte sınayın; yalnız terminaldeki son eleman yeterli değildir.
Bellek yetersizliğini gerçek makinenin RAM'ini tüketerek test etmeyin. Test allocator'ıyla belirli malloc çağrısını kontrollü olarak başarısız yapabilirsiniz: stack'in ikinci allocation'ında ilk nesne bırakılmalı; queue enqueue başarısızlığında eski sıra korunmalıdır. Test sayacı, alınan ve bırakılan alanları izleyebilir. Dangling handle kullanarak “koruma test edildi” sonucu çıkarmayın; bu kullanım sözleşme dışıdır.
Genellenmiş modelde push/pop/peek ve queue'daki bağlantı güncellemeleri sabit sayıda adım kullanır. Malloc/free maliyetini ayrıca değerlendirin; allocator'ın bütün ortamlarda sabit süreli olduğunu iddia etmiyoruz. Stack alanı kapasiteyle, bağlı queue alanı aktif düğüm sayısıyla büyür; queue destroy bütün düğümleri gezer. Örneklerimiz kapasiteyi 64'le sınırlar. Tek iş parçacığında kullanılır; eşzamanlı erişim için kilit veya başka bir düzen eklenmemiştir.
10. Polito DSA'da sonraki adımı sözleşme hatanıza göre seçin
Temsil çizimi karışıyorsa Linked List Lab rehberindeki düğüm/bağlantı gözlem yaklaşımına dönün. Bu altı kaynak dosyanın Lab'de hazır bulunduğunu veya oraya yapıştırılarak çalıştırılabildiğini iddia etmiyoruz. Bağımsız derleyici ve test projesi gerekir. Araçların giriş noktası Academy Lab sayfasıdır.
Array/struct ön koşulunuz zayıfsa C veri modeli rehberini; çalışma sırasını düzenlemek için 12 haftalık Polito DSA planını kullanın. Kendi ders kodunuz ve bir hata kaydıyla Polito DSA özel ders sürecini inceleyebilirsiniz. Hedef, öğrencinin kendi arayüzünü ve uygulamasını gerekçelendirmesidir.
Nesne yaşam süresi için 6.2.4, free için 7.22.3.3 ve malloc için 7.22.3.4 bölümleri WG14 N1570 C11 komite taslağında okunabilir. Bu kamuya açık referans güncel nihai standart olarak sunulmuyor; projelerin derleme hedefi C17'dir. NULL davranışı, yaşam süresi bitmiş nesneye erişme izni değildir.
Websoftik Academy, Politecnico di Torino'dan bağımsızdır. Güncel sınav kuralları için kendi öğretim grubunuzun duyuruları esas alınır. Bu özgün alıştırmalar belirli not veya geçme garantisi vermez; değerlendirilecek ödev veya sınav öğrenci yerine çözülmez.
