[CS50] week5 - Data structures part3

# 初めに

前回の続きです。

https://www.youtube.com/watch?v=FHMPswJDCvU&list=PLhQjrBD2T381k8ul4WQ8SQ165XqY149WW&index=19

https://www.youtube.com/watch?v=hVsNqhEthOk&list=PLhQjrBD2T381k8ul4WQ8SQ165XqY149WW&index=47

https://www.youtube.com/watch?v=3TmUv1uS92s&list=PLhQjrBD2T381k8ul4WQ8SQ165XqY149WW&index=42

https://www.youtube.com/watch?v=nvzVHwrrub0&list=PLhQjrBD2T381k8ul4WQ8SQ165XqY149WW&index=25

https://www.youtube.com/watch?v=MC-iQHFdEDI&list=PLhQjrBD2T381k8ul4WQ8SQ165XqY149WW&index=50

# 双方向リスト（Doubly-linked list）
## 挿入（Insertion）
https://prepinsta.com/c-program/insertion-in-doubly-linked-list/

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

```c
#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
```
https://prepinsta.com/c-program/doubly-linked-list-node-insertion-in-the-middle/

## 削除（Deletion）
https://prepinsta.com/c-program/deletion-in-doubly-linked-list/

```c
#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）
https://prepinsta.com/data-structures/stack/

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

## 配列への応用（As an array）
https://prepinsta.com/data-structures/representation-of-a-stack/

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

```c
#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）
https://prepinsta.com/data-structures/representation-of-a-stack-as-a-linked-list/

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

```c
#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）
https://ja.wikipedia.org/wiki/%E4%B8%AD%E7%BD%AE%E8%A8%98%E6%B3%95

https://ja.wikipedia.org/wiki/%E9%80%86%E3%83%9D%E3%83%BC%E3%83%A9%E3%83%B3%E3%83%89%E8%A8%98%E6%B3%95#%E8%A8%88%E7%AE%97%E5%8B%95%E4%BD%9C%E3%81%AE%E4%BE%8B

https://ja.wikipedia.org/wiki/%E3%83%9D%E3%83%BC%E3%83%A9%E3%83%B3%E3%83%89%E8%A8%98%E6%B3%95

- 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`

https://prepinsta.com/data-structures/infix-to-postfix-conversion/

https://prepinsta.com/data-structures/infix-to-prefix-conversion/

https://prepinsta.com/data-structures/postfix-to-prefix-conversion/

# キュー（Queue）
https://prepinsta.com/data-structures/queue/

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


## 配列への応用（As an array）
https://prepinsta.com/data-structures/queue-program-and-implementation/

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

```c
#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
```
**欠点：
一度キューを満たし、そしてキューをクリアするまで先頭に新しい要素を追加できない。**

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

https://prepinsta.com/data-structures/implementation-of-queues-using-arrays/

```c
#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）

https://prepinsta.com/c-program/reverse-a-queue/

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

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

```c
#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
```
慣れてない再帰の書き方とても簡潔に書かれている。いつかこの再帰を書けるようにと思って真似ってみました。
```c
// 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）
https://prepinsta.com/c-program/implementation-of-queues-using-linked-list/

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

```c
#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
```

## スタック二つでキューを実現する
https://prepinsta.com/c-program/implementation-of-queue-using-two-stacks/

```         
             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
```

```c
#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
```

## スケジューリング（スレッド／プロセス／データ）での応用
https://prepinsta.com/data-structures/types-of-queue/

- **Simple Queue**
- **Circular Queue**
- **Priority Queue**
- **Double Ended Queue (Deque)**

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

https://prepinsta.com/application-of-queue-in-data-structure/

# その他

https://prepinsta.com/data-structures/

https://prepinsta.com/top-100-codes/