『あはは!アルゴリズム』-第2章:スタック、キュー、チェーンテーブル

キュー
コンセプト
キューは特殊な線形構造で、キューのヘッダのみを削除できます.これを「デキュー」と呼び、キューの末尾に挿入操作を行います.これを「エンキュー」と呼びます.キューに要素がない場合(head == tail)、空のキューと呼ばれます.
キューには「先進先出」(Frost In Frost Out,FIFO)の原則があります.
コード実装

struct queue {
  int data[101];
  int head;
  int tail;
};

スタック
コンセプト
スタックは、後進先出のデータ構造です.挿入と削除の操作は、一部のみに限定されます.
例を挙げて説明する
例えば、小さなバケツがあり、小さなバケツの直径は小さなボールを1つしか置くことができません.今、バケツには2、1、3番の小さなボールが順番に入っています.もし今2番のボールを出す必要があるならば、それでは先に3番のボールと1番のボールを出さなければならなくて、最後にやっと2番のボールを得ることができます.ボールを取る過程で、最初に入れた最後に出すことができますが、最後に入れたのは最初に出すことができます.
チェーンテーブル
問題を解決する
大きな波数を格納する場合、通常は配列が使用されますが、配列が柔軟でない場合があります.たとえば、次のようになります.
小さいものから大きいものまで並べ替えられた数があります.この逃げ数種に1つの数字を挿入して、得られた新しいシーケンスが小さいものから大きいものに一致するようにする必要があります.
ダイナミックストレージ
例えば、プログラムに整数10を格納し、int aを用いてメモリに領域を申請して格納するほか、動的記憶方法もある.

malloc(4);

タイプが何バイトなのか不明な場合は、sizeof()を使用して取得できます.たとえば、次のようになります.

malloc(sizeof(int));

コード実装
各ノードは2つの部分から構成されています.一部は特定の数値を格納するために使用され、もう一部は次のノードのアドレスを格納するために使用される必要がある.例:

//     
struct node {
  int data;
  struct node *next;
};

#include 
#include 

//     
struct node {
  int data;
  struct node *next;
};

void insert(struct node *head, int n) {
  struct node *p, *t;
  
  t = head;

  while (t != NULL) {
    if (t->next == NULL || t->next->data > n) {
      //                                  
      p = (struct node*)malloc(sizeof(struct node));
      p->data = n;
      p->next = t->next;
      t->next = p;
      break;
    }

    t = t->next;
  }
}

