いろいろな処理のプログラムを書いていると、データを貰ったのに処理は少し後で行いたいことがあります。それはまとめて処理したかったり、処理の順序を入れ替えたかったりなど様々な理由があります。

例えば CPU 自身が、サブルーチンを呼ぶ時には、今、処理をしている命令のあるアドレスをスタックポインタというレジスタが指し示すメモリに、いったん保存しておいて、サブルーチンの処理が終了したら、保存しておいたアドレスからプログラムを再開しています。他にも普通の数式を解釈する時も、左から順に計算していくのですが、括弧や乗除算を見つけると、そちらを先に計算する必要があるので、それまでの値をいったん保存するためにも、スタックの処理を用います。このようにデータを「先入れ後出し」(LIFO: Last In First Out)または「後入れ先出し」(FILO: First In Last Out)するものを「スタック」と呼んでいます。

スタック

また、何らかのデバイスに出力をしたいのだけど、出力はデバイスがビジーでないときにしか行えないので、それまでデータを貯めておいて、ビジーでない間に順に出力するなんて言うこともあります。こちらは「先入れ先出し」(FIFO:First In First Out)となり、待ち行列または「キュー」と呼びます。

キュー (コンピュータ)

前回までにリスト構造を学んだので、リストを使って、スタックとキューを書いてみましょう。

まず、スタックです。スタックは片側からしかデータをアクセスしないので、単方向リストを使ってみました。

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

typedef struct node {
  int val;
  struct node* next;
} Node;

typedef struct stack {
  struct node* top;
} Stack;

Node* create_node(int val) {
  Node *node = (Node*)malloc(sizeof(Node));
  node->val = val;
  node->next = NULL;
  return node;
}

void create_stack(Stack* stack) {
  Node *dummy = (Node*)malloc(sizeof(Node));
  dummy->next = dummy;
  stack->top =  dummy;
}

void destroy_stack(Stack* stack) {
   Node *current = stack->top->next;
   Node *next;
   while (current != stack->top) {
        next = current->next;
        free(current);
        current = next;
    }
    free(stack->top);
    stack->top = NULL;
}

void print_stack(Stack* stack) {
  Node *current = stack->top->next;
  while (current != stack->top) {
    printf("%d ", current->val);
    current = current->next;
  }
  printf("\n");
}

typedef unsigned int byte;

void dump_stack(Stack* stack) {
  printf("Top :%08x next:%08x\n",
    (byte)stack->top, (byte)stack->top->next);
  Node *current = stack->top->next;
  while (current != stack->top) {
    printf("Node:%08x next:%08x val:%d\n",
     (byte)current, (byte)current->next, current->val);
    current = current->next;
  }
}

int push_stack(Stack* stack, int val) {
  Node *node = create_node(val);
  if (node != NULL) {
    node->next = stack->top->next;
    stack->top->next = node;    
    return -1;
  }
  return 0;
}

int pop_stack(Stack* stack) {
  int r = 0;
  Node *node = stack->top->next;
  if (node != stack->top) {
    r = node->val;
    stack->top->next = node->next;
    free(node);
  }
  return r;
}

int empty_stack(Stack* stack) {
  return stack->top->next == stack->top;
}

void main() {
  Stack stack;

  create_stack(&stack);
  
  if (!push_stack(&stack, 10)) exit(1);
  if (!push_stack(&stack, 20)) exit(1);
  if (!push_stack(&stack, 30)) exit(1);

  while (!empty_stack(&stack)) {
    printf("%d\n", pop_stack(&stack));
  }

  destroy_stack(&stack);
}

このプログラムを実行すると、

30
20
10

と出力されます。スタックに値を入れるには push_stack()、出すには pop_stack() です。push 出来ない時(メモリが確保できない時)は、int型で FALSE の値(1)が戻ります。pop の時にデータが空で取り出せない時は、エラー値を用意できないので、0を返しています。予め empty_stack() で空で無いことを確認してください。内部のデータを確認したい時には dump_stack() を呼び出して確認してください。

