[CS50] week5 - Data structures part3

初めに

前回の続きです。

双方向リスト（Doubly-linked list）

挿入（Insertion）

先頭のノードpreviousと最後のノードのnextはNULLを指す。

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

typedef struct Node
{
  int data;
  struct Node *previous;
  struct Node *next;
} demoNode;

int getSize(demoNode *node)
{
  int size = 0;
  while (node != NULL)
  {
    size++;
    node = node->next;
  }
  return size;
}

void display(demoNode *node)
{
  demoNode *end = NULL;
  printf("Print list in forward direction: ");
  while (node != NULL)
  {
    printf("%d ", node->data);
    end = node;
    node = node->next;
  }

  printf("\nPrint list in backward direction: ");
  while (end != NULL)
  {
    printf("%d ", end->data);
    end = end->previous;
  }
  printf("\n");
}

void insertStart(demoNode **head, int data)
{
  demoNode *newNode = (demoNode *)malloc(sizeof(demoNode));
  newNode->data = data;
  newNode->next = *head;
  newNode->previous = NULL;

  if (*head != NULL)
  {
    (*head)->previous = newNode;
  }
  *head = newNode;
}

void insertLast(demoNode **head, int data)
{
  demoNode *newNode = (demoNode *)malloc(sizeof(demoNode));
  newNode->data = data;
  newNode->next = NULL;

  if (*head == NULL)
  {
    *head = newNode;
    newNode->previous = NULL;
    return;
  }

  demoNode *temp = *head;
  while (temp->next != NULL)
  {
    temp = temp->next;
  }
  temp->next = newNode;
  newNode->previous = temp;
}

void insertPosition(int position, int data, demoNode **head)
{
  int size = getSize(*head);

  if (position < 0 || position > size)
  {
    printf("%d is not a valid position\n", position);
    return;
  }

  if (position == 0)
  {
    insertStart(head, data);
  }
  else if (position == size)
  {
    insertLast(head, data);
  }
  else
  {
    demoNode *current = *head;
    demoNode *newNode = (demoNode *)malloc(sizeof(demoNode));
    newNode->data = data;
    newNode->next = NULL;

    while (--position)
    {
      current = current->next;
    }

    demoNode *tempNext = current->next;
    newNode->next = current->next;
    newNode->previous = current;
    current->next = newNode;
    tempNext->previous = newNode;
  }
}

int main(void)
{
  demoNode *head = NULL;
  insertStart(&head, 1);
  insertStart(&head, 2);
  insertStart(&head, 3);
  display(head);

  insertLast(&head, 5);
  insertLast(&head, 6);
  insertLast(&head, 7);
  display(head);

  insertPosition(5, 50, &head);
  display(head);

  return 0;
}
// Print list in forward direction: 3 2 1
// Print list in backward direction: 1 2 3

// Print list in forward direction: 3 2 1 5 6 7
// Print list in backward direction: 7 6 5 1 2 3

// Print list in forward direction: 3 2 1 5 6 50 7
// Print list in backward direction: 7 50 6 5 1 2 3

削除（Deletion）

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

typedef struct Node
{
  int data;
  struct Node *previous;
  struct Node *next;
} demoNode;

int getSize(demoNode *head)
{
  int size = 0;
  demoNode *temp = head;
  while (temp)
  {
    temp = temp->next;
    size++;
  }
  return size;
}

void display(demoNode *node)
{
  demoNode *end = NULL;

  printf("Print list in forward direction: ");
  while (node != NULL)
  {
    printf("%d ", node->data);
    end = node;
    node = node->next;
  }

  printf("\nPrint list in backward direction: ");
  while (end != NULL)
  {
    printf("%d ", end->data);
    end = end->previous;
  }
  printf("\n");
}

void insert(demoNode **head, int data)
{
  demoNode *newNode = (demoNode *)malloc(sizeof(demoNode));
  newNode->data = data;
  newNode->next = *head;
  newNode->previous = NULL;

  if (*head != NULL)
  {
    (*head)->previous = newNode;
  }
  *head = newNode;
}

