データ構造#線形キュー、円形キュー、Deque-C言語

こんにちは!このレッスンでは、線形キュー、円形キュー、インデックスについて説明します.円形キューと線形キューにはインデックス機能があるため、インデックスのみを実装します.

せんけいキュー

通常、既知の1次元配列を使用するデータ構造です.front、hutを使用して、挿入と削除を実現します.

frontは最初の要素のインデックスより1つ少なく、要素を削除するときにfrontを追加します.

hureは、最後の要素のインデックスを指し、挿入する場合はhundを追加してから要素を挿入します.

リングキュー

円形キューでは、前のロールと後のロールは、線形キューで説明したのと同じです.ただし、前または後のいずれかを再割り当てする場合は、キューのサイズ値に割り当ててからキューに割り当てる必要があります.
円キューの論理モデルは円ですが、物理メモリでは線形です.サイズ外のアドレスを参照する場合は、最初のアドレスに戻ります.
現在の要素の数を表す変数が使用できない場合は、スペースを空ける必要があります.それ以外の場合、要素がいっぱいなのか空なのかは判断できません.

インデックス(Deque)

インデックスは、挿入操作と削除操作を前後に切り替えるデータ構造です.スタックとキューには演算があるため、より柔軟なデータ構造と理解できます.
インデックスと同様に、フロントエンドとバックエンドは同じ役割を果たし、ほとんどの演算は円形キューで使用されます.
異なる点は、前後に再割り当てする場合、インデックスのサイズを増やしてから割り当てる必要があります.これは、前に挿入演算を行うと、インデックスが占有するメモリアドレスから離れることがあるからです.これはこのような状況を防ぐためだ.

front = (front + 덱의 크기) % 덱의 크기
rear = (rear+ 덱의 크기) % 덱의 크기

インプリメンテーション

では、DEXをc言語で実現しましょう.

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

#define MAX_DEQUE_SIZE 5

typedef struct {
  int front;
  int rear;
  int data[MAX_DEQUE_SIZE];
} Deque;

void init_deque(Deque *q) {
  q->front = q->rear = 0;
}

int is_empty(Deque *q) {
  return (q->front == q->rear);
}

int is_full(Deque *q) {
  return (q->rear + 1) % MAX_DEQUE_SIZE == q->front;
}

void print_deque(Deque *q) {
  printf("front: %d | rear: %d\n", q->front, q->rear);
  if (is_empty(q)) {
    printf("none");
    exit(1);
  }

  int i = (q->front + 1) % MAX_DEQUE_SIZE;

  while(1) {
    printf("%d | ", q->data[i]);
    if (i == q->rear) break;
    i = (i + 1) % MAX_DEQUE_SIZE;
  }
}

void add_rear(Deque *q, int item) {
  if (is_full(q)) {
    printf("deque가 가득찼습니다. rear");
     exit(1);
  }
  q->rear = (q->rear + 1) % MAX_DEQUE_SIZE;
  q->data[q->rear] = item;
}

int delete_rear(Deque *q) {
  if (is_empty(q)) {
    printf("deque가 비었습니다. rear");
     exit(1);
  }
  int prev = q->rear;
  q->rear = (q->rear - 1 + MAX_DEQUE_SIZE) % MAX_DEQUE_SIZE;
  return q->data[prev];
}

void add_front(Deque *q, int item) {
  if (is_full(q)) {
    printf("deque가 가득찼습니다. front");
    exit(1);
  }
  q->data[q->front] = item;
  q->front = (q->front - 1 + MAX_DEQUE_SIZE) % MAX_DEQUE_SIZE;
}

int delete_front(Deque *q) {
  if (is_empty(q)) {
    printf("deque가 비었습니다. front");
    exit(1);
  }
  q->front = (q->front + 1) % MAX_DEQUE_SIZE;
  return q->data[q->front];
}

int main(void) {
  Deque deque;
  init_deque(&deque);

  add_front(&deque, 10);
  add_front(&deque, 20);
  add_front(&deque, 30);
  add_front(&deque, 40);
  printf("%d\n", delete_front(&deque));
  printf("%d\n", delete_front(&deque));
  printf("%d\n", delete_front(&deque));
  printf("%d\n", delete_front(&deque));
  add_rear(&deque, 100);
  add_rear(&deque, 200);
  add_front(&deque, 50);
  add_front(&deque, 60);
  print_deque(&deque);

  return 0;
}