STEP 5.3　リスト、スタック、キューの操作　確認

準備：

関係ファイルは1つのヘッダファイルと、3つのソースファイル

list.objとstackqueue.objを、このあとの課題プログラムでリンクします。（再利用）

<コンパイル>
gcc -c list.c
gcc -c stackqueue.c
gcc -c 0503.c
gcc -o 0503 0503.o list.o stackqueue.o


./0503 （UNIXの場合は、./0503 スペースはどこにも入れないことに注意)


<実行結果> (練習問題の１つ）

push(a)
push(b)
enq(pop())
enc(c)
oush(d)
push(deq())
x = pop()

を、C言語で実行してみる

以下、実行例 (main関数を確かめよう）

x = b 　　（問題の解答はb）

Stack 　　（最終のスタックを、プリント)

d
a

Queue 　　（最終のキューを、プリント)

c

解答例

以下、list.h

#include <stdio.h>
#include <stdlib.h>

/* リスト構造体 */
typedef struct list {
    struct list *next; 
    char data; 
} List; 

/* 関数のプロトタイプ宣言 */
List *create(void); 

char access(List *L, int i);
void insert(List *L, int i, char x);
void delete(List *L, int i);
void initialize(List *L);
int empty(List *L);
void printlist(List *L); 
void FreeData(List *L);


void pushdown (List *L, char x);
char popup (List *L);

void enqueue(List *L, char x);
char dequeue(List *L);


以下、list.c

#include "list.h"

List *create(void){
    List *p;
    p = (List *)malloc(sizeof(List)); 
    p->next = NULL;
    p->data = '\0';
    return (p);
}

char access(List *L, int i) {
    if (L->next != NULL) {
       if (i > 1) { 
           return (access(L->next,i-1)); 
       } else { 
           return (L->next->data);
       }
    } else {
        printf("List L ends before arriving "); 
        printf("at the position.\n");
        return('\0');
   }
}

void insert(List *L, int i, char x) {
    List *p;
    if (L != NULL) {
        if (i > 1) { /* 再帰条件 */
            insert(L->next,i-1,x);
        } else {
            p = create(); 
            p->data = x; 
            p->next = L->next; 
            L->next = p; 
        }
    } else {
         printf("List L ends before arriving "); 
         printf("at the position.\n");
    }
}

void delete(List *L, int i) {
    List *del;
    if (L->next != NULL) { 
        if(i > 1) {
            delete(L->next,i-1);
        } else {
            del = L->next;
            L->next = L->next->next; 
            free(del); 
        }
     } else {
         printf("List L ends before arriving "); 
         printf("at the position.\n");
     }
}

void initialize (List *L) {
    while (!empty(L)) {
        delete(L,1);
    }
}


int empty(List *L){
    if (L -> next == NULL) {
        return(1);
    }
        return(0);
}


void printlist (List *L) {
    printf("\n");

    while (L != NULL) {
       if (L -> data != '\0') 
           printf("%c \n", L -> data);
        L = L -> next;
    }
}

/* 再帰 */
void FreeData(List *L) {
    if (L != NULL) { 
        FreeData(L -> next);
        free (L);
    } 
}

以下、stackqueue.c

#include "list.h"

void pushdown (List *L, char x) {
    insert(L,1,x);
}

char popup (List *L) {
    char pop;
    pop = access(L,1);
    delete (L,1);
    return(pop);
}


void enqueue(List *L, char x) {
    if (L -> next != NULL){
        enqueue(L -> next,x); 
    } else {
        insert(L,1,x); 
    }
}

char dequeue(List *L) {
    char deq;
    deq = access(L,1);
    delete (L,1);
    return(deq);
}

以下、例題用 (以前とりあげたクイズを実行してみます）
0503.c

#include "list.h"

int main (void) {
    char x;

    List *Stack;
    List *Queue;

    Stack = create();
    Queue = create();

    pushdown (Stack, 'a');
    pushdown (Stack, 'b');
    enqueue(Queue, popup(Stack));
    enqueue(Queue, 'c');

    pushdown(Stack, 'd');
    pushdown(Stack, dequeue(Queue));

    x = popup(Stack);
 
    printf("x = %c\n", x);

    printf("\nStack\n");
    printlist(Stack);

    printf("\nQueue\n");
    printlist(Queue);

    FreeData(Stack); FreeData(Queue);

    return 0;
}