void deleteFront(demoNode **head)
{
  demoNode *temp = *head;

  if (*head == NULL)
  {
    printf("linked list is empty\n");
    return;
  }

  if (temp->next == NULL)
  {
    printf("%d deleted, linked list is empty", temp->data);
    *head = NULL;
    return;
  }

  *head = (*head)->next;
  (*head)->previous = NULL;
  printf("%d deleted\n", temp->data);
  free(temp);
}

void deleteEnd(demoNode **head)
{
  demoNode *temp = *head;

  if (*head == NULL)
  {
    printf("Linked list is empty\n");
    return;
  }

  if (temp->next == NULL)
  {
    printf("%d deleted\n", temp->data);
    *head = NULL;
    return;
  }

  // traverse to the last node
  while (temp->next != NULL)
  {
    temp = temp->next;
  }
  // store the previous node
  demoNode *secondToLast = temp->previous;
  secondToLast->next = NULL;
  printf("%d deleted\n", temp->data);
  free(temp);
}

void deleteNth(demoNode **head, int nth)
{
  int size = getSize(*head);

  if (nth < 1 || nth > size)
  {
    printf("%d is not a valid position\n", nth);
    return;
  }

  if (nth == 1)
  {
    deleteFront(head);
    return;
  }

  if (nth == size)
  {
    deleteEnd(head);
    return;
  }

  demoNode *temp = *head;
  // traverse
  while (--nth)
  {
    temp = temp->next;
  }
  demoNode *previousNode = temp->previous;
  demoNode *nextNode = temp->next;
  // skip over temp(current) node
  previousNode->next = temp->next;
  nextNode->previous = temp->previous;

  printf("%d deleted\n", temp->data);
  free(temp);
}

int main(void)
{
  demoNode *head = NULL;
  insert(&head, 1);
  insert(&head, 2);
  insert(&head, 3);
  insert(&head, 4);
  insert(&head, 5);
  display(head);

  deleteFront(&head);
  display(head);

  deleteEnd(&head);
  display(head);

  deleteNth(&head, 3);
  display(head);

  return 0;
}
// Print list in forward direction: 5 4 3 2 1
// Print list in backward direction: 1 2 3 4 5
// 5 deleted
// Print list in forward direction: 4 3 2 1
// Print list in backward direction: 1 2 3 4
// 1 deleted
// Print list in forward direction: 4 3 2
// Print list in backward direction: 2 3 4
// 2 deleted
// Print list in forward direction: 4 3
// Print list in backward direction: 3 4

スタック（Stack）

• 後入先出（Last In First Out、LIFO）
• メソッドのイメージ：
  • push()：縦方向に上からデータを格納する。
  • pop()：縦方向に上からデータを取り出しする。
  • top()/peak()：現在最上位にあるデータを見つける。
  • isEmpty()：空であるかどうか中身を確認。空っぽになったスタックはtop = -1で表す。

配列への応用（As an array）

• create()：メモリを確保。
• isFull()：中身にデータがあるかどうかを確認。
• isEmpty()：スタックが満たされてるかどうか確認。
• push()：左から右へデータを格納する。
• pop()：一番新しいインデックスのデータを取り出す。
• peek()：一番新しいデータを返す。

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

struct Stack
{
  int top;
  int maxSize;
  int *array;
};

struct Stack *create(int size)
{
  struct Stack *stack = (struct Stack *)malloc(sizeof(struct Stack));
  stack->maxSize = size;
  stack->top = -1;
  stack->array = (int *)malloc(stack->maxSize * sizeof(int));

  return stack;
}

int isFull(struct Stack *stack)
{
  if (stack->top == stack->maxSize - 1)
  {
    printf("Can not push more stack\n");
  }
  // array starts from 0
  // return true or false
  return stack->top == stack->maxSize - 1;
}

int isEmpty(struct Stack *stack)
{
  return stack->top == -1;
}

