C
Yığın ve kuyruk
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.
Örnek çözümü göster
#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;
}
Kendini test et
-
Yığın ve kuyruk
- yığın
- LIFO
- kuyruk
- FIFO
- push
- ekle
- pop
- çıkar
-
Yığında push(10), push(20) sonra iki pop yapılırsa çıktı ne olur?
Cevabı göster
20 10 — LIFO: son giren 20 önce, 10 sonra çıkar.
-
Push işlemi
void stack_push(Stack *s, int v) { s->data[s->____++] = v; }
Cevabı göster
void stack_push(Stack *s, int v) { s->data[s->top++] = v; }
Sıradaki ders: Özet - Dinamik veri
