Yığın ve kuyruk
- C kursu
- Orta seviye
- Ders 74/116
- 5 dk
Bağlı listeyle yığın ve kuyruk uygulamayı öğrenirsin.
Yığın ve kuyruk
Bir yığın (stack), son giren ilk çıkar (LIFO) ilkesine uyar: en son eklenen ilk çıkarılır. Bir kuyruk (queue) ise ilk giren ilk çıkar (FIFO) ilkesine uyar.
Yığın iki temel işleme sahiptir: push (ekle) ve pop (çıkar). Diziyle uygulandığında bir top indisini tutarız; push data[top++] = v;, pop data[--top] döndürür. Kuyrukta enqueue ve dequeue işlemleri vardır; baş ve son ayrı tutulur. Yığın, fonksiyon çağrılarını ve geri izlemeyi (backtracking) izlemek için kullanılır; kuyruk, sırayla işlenen görevler için.
Dizi tabanlı yığın
Yığın, sabit boyutlu bir dizi ve bir top indisi ile uygulanır. top bir sonraki boş yeri gösterir; başlangıçta 0'dır.
Tanımlar: typedef struct { int data[100]; int top; } Stack;. void stack_init(Stack *s) { s->top = 0; } ile başlatılır. void stack_push(Stack *s, int v) { s->data[s->top++] = v; } ekler. int stack_pop(Stack *s) { return s->data[--s->top]; } çıkarır. top++ önce değeri yazar sonra artırır; --top önce azaltır sonra okur. Bu yüzden push top'u kullanıp artırır, pop önce azaltıp okur. Kapasiteyi aşmamak uygulamaya bağlıdır; basit örnekte atlanır.
Uygulama Yığın uygula
void stack_init(Stack *s) yaz: s->top = 0;. void stack_push(Stack *s, int v) yaz: s->data[s->top++] = v;. int stack_pop(Stack *s) yaz: return s->data[--s->top];. main'de Stack s; stack_init(&s);, stack_push(&s, 10);, stack_push(&s, 20);, printf("%d %d\n", stack_pop(&s), stack_pop(&s)); çağır.
Başlangıç kodu
#include <stdio.h>
#include <stdlib.h>
#define STACK_CAP 100
typedef struct {
int data[STACK_CAP];
int top;
} Stack;
// stack_init: top = 0
// stack_push: data[top++] = v
// stack_pop: data[--top] döndür
// main: başlat, 10 ve 20 push et, iki pop'u yazdır
int main(void) {
// buraya yaz
return 0;
}Örnek çözüm
#include <stdio.h>
#include <stdlib.h>
#define STACK_CAP 100
typedef struct {
int data[STACK_CAP];
int top;
} Stack;
void stack_init(Stack *s) { s->top = 0; }
void stack_push(Stack *s, int v) {
s->data[s->top++] = v;
}
int stack_pop(Stack *s) {
return s->data[--s->top];
}
int main(void) {
Stack s;
stack_init(&s);
stack_push(&s, 10);
stack_push(&s, 20);
printf("%d %d\n", stack_pop(&s), stack_pop(&s));
return 0;
}Beklenen çıktı
20 10
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Yığın ve kuyruk
| Kavram | Anlamı |
|---|---|
yığın |
LIFO |
kuyruk |
FIFO |
push |
ekle |
pop |
çıkar |
2 Yığında push(10), push(20) sonra iki pop yapılırsa çıktı ne olur?
- 10 10
- 10 20
- 20 10 Doğru cevap
- 20 20
Açıklama: LIFO: son giren 20 önce, 10 sonra çıkar.
3 Push işlemi
void stack_push(Stack *s, int v) { s->data[s->____++] = v; }void stack_push(Stack *s, int v) { s->data[s->top++] = v; }Açıklama: data[top++] önce top'a yazar, sonra artırır.