void push(struct Stack *stack, int item)
{
  if (isFull(stack))
  {
    return;
  }
  stack->array[++(stack->top)] = item;
  printf("%d had been pushed to stack\n", item);
}

int pop(struct Stack *stack)
{
  if (isEmpty(stack))
  {
    return INT_MIN; // <limits.h> // -2147483648
  }
  return stack->array[(stack->top)--];
}

int peek(struct Stack *stack)
{
  if (isEmpty(stack))
  {
    return INT_MIN;
  }
  return stack->array[stack->top];
}

int main(void)
{
  struct Stack *stack = create(10);
  push(stack, 5);
  push(stack, 20);
  push(stack, 35);

  int flag = 1;
  while (flag)
  {
    if (!isEmpty(stack))
    {
      printf("%d had been popped from stack\n", pop(stack));
    }
    else
    {
      printf("Can not pop stack anymore, stack is empty\n");
      flag = 0;
    }
  }
  return 0;
}
// 5 had been pushed to stack
// 20 had been pushed to stack
// 35 had been pushed to stack
// 35 had been popped from stack
// 20 had been popped from stack
// 5 had been popped from stack
// Can not pop stack anymore, stack is empty

連結リストへの応用（As a linked list）

• push()：リスト先頭に入れる。
• pop()：リスト先頭から取り出す。

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

struct Node
{
  int data;
  struct Node *next;
};

struct Node *head = NULL; // global variable

void push(int data)
{
  struct Node *newNode = malloc(sizeof(struct Node));
  newNode->data = data;
  newNode->next = head;
  head = newNode;
}

void pop()
{
  struct Node *temp;
  if (head == NULL)
  {
    printf("Stack is empty\n");
  }
  else
  {
    printf("%d popped\n", head->data);
    temp = head;
    head = head->next;
    free(temp);
  }
}

void display()
{
  struct Node *temp = head;
  while (temp != NULL)
  {
    printf("%d->", temp->data);
    temp = temp->next;
  }
  printf("NULL\n");
}

int main(void)
{
  push(10);
  push(20);
  push(30);
  display();

  pop();
  display();

  return 0;
}
// 30->20->10->NULL
// 30 popped
// 20->10->NULL

逆ポーランド記法（Postfix notation）とポーランド記法（Prefix notation）

• Infix notation ⇒ Postfix notation：中置記法　⇒　逆ポーランド記法

  • 運算子への処理、進行方向→
  • (3 + 4) * (1 - 2) // infix
  • 3 4 + * 1 2 -
  • 3 4 + 1 2 - *
  • 3 4 + 1 2 - *

• Infix notation ⇒ Prefix notation：中置記法　⇒　ポーランド記法

  • 運算子への処理、進行方向←
  • (1 + 5) * (2 + 3) // infix
  • + 1 5 * + 2 3
  • * + 1 5 + 2 3
  • * + 1 5 + 2 3

キュー（Queue）

• 先入先出（First In First Out、FIFO）
• メソッドのイメージ：
  • Enqueue()：横方向に左から右へデータを入れる。
  • Dequeue()：横方向に一番左から順を追ってデータを取り出す。
  • isEmpty()：中身にデータがあるかどうかを確認。
  • isFull()：キューが満たされてるかどうか確認。
• オペレーティングシステムではスケジューリング（スレッド／プロセス／データ）、あらゆる面においてこの概念がよく使われる。
• 非同期処理でもこの概念が用いられる。

配列への応用（As an array）

• enqueue()：配列の順を追って要素を入れる。
• dequeue()：要素が存在する一番古いインデックスから取り出す。

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

#define MAX 6

int intArray[MAX];
int front = 0;
int rear = -1;
int itemCount = 0;

// alway show the first element in array
int peek(void)
{
  return intArray[front];
}

bool isEmpty(void)
{
  return itemCount == 0;
}

bool isFull(void)
{
  return itemCount == MAX;
}

int size(void)
{
  return itemCount;
}

