More than 3 years have passed since last update.

データ構造とアルゴリズム Vol.4

Last updated at 2021-01-18Posted at 2021-01-18

Vol.4: Stack

Stack資料の構造の考え方と活用方法について学びます。
C言語を利用してStackの資料構造を直接具現できます。

Stackとは？

👌 Stackは一方に入って、一方に出てくる資料構造(Data Structure)です。
この特性から、数式計算などのアルゴリズムにおいて多方面に活用されます。
👌 Doubly Linked Listの各ノードは、前ノードと後ろノードの情報を両方とも保存しています。

基本的にpushとpopで構成されています。
PUSH:Stackにデータを入れます。
POP:Stackからデータを抜き取ります

例）

PUSH(7)-PUSH(5)-PUSH(4)-POP()-PUSH(6)-POP()

🤔 結果は？

Stackの実装

👌Stackは、配列を利用した実装方法と、接続リストを利用した実装方法に分かれます。
👌最も基本的な形態の資料構造であり、実現の難易度は低い方です。

配列を利用したStackを実現

例）実行するコードの例

//Stackの宣言
# include <stdio.h>
# include <stdlib.h>
# define SIZE 10000
# define INF 9999999 //INF = infinite
int stack[SIZE];
int top = 1; //Stackの最上段(=入り口)を意味

//Stack挿入関数
void push(int data) {
  if (top == SIZE - 1) {
    printf("Stack overflowが発生しました。\n");
  return;
  }
  stack[++top] = data;
}
//Stack抽出関数
int pop() {
  if (top == -1) {
    printf("Stack underflowが発生しました。\n");
    return -INF;
  }
  return stack[top--];
}
//Stack全体の出力関数
void show() {
  printf("--- Stackの最上段 ---\n");
  for (int i = top; i >= 0; i--) {
    printf("%d\n", stack[i]);
  }
  printf("--- Stackの最下段 ---\n");
}
//完成したStackを使用する
int main(void) {
  push(7);
  push(5);
  push(4);
  pop();
  push(6);
  pop();
  show();
  system("pause");
  
  return 0;
}

🤔 結果は？
result->

5
7
--- Stackの最下段 ---```

## Linked Listを利用したStackを実現
#### 例）実行するコードの例
```C
//Stackの宣言
# include <stdio.h>
# include <stdlib.h>
# define INF 99999999
typedef struct {
  int data;
  struct Node *next;
} Node;
typedef struct {
  Node *top;
} Stack;

//Stack挿入関数
void push(Stack *stack, int data) {
  Node *node = (Node*) malloc(sizeof(Node));
  node->data = data;
  node->next = stack->top;
  stack->top = node;
}

//Stack抽出関数
int pop(Stack *stack) {
  if (stack->top == NULL) {
    printf("Stack underflowが発生しました。\n");
    return -INF;
  }
  Node *node = stack->top;
  int data = node->data;
  stack->top = node->next;
  free(node);
  return data;
}

//Stack全体の出力関数
void show(Stack *stack) {
  Node *cur = stack->top;
  printf("--- Stackの最上段 ---\n");
  while (cur != NULL) {
    printf("%d\n", cur->data);
    cur = cur->next;
  }
  printf("--- Stackの最下段 ---\n");
}

//完成したStackを使用する
int main(void) {
  Stack stack;
  stack.top = NULL;
  show(&stack);
  push(&stack, 7);
  push(&stack, 5);
  push(&stack, 4);
  pop(&stack);
  push(&stack, 6);
  pop(&stack);
  show(&stack);
  system("pause");
  return 0;
}