STACK VE QUEUE YAPILARI
AMAÇ
Bu deney föyü ile öğrenciler, C programlama dilinde Stack (Yığın) ve Queue (Kuyruk) veri
yapılarını teorik olarak kavrayacak ve bu yapıları uygulayan örnek programlarla konuyu
pekiştirecektir.
TEORİK BİLGİ
1. Stack (Yığın) Nedir?
• Stack, LIFO (Last In, First Out - Son Giren İlk Çıkar) prensibine dayalı bir veri
yapısıdır.
• Elemanlar yalnızca bir uçtan (top) eklenir ve çıkarılır.
• Temel işlemler:
– Push: Yığına eleman ekler.
– Pop: Yığından elemanı çıkarır ve döndürür.
– Peek/Top: Yığının tepesindeki elemanı döndürür (çıkarmadan).
– isEmpty: Yığının boş olup olmadığını kontrol eder.
• Kullanım Alanları: Fonksiyon çağrı yığınları, geri alma (undo) işlemleri, ifade
değerlendirme (ör. postfix).
2. Queue (Kuyruk) Nedir?
• Queue, FIFO (First In, First Out - İlk Giren İlk Çıkar) prensibine dayalı bir veri
yapısıdır.
• Elemanlar bir uçtan (rear) eklenir, diğer uçtan (front) çıkarılır.
• Temel işlemler:
– Enqueue: Kuyruğa eleman ekler.
– Dequeue: Kuyruktan elemanı çıkarır ve döndürür.
– Front: Kuyruğun başındaki elemanı döndürür (çıkarmadan).
– isEmpty: Kuyruğun boş olup olmadığını kontrol eder.
• Kullanım Alanları: İşlemci kuyrukları, yazdırma kuyrukları, BFS (Breadth-First
Search).
Farklılıklar
Özellik Stack (Yığın) Queue (Kuyruk)
Çalışma Prensibi LIFO FIFO
Ekleme/Çıkarma Tek uç (top) İki uç (rear/front)
Örnek Kullanım Parantez kontrolü Görev sıralama
DENEY UYGULAMALARI
ÖRNEK 1: Stack Kullanımı - Basit Push ve Pop İşlemleri
Amaç: Bir tamsayı yığını oluşturup eleman ekleme ve çıkarma işlemlerini gerçekleştirme.
#include <stdio.h>
#include <stdlib.h>
#define MAX 5
struct Stack {
int items[MAX];
int top;
};
void initStack(struct Stack* s) {
s->top = -1;
}
int isFull(struct Stack* s) {
return s->top == MAX - 1;
}
int isEmpty(struct Stack* s) {
return s->top == -1;
}
void push(struct Stack* s, int value) {
if (isFull(s)) {
printf("Yigin dolu!\n");
} else {
s->items[++s->top] = value;
printf("%d yigina eklendi.\n", value);
}
}
int pop(struct Stack* s) {
if (isEmpty(s)) {
printf("Yigin bos!\n");
return -1;
} else {
return s->items[s->top--];
}
}
int main() {
struct Stack s;
initStack(&s);
push(&s, 10);
push(&s, 20);
push(&s, 30);
printf("Cikarilan: %d\n", pop(&s)); // 30
printf("Cikarilan: %d\n", pop(&s)); // 20
return 0;
}
Çıktı:
10 yigina eklendi.
20 yigina eklendi.
30 yigina eklendi.
Cikarilan: 30
Cikarilan: 20
Alıştırma: Yığını 6 elemanla doldurmaya çalışın ve “Yığın dolu” mesajını gözlemleyin.
ÖRNEK 2: Stack ile Parantez Kontrolü
Amaç: Bir ifadenin parantezlerinin doğru eşleşip eşleşmediğini kontrol etme.
#include <stdio.h>
#include <string.h>
#define MAX 100
struct Stack {
char items[MAX];
int top;
};
void initStack(struct Stack* s) {
s->top = -1;
}
void push(struct Stack* s, char value) {
s->items[++s->top] = value;
}
char pop(struct Stack* s) {
return s->items[s->top--];
}
int isEmpty(struct Stack* s) {
return s->top == -1;
}
int checkParentheses(char* expr) {
struct Stack s;
initStack(&s);
for (int i = 0; expr[i]; i++) {
if (expr[i] == '(') {
push(&s, '(');
} else if (expr[i] == ')') {
if (isEmpty(&s)) return 0; // Kapanmamış parantez
pop(&s);
}
}
return isEmpty(&s); // Yığın boşsa doğru
}
int main() {
char expr[] = "((a+b)*(c-d))";
if (checkParentheses(expr)) {
printf("Parantezler dogru.\n");
} else {
printf("Parantezler hatali.\n");
}
return 0;
}
Çıktı:
Parantezler dogru.
Alıştırma: "(a+b))" ifadesini test edin ve sonucu açıklayın.
ÖRNEK 3: Queue Kullanımı - Basit Enqueue ve Dequeue İşlemleri
Amaç: Bir tamsayı kuyruğu oluşturup eleman ekleme ve çıkarma işlemlerini
gerçekleştirme.
#include <stdio.h>
#include <stdlib.h>
#define MAX 5
struct Queue {
int items[MAX];
int front, rear;
};
void initQueue(struct Queue* q) {
q->front = -1;
q->rear = -1;
}
int isFull(struct Queue* q) {
return q->rear == MAX - 1;
}
int isEmpty(struct Queue* q) {
return q->front == -1 || q->front > q->rear;
}
void enqueue(struct Queue* q, int value) {
if (isFull(q)) {
printf("Kuyruk dolu!\n");
} else {
if (q->front == -1) q->front = 0;
q->items[++q->rear] = value;
printf("%d kuyruga eklendi.\n", value);
}
}
int dequeue(struct Queue* q) {
if (isEmpty(q)) {
printf("Kuyruk bos!\n");
return -1;
} else {
int value = q->items[q->front++];
if (q->front > q->rear) {
q->front = q->rear = -1; // Kuyruk boşaldı
}
return value;
}
}
int main() {
struct Queue q;
initQueue(&q);
enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);
printf("Cikarilan: %d\n", dequeue(&q)); // 10
printf("Cikarilan: %d\n", dequeue(&q)); // 20
return 0;
}
Çıktı:
10 kuyruga eklendi.
20 kuyruga eklendi.
30 kuyruga eklendi.
Cikarilan: 10
Cikarilan: 20
Alıştırma: Kuyruğu tamamen doldurun ve ardından tüm elemanları çıkarın.
ÖRNEK 4: Queue ile Görev Sıralama Simülasyonu
Amaç: Görevlerin sırayla işlenmesini simüle etme.
#include <stdio.h>
#define MAX 10
struct Queue {
char tasks[MAX][50];
int front, rear;
};
void initQueue(struct Queue* q) {
q->front = -1;
q->rear = -1;
}
void enqueue(struct Queue* q, char* task) {
if (q->rear == MAX - 1) {
printf("Kuyruk dolu!\n");
} else {
if (q->front == -1) q->front = 0;
q->rear++;
strcpy(q->tasks[q->rear], task);
printf("Görev eklendi: %s\n", task);
}
}
char* dequeue(struct Queue* q) {
static char empty[] = "Bos";
if (q->front == -1 || q->front > q->rear) {
printf("Kuyruk bos!\n");
return empty;
} else {
return q->tasks[q->front++];
}
}
int main() {
struct Queue q;
initQueue(&q);
enqueue(&q, "Dosya yazdir");
enqueue(&q, "E-posta gönder");
enqueue(&q, "Veri tabani guncelle");
printf("Islenen görev: %s\n", dequeue(&q)); // Dosya yazdir
printf("Islenen görev: %s\n", dequeue(&q)); // E-posta gönder
return 0;
}
Çıktı:
Görev eklendi: Dosya yazdir
Görev eklendi: E-posta gönder
Görev eklendi: Veri tabani guncelle
Islenen görev: Dosya yazdir
Islenen görev: E-posta gönder
Alıştırma: Yeni görevler ekleyerek kuyruğu doldurun ve sırayla işletin.
Ek Sorular: 1. Stack ve Queue yapılarını dinamik bellek (malloc) kullanarak nasıl
implemente edersiniz? 2. Stack ile Queue arasındaki performans farklarını tartışın.