void insert(int data)
{
  if (!isFull())
  {
    // if number of elements in array is full, reset rear
    if (rear == MAX - 1)
    {
      rear = -1;
    }
    intArray[++rear] = data;
    itemCount++;
  }
  else
  {
    printf("Inserting element %d is invalid, queue is Full\n", data);
  }
}

void display(void)
{
  printf("Display elements in queue: ");
  for (int i = 0; i < MAX; i++)
  {
    printf("%d ", intArray[i]);
  }
  printf("\n");
}

int removeData(void)
{
  int data = intArray[front];
  intArray[front] = 0;
  front++;

  // if the last element is removed, reset front
  if (front == MAX)
  {
    front = 0;
  }

  itemCount--;
  return data;
}

int main(void)
{
  display();
  insert(1);
  insert(3);
  insert(5);
  insert(7);
  insert(9);
  insert(10);
  insert(15);

  display();
  printf("Element removed: %d\n", removeData());
  display();

  printf("---Clear queue---\n");
  while (!isEmpty())
  {
    printf("Element removed: %d\n", removeData());
  }
  display();

  return 0;
}
// Display elements in queue: 0 0 0 0 0 0
// Inserting element 15 is invalid, queue is Full
// Display elements in queue: 1 3 5 7 9 10
// Element removed: 1
// Display elements in queue: 0 3 5 7 9 10
// ---Clear queue---
// Element removed: 3
// Element removed: 5
// Element removed: 7
// Element removed: 9
// Element removed: 10
// Display elements in queue: 0 0 0 0 0 0
// Display elements in queue : 100 0 0 0 0 0

欠点：
一度キューを満たし、そしてキューをクリアするまで先頭に新しい要素を追加できない。

解決策：剰余%で一番古い要素のインデックスを決める

#include <stdio.h>

#define maxCapacity 5

int queue[maxCapacity];
int front = -1;
int rear = -1;
int currentSize = 0;

void enqueue(int data)
{
  if (currentSize == maxCapacity)
  {
    printf("Max size reached, %d can not enqueue\n", data);
  }
  else
  {
    if (front == -1)
    {
      currentSize = 0;
      front = 0;
      rear = maxCapacity - 1;
    }
    rear = (rear + 1) % maxCapacity;
    queue[rear] = data;
    currentSize++;
    printf("%d successfully enqueued at array index %d\n", data, rear);
  }
}

void dequeue(void)
{
  if (currentSize == 0)
  {
    printf("No elements, queue is empty\n");
  }
  else
  {
    int item = queue[front];
    front = (front + 1) % maxCapacity;
    currentSize--;

    printf("%d successfully dequeued\n", item);
    printf("The current front Value %d is at index %d\n", queue[front], front);
    queue[front - 1] = 0;
  }
}

void display(void)
{
  if (rear == -1)
  {
    printf("Queue was empty\n");
  }
  else
  {
    printf("Queue: ");
    for (int i = 0; i < maxCapacity; i++)
    {
      printf("%d ", queue[i]);
    }
  }
  printf("\n");
}

int main(void)
{
  enqueue(55);
  enqueue(13);
  enqueue(20);
  enqueue(6);
  display();

  dequeue();
  display();
  dequeue();
  display();

  enqueue(100);
  display();
  enqueue(200);
  display();
  
  dequeue();
  display();

  return 0;
}
// 55 successfully enqueued at array index 0
// 13 successfully enqueued at array index 1
// 20 successfully enqueued at array index 2
// 6 successfully enqueued at array index 3
// Queue: 55 13 20 6 0

// 55 successfully dequeued
// The current front Value 13 is at index 1
// Queue: 0 13 20 6 0
// 13 successfully dequeued
// The current front Value 20 is at index 2
// Queue: 0 0 20 6 0

// 100 successfully enqueued at array index 4
// Queue: 0 0 20 6 100
// 200 successfully enqueued at array index 0
// Queue: 200 0 20 6 10

// 20 successfully dequeued
// The current front Value 6 is at index 3
// Queue: 200 0 0 6 100