int main(void) {
  struct node *head, *p, *q, *t;
  int i, n, a;
  
  scanf("%d", &n);

  //         
  head = NULL;

  for (i = 0; i < n; i++) {
    scanf("%d", &a);

    //         ，        ，        p       
    p = (struct node *)malloc(sizeof(struct node));
    p->data = a;
    p->next = NULL;

    if (head != NULL) {
      //       ，         ，         
      q->next = p;
    } else {
      //      ，       ，       
      head = p;
    }

    //        
    // q         
    q = p;
  }

  scanf("%d", &n);

  insert(head, n);
  
  t = head;

  while (t != NULL) {
    printf("%d ", t->data);
    t = t->next;
  }

  printf("
");

  return 0;
}

アレイ実装-シミュレーションチェーンテーブル
インプリメンテーションモード
整数配列dataと整数配列rightの2つの変数を明らかにした.dataはシーケンス種の具体的な数字を格納するために使用され、rightは現在のシーケンス種の各要素の右側が配列dataに位置し、なければ0である.
コード実装

#include 
#define NUM 100

int main(void) {
  int data[NUM], right[NUM], i, n, len = 1;

  for (i = 0; i < NUM; i++) {
    data[i] = 0;
    right[i] = 0;
  }

  scanf("%d", &n);

  for (i = 1; i <= n; i++) {
    scanf("%d", &data[i]);

    right[len] = len + 1;
    len++;
  }

  //   
  scanf("%d", &data[len]);

  i = 1;

  while (i != 0) {
    if (data[right[i]] > data[len]) {
      //                    ，       
      right[len] = right[i];ight[len] = right[i];
      right[i] = len;
      break;
    }
    i = right[i];
  }

  i = 1;

  while (i != 0) {
    printf("%d ", data[i]);
    i = right[i];
  }

  printf("
");

  return 0;
}

カードゲーム-子猫釣り

#include 

//   
struct queue {
  int data[101];
  int head;
  int tail;
} q1, q2;

//  
struct stack {
  int data[101];
  int top;
} cards;

//     
int c1[101] = {2, 4, 1, 2, 5, 6};
int c2[101] = {3, 1, 3, 5, 6, 4};


//      
void play(struct queue *q1) {
  //   
  int i, flag = 0, t = q1->data[q1->head];
  q1->head++;

  //   
  for (i = 0; i < cards.top; i++) {
    if (cards.data[i] == t) {
      flag = 1;
      break;
    }
  }

  if (flag == 1) {
    //     
    while (cards.data[cards.top - 1] != t) {
      q1->data[q1->tail++] = cards.data[cards.top - 1];
      cards.top--;
    }

    q1->data[q1->tail++] = t;
  } else {
    //     
    //          
    cards.data[cards.top++] = t;
  }
}

//    

int main(void) {
  //      
  cards.top = 0;
  //      
  int i;
  q1.head = 0;
  q1.tail = 0;
  q2.head = 0;
  q2.tail = 0;
  for (i = 0; i < 6; i++) {
    q1.data[i] = c1[i];
    q1.tail++;
    q2.data[i] = c2[i];
    q2.tail++;    
  }

  while (q1.head < q1.tail && q2.head < q2.tail) {
    play(&q1);
    play(&q2);
  }

  if (q1.head == q1.tail) {
    printf("winer is q2
");
  } else {
    printf("winer is q1
");    
  }

  printf("q1:");
  for (i = q1.head; i < q1.tail; i++) {
    printf("%d ", q1.data[i]);
  }
  printf("
q2:");  
  for (i = q2.head; i < q2.tail; i++) {
    printf("%d ", q2.data[i]);
  }
  printf("
");  
  for (i = 0; i < cards.top; i++) {
    printf("%d ", cards.data[i]);
  }

  return 0;
}

かっこの一致
タイトル
「()[]{}」のみを含む文字列を1行入力し、「{[{}()]}」または「{()[]{}}」などの形が正しく一致するかどうかを判断します.明らかに上記の2つの例は正しく一致することができる.「([)]は一致しません.
コード実装

#include 
#include 

int main(void) {
  char left_d = '{';
  char left_z = '[';
  char left_x = '(';
  char right_d = '}';
  char right_z = ']';
  char right_x = ')';
  int flag = 1;
  int have_other_word = 0;
  int i;

  //   
  char que[100];
  int head = 0;
  int tail = 0;

  //  
  struct Stack {
    int s[100];
    int top;
  } stack;
  stack.top = 0;

  gets(que);

  tail = strlen(que);

  for (i = 0; i < tail; i++) {
    if (
      que[i] != left_d &&
      que[i] != left_z &&
      que[i] != left_x &&
      que[i] != right_d &&
      que[i] != right_z &&
      que[i] != right_x
    ) {
      have_other_word = 1;
      break;
    }
  }

  if (have_other_word == 0) {
    while (head < tail) {
      if (que[head] == left_d || que[head] == left_z || que[head] == left_x) {
        stack.s[stack.top] = head;    
        stack.top++;
      } else {
        if (que[head] == right_d) {
          if (que[stack.s[stack.top - 1]] == left_d) {
            stack.top--;
          } else {
            flag = 0;
          }
        }
        
        if (que[head] == right_z) {
          if (que[stack.s[stack.top - 1]] == left_z) {
            stack.top--;        
          } else {
            flag = 0;        
          }
        }

        if (que[head] == right_x) {
          if (que[stack.s[stack.top - 1]] == left_x) {
            stack.top--;        
          } else {
            flag = 0;
          }
        }
      }

      if (flag == 0) {
        break;
      }

      head++;
    }
  } else {
    flag = 0;
  }

  if (flag) {
    printf("YES
");
  } else {
    printf("NO
");
  }

  return 0;
}