同じようにキューも書いてみます。こちらは両端をアクセスするので双方向リストを使いました。

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

typedef struct node {
  int val;
  struct node* next;
  struct node* prev;
} Node;

typedef struct queue {
  struct node* top;
} Queue;

Node* create_node(int val) {
  Node *node = (Node*)malloc(sizeof(Node));
  node->val = val;
  node->next = NULL;
  node->prev = NULL;
  return node;
}

void create_queue(Queue *que) {
  Node *dummy = (Node*)malloc(sizeof(Node));
  dummy->next = dummy;
  dummy->prev = dummy;
  que->top =  dummy;
}

void destroy_queue(Queue* que) {
   Node *current = que->top->next;
   Node *next;
   while (current != que->top) {
        next = current->next;
        free(current);
        current = next;
    }
    free(que->top);
    que->top = NULL;
}

void print_queue(Queue* que) {
  Node *current = que->top->next;
  while (current != que->top) {
    printf("%d ", current->val);
    current = current->next;
  }
  printf("\n");
}

typedef unsigned int byte;

void dump_queue(Queue* que) {
  printf("Top :%08x next:%08x prev:%08x\n",
    (byte)que->top, (byte)que->top->next, (byte)que->top->prev);
  Node *current = que->top->next;
  while (current != que->top) {
    printf("Node:%08x next:%08x prev:%08x val:%d\n",
     (byte)current, (byte)current->next, (byte)current->prev, current->val);
    current = current->next;
  }
}

int enqueue(Queue* que, int val) {
  Node *node = create_node(val);
  if (node != NULL) {
    node->next = que->top->next;
    node->prev = que->top;
    que->top->next->prev = node;
    que->top->next = node;    
    return -1;
  }
  return 0;
}

int dequeue(Queue* que) {
  int r = 0;
  Node *node = que->top->prev;
  if (node != que->top) {
    r = node->val;
    que->top->prev = node->prev;
    node->prev->next = que->top;
    free(node);
  }
  return r;
}

int empty_queue(Queue* que) {
  return que->top->next == que->top;
}

void main() {
  Queue que;

  create_queue(&que);

  if (!enqueue(&que, 10)) exit(1);
  if (!enqueue(&que, 20)) exit(1);
  if (!enqueue(&que, 30)) exit(1);

  while (!empty_queue(&que)) {
    printf("%d\n", dequeue(&que));
  }

  destroy_queue(&que);
}

先入れ先出しなので、結果は以下のようになります。

10
20
30

使い方は、データを入れるのに enqueue()、取り出すのに dequeue() を使います。enqueue() でメモリを確保できない時は FALSE の値を返しています。また dequeue() でキューが空の時は、やはり 0 を返しているので、empty_queue() で空で無いことを確認してから使ってください。内部構造は dump_queue() で確認することが出来ます。

スタックもキューも仕組みは難しくないと思います。今回はリスト構造を使いましたが、他のデータ構造を利用して書くことも出来ます。

スタックは先頭は決まっているのですが、キューは出し入れに従って、アクセスする位置が進んでいくので、素直に書くとデータで一杯になる前に、いずれ最後の要素に達していしまいます。そこで最後までいったら使われていない先頭に戻って使うようにしてくださいという意味です。これは、意外と面倒なので難しいと思えば、最後まで到達したらキューを作り直すような方法でも構いません。

ヘッダ画像は、以下のものを使わせて頂きました。

https://commons.wikimedia.org/wiki/File:Data_Queue.svg

This Image was created by User:Vegpuff.If you are using the image under the creative commons share alike license please credit the photo Vegpuff/Wikipedia and include a link to this page. No explicit permission is needed from me, but an email if my work has been of help to you.If you dont want to release your work under a creative commons license, please mail me at vegpuff@gmail.com or catch me at my twitter stream for a custom license. - 投稿者自身による著作物, CC 表示-継承 3.0, https://commons.wikimedia.org/w/index.php?curid=7586271による