構造体への応用（As a struct）

Queue.rearに一番新しいインデックス、Queue.frontにデータが存在する一番古いインデックスを記憶させる。

スタックの後入れ先出しの概念を用いて、一度キューに入ってる全てのデータを一つずつdequeue()してスタックへpush()し、スタックのpop()で最後の要素からもう一度キューへenqueue()すれば反転したキューをゲットする。

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

#define MAX 10
struct Queue
{
  int items[MAX];
  int front;
  int rear;
};

struct Stack
{
  int items[MAX];
  int top;
};

void enqueue(struct Queue *q, int item)
{
  if (q->rear == MAX - 1)
  {
    printf("Queue overflow\n");
    return;
  }

  if (q->front == -1)
  {
    // reset front
    q->front = 0;
  }
  q->rear++;
  // rear: the current last one
  q->items[q->rear] = item;
}

int dequeue(struct Queue *q)
{
  if (q->front == -1)
  {
    printf("Queue underflow\n");
    return -1;
  }

  int item = q->items[q->front];
  // the current front one move on
  q->front++;

  // when the current last element was dequeued, front will greater than rear
  if (q->front > q->rear)
  {
    // reset rear and front
    q->rear = -1;
    q->front = -1;
  }
  return item;
}

void display(struct Queue *q)
{
  if (q->rear == -1)
  {
    printf("Queue is empty\n");
    return;
  }

  for (int i = q->front; i <= q->rear; i++)
  {
    printf("%d ", q->items[i]);
  }
  printf("\n");
}

void push(struct Stack *s, int item)
{
  if (s->top == MAX - 1)
  {
    printf("Stack overflow\n");
    return;
  }
  s->top++;
  s->items[s->top] = item;
}

int pop(struct Stack *s)
{
  if (s->top == -1)
  {
    printf("Stack underflow\n");
    return -1;
  }
  // the last one
  int item = s->items[s->top];
  s->top--;

  return item;
}

int main(void)
{
  // initialize
  // MAX is 10
  struct Queue q;
  q.front = -1;
  q.rear = -1;

  struct Stack s;
  s.top = -1;

  // do enqueue
  enqueue(&q, 1);
  enqueue(&q, 2);
  enqueue(&q, 3);
  enqueue(&q, 4);

  printf("---Queue before reversing---\n");
  display(&q);

  // note: for me, it seems like one-thread queue,
  // each queue carried the task(or data) itself
  // and pass to the call stack to work
  while (q.front != -1)
  {
    push(&s, dequeue(&q));
  }
  // note: of course it just the implementation for reversing
  // use pop() to pass the last one back
  while (s.top != -1)
  {
    enqueue(&q, pop(&s));
  }

  printf("---Queue after reversing---\n");
  display(&q);

  return 0;
}
// ---Queue before reversing---
// 1 2 3 4
// ---Queue after reversing---
// 4 3 2 1

慣れてない再帰の書き方とても簡潔に書かれている。いつかこの再帰を書けるようにと思って真似ってみました。

// recursion
void reverse(struct Queue *q)
{
  // termination condition
  if (q->front == -1)
  {
    return;
  }

  // solve the small problem explicitly
  int item = dequeue(q);
  // call itself
  reverse(q);
  // something has to do at the end of every recursion
  enqueue(q, item);
}

連結リストへの応用（As a linked list）

リストへの応用ではfrontとrearはグローバル変数として管理する。rearに新しく追加したノード（insertLast/insertEndとほぼ同じ概念）、frontにヘッドにあるノードを記録させる（deleteFirst/deleteStartとほぼ同じ概念）。

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

struct Node
{
  int data;
  struct Node *next;
};

struct Node *front = NULL;
struct Node *rear = NULL;

void enqueue(int data)
{
  struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
  newNode->data = data;
  newNode->next = NULL;

  if (front == NULL && rear == NULL)
  {
    // the first node
    rear = newNode;
    front = newNode;
  }
  else
  {
    // let current node next point to new node
    rear->next = newNode;
    // go on next node
    rear = newNode;
  }
}

