うさぎでもわかるスタックとキュー

#include<stdio.h>
#define SIZE  10 // スタックサイズ

// スタック用構造体
struct STACK {
    int elm[SIZE]; // 各要素
    int top; // データがどの場所まであるかを記憶
} ;

// 初期化関数　STACKがポインタなのは参照渡しにするため
void init(struct STACK *s) {
    s->top = -1; // スタックが空 -> -1
}

// 出力関数　STACKがポインタなのは参照渡しにするため
void print(struct STACK *s){
    printf("スタックの中身:");
    for(int i = 0; i <= s->top; i += 1) {
        printf("%d ",s->elm[i]);
    }
    printf("\n");
}

// push関数　STACKが（以下省略）
void push(int x, struct STACK *s){
    s->top += 1; // データの場所が1つ増やす
    s->elm[s->top] = x; // 要素格納
}

// pop関数　
int pop(struct STACK *s){
    int out_data = s->elm[s->top]; // 出力する要素
    s->top -= 1; // データの場所が1つ減る
    return out_data;
}

// スタックが空か判定
int isEmpty(struct STACK *s){
    if(s->top != -1) {
        return 0;
    }
    else {
        return 1;
    }
}

int main() {
    struct STACK s;
    init(&s); // 初期化

    push(10,&s); // スタックの中身 10
    push(20,&s); // スタックの中身 10 -> 20
    push(30,&s); // スタックの中身 10 -> 20 -> 30
    print(&s);

    printf("pop: %2d\n",pop(&s)); // スタックの中身 10 -> 20
    printf("pop: %2d\n",pop(&s)); // スタックの中身 10
    push(40,&s); // スタックの中身 10 -> 40
    print(&s);

    // スタックが空になるまでひたすらpop
    while(! isEmpty(&s)) {
        printf("pop: %2d\n",pop(&s));
    }

    return 0;
}

スタックの中身:10 20 30
pop: 30
pop: 20
スタックの中身:10 40
pop: 40
pop: 10

#include<stdio.h>
#define SIZE 5

struct QUEUE {
    int elm[SIZE]; // データの中身
    int start;     // キューのデータの始まり
    int end;       // キューのデータの終わり
} ;

// 初期化関数　QUEUEがポインタなのは参照渡しにするため
void init(struct QUEUE *q) {
    q->start = 0;
    q->end = 0;
}

// キューを環状と考え、次のキューの場所を計算する関数
// Ex. SIZE = 5 のとき、3番目の次は4番目、4番目の次は0番目
int nextStep(int x) {
    return (x + 1) % SIZE;
}

// キュー内のデータ出力関数　QUEUEがポインタなのは参照渡しにするため
void print(struct QUEUE *q){
    printf("キューの中身:");
    for(int i = q->start; i != q->end; i = nextStep(i)) {
        printf("%d ",q->elm[i]);
    }
    printf("\n");
}

// enqueue関数　QUEUEが（以下省略）
void enqueue(int x, struct QUEUE *q){
    q->elm[q->end] = x;
    q->end = nextStep(q->end);
}

// dequeue関数　
int dequeue(struct QUEUE *q){
    int out_data = q->elm[q->start];
    q->start = nextStep(q->start);
    return out_data;
}

// キューが空かどうかを判定
int isEmpty(struct QUEUE *q){
    if(q->start != q->end) {
        return 0;
    }
    else {
        return 1;
    }
}


int main() {
    struct QUEUE q;
    init(&q); // 初期化

    enqueue(10,&q); // キューの中身 10
    enqueue(20,&q); // キューの中身 10 -> 20
    enqueue(30,&q); // キューの中身 10 -> 20 -> 30
    print(&q);

    printf("dequeue: %2d\n",dequeue(&q)); // キュー中身 20 -> 30
    printf("dequeue: %2d\n",dequeue(&q)); // キューの中身 30

    enqueue(40,&q); // キューの中身 30 -> 40
    enqueue(50,&q); // キューの中身 30 -> 40 -> 50
    enqueue(60,&q); // キューの中身 30 -> 40 -> 50 -> 60

    print(&q);

    // スタックが空になるまでひたすらpop
    while(! isEmpty(&q)) {
        printf("dequeue: %2d\n",dequeue(&q));
    }

    return 0;
}

キューの中身:10 20 30
dequeue: 10
dequeue: 20
キューの中身:30 40 50 60
dequeue: 30
dequeue: 40
dequeue: 50
dequeue: 60

push(a)
push(b)
enq(pop())
enq(c)
push(d)
push(deq())
x ← pop()

push(a)     # スタックにaを入れる　スタック [a]
push(b)     # スタックにbを入れる　スタック [a,b]
enq(pop())  # スタックからbを取り出し、キューへ入れる　スタック [a],  キュー [b]
enq(c)      # キューにcを入れる　キュー [b,c]
push(d)     # スタックにdを入れる　スタック [a,d]
push(deq()) # キューからbを取り出し、スタックに入れる　 キュー [c],  スタック [a,d,b]
x ← pop()   # スタックからbを取り出す

初期状態　キュー [A,B,C,D]　スタック  []
deq_push(1回目)　キュー [B,C,D]　スタック　[A]  (Aをスタックに)
deq_push(2回目)　キュー [C,D]　スタック　[A,B] (Bをスタックに)
deq_push(3回目)　キュー [D]　スタック　[A,B,C] (Cをスタックに)
pop_enq(1回目)　キュー [D,C]　スタック　[A,B] (Cをキューに)
pop_enq(2回目)　キュー [D,C,B]　スタック　[A] (Bをキューに)
pop_enq(3回目)　キュー [D,C,B,A]　スタック　[] (Aをキューに)