void display(void)
{
  struct Node *temp;
  if (front == NULL && rear == NULL)
  {
    printf("Queue is empty\n");
  }
  else
  {
    temp = front;
    printf("Queue: ");
    while (temp)
    {
      printf("%d ", temp->data);
      temp = temp->next;
    }
  }
  printf("\n");
}

void dequeue(void)
{
  struct Node *temp;
  temp = front;
  if (front == NULL && rear == NULL)
  {
    printf("Queue is empty\n");
  }
  else
  {
    front = front->next;
    free(temp);
  }
}

int main(void)
{
  enqueue(1);
  enqueue(2);
  enqueue(3);
  enqueue(4);
  enqueue(5);
  display();

  dequeue();
  display();

  enqueue(100);
  display();

  return 0;
}
// Queue: 1 2 3 4 5
// Queue: 2 3 4 5
// Queue: 2 3 4 5 100

スタック二つでキューを実現する

             loop↓                         |  popStack2()
  |3|      popStack1()   | |     |1|       |       
  |2|          &         | |     |2|       |      |2|  
  |1|    pushToStack2()  | |     |3|       |      |3|  
 stack1                 stack1  stack2     |     stack2

    count--         loop↓             
                  popStack2()   
  | |     |2|          &         |3|     | |
  | |     |3|    pushToStack1()  |2|     | |
 stack1  stack2                 stack1  stack2

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

#define MAX 10

int stack1[MAX];
int stack2[MAX];

int topInStack1 = -1;
int topInStack2 = -1;
int count = 0;

void pushToStack1(int data)
{
  if (topInStack1 == MAX - 1)
  {
    printf("Stack1 is overflow\n");
    return;
  }
  else
  {
    topInStack1++;
    stack1[topInStack1] = data;
  }
}

void pushToStack2(int data)
{
  if (topInStack2 == MAX - 1)
  {
    printf("Stack2 is overflow\n");
    return;
  }
  else
  {
    topInStack2++;
    stack2[topInStack2] = data;
  }
}

int popStack1(void)
{
  if (topInStack1 == -1)
  {
    printf("Stack1 is underflow\n");
    return -1;
  }
  return stack1[topInStack1--];
}

int popStack2(void)
{
  if (topInStack2 == -1)
  {
    printf("Stack2 is underflow\n");
    return -1;
  }

  return stack2[topInStack2--];
}

void enqueue(int data)
{
  pushToStack1(data);
  count++;
}

void dequeue(void)
{
  if (topInStack1 == -1 && topInStack2 == -1)
  {
    printf("Queue is empty\n");
  }
  else
  {
    for (int i = 0; i < count; i++)
    {
      int temp = popStack1();
      pushToStack2(temp);
    }

    int dequeuedElement = popStack2();
    printf("Dequeued element %d\n", dequeuedElement);
    count--;
    for (int i = 0; i < count; i++)
    {
      int temp = popStack2();
      pushToStack1(temp);
    }
  }
}

void display(void)
{
  if (topInStack1 == -1)
  {
    printf("Queue is empty\n");
    return;
  }

  printf("Queue: \n");
  for (int i = 0; i < count; i++)
  {
    printf("%d ", stack1[i]);
  }
  printf("\n");
}

void top(void)
{
  printf("Top element of queue(stack1) is %d\n", stack1[0]);
}

int main(void)
{
  enqueue(1);
  enqueue(2);
  enqueue(3);
  enqueue(4);
  enqueue(5);
  display();

  dequeue();
  display();

  enqueue(100);
  display();

  return 0;
}
// Queue:
// 1 2 3 4 5
// Dequeued element 1
// Queue:
// 2 3 4 5
// Queue:
// 2 3 4 5 100

スケジューリング（スレッド／プロセス／データ）での応用

• Simple Queue
• Circular Queue
• Priority Queue
• Double Ended Queue (Deque)

アプリケーションでの応用

その他