[資料構造]キュー
▼▼▼▼▼▼▼▼▼▼▼▼
Qとは何ですか.データ構造
ex.チケット売り場の列
キューのADTは次のようになります.
ここで注意したいのは、キューがスタックでtopを使用しているのとは異なり、キューはfront、hundを使用していることです.
挿入はキューの後ろにのみ発生し、削除はキューの前に発生します.
▼▼リニアキュー
配列を線形として使用してキューを実装し、挿入を続けるために各要素を移動する必要があります.
#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 5
typedef int element;
typedef struct { // 큐 타입
int front;
int rear;
element data[MAX_QUEUE_SIZE];
} QueueType;
// 오류 함수
void error(char *message)
{
fprintf(stderr, "%s\n", message);
exit(1);
}
void init_queue(QueueType *q)
{
q->rear = -1;
q->front = -1;
}
void queue_print(QueueType *q)
{
for (int i = 0; i<MAX_QUEUE_SIZE; i++) {
if (i <= q->front || i> q->rear)
printf(" | ");
else
printf("%d | ", q->data[i]);
}
printf("\n");
}
int is_full(QueueType *q)
{
if (q->rear == MAX_QUEUE_SIZE - 1)
return 1;
else
return 0;
}
int is_empty(QueueType *q)
{
if (q->front == q->rear)
return 1;
else
return 0;
}
void enqueue(QueueType *q, int item)
{
if (is_full(q)) {
error("큐가 포화상태입니다.");
return;
}
q->data[++(q->rear)] = item;
}
int dequeue(QueueType *q)
{
if (is_empty(q)) {
error("큐가 공백상태입니다.");
return -1;
}
int item = q->data[++(q->front)];
return item;
}
int main(void)
{
int item = 0;
QueueType q;
init_queue(&q);
enqueue(&q, 10); queue_print(&q);
enqueue(&q, 20); queue_print(&q);
enqueue(&q, 30); queue_print(&q);
item = dequeue(&q); queue_print(&q);
item = dequeue(&q); queue_print(&q);
item = dequeue(&q); queue_print(&q);
return 0;
}10 | | | | |
10 | 20 | | | |
10 | 20 | 30 | | |
| 20 | 30 | | |
| | 30 | | |
| | | | | 関数enqueueはstackの関数pushと同じであることを覚えておいてください.しかし、関数dequeueはstackの関数popとは異なり、プリアンブル演算子です.
▼▼円形行列
前列と後列の値が増加し続けると、前列が空いていても使用できず、前列が空いている場合は前に引っ張る必要がありますが、コストが高いです.
そのため、前後の概念を少し変えたのが丸いキューです.
したがって,独立して複数のデータを入れることができる可数変数count変数を作成するか,MAXSIZE−1にデータを書き込むだけで解決できる.
#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 5
typedef int element;
typedef struct { // 큐 타입
element data[MAX_QUEUE_SIZE];
int front, rear;
} QueueType;
// 오류 함수
void error(char *message)
{
fprintf(stderr, "%s\n", message);
exit(1);
}
// 공백 상태 검출 함수
void init_queue(QueueType *q)
{
q->front = q->rear = 0;
}
// 공백 상태 검출 함수
int is_empty(QueueType *q)
{
return (q->front == q->rear);
}
// 포화 상태 검출 함수
int is_full(QueueType *q)
{
return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}
// 원형큐 출력 함수
void queue_print(QueueType *q)
{
printf("QUEUE(front=%d rear=%d) = ", q->front, q->rear);
if (!is_empty(q)) {
int i = q->front;
do {
i = (i + 1) % (MAX_QUEUE_SIZE);
printf("%d | ", q->data[i]);
if (i == q->rear)
break;
} while (i != q->front);
}
printf("\n");
}
// 삽입 함수
void enqueue(QueueType *q, element item)
{
if (is_full(q))
error("큐가 포화상태입니다");
q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
q->data[q->rear] = item;
}
// 삭제 함수
element dequeue(QueueType *q)
{
if (is_empty(q))
error("큐가 공백상태입니다");
q->front = (q->front + 1) % MAX_QUEUE_SIZE;
return q->data[q->front];
}
// 삭제 함수
element peek(QueueType *q)
{
if (is_empty(q))
error("큐가 공백상태입니다");
return q->data[(q->front + 1) % MAX_QUEUE_SIZE];
}
int main(void)
{
QueueType queue;
int element;
init_queue(&queue);
printf("--데이터 추가 단계--\n");
while (!is_full(&queue))
{
printf("정수를 입력하시오: ");
scanf("%d", &element);
enqueue(&queue, element);
queue_print(&queue);
}
printf("큐는 포화상태입니다.\n\n");
printf("--데이터 삭제 단계--\n");
while (!is_empty(&queue))
{
element = dequeue(&queue);
printf("꺼내진 정수: %d \n", element);
queue_print(&queue);
}
printf("큐는 공백상태입니다.\n");
return 0;
}ここで注意すべき点は,飽和状態ではcount変数は単独ではなくMAXSIZE−1を用いるのでq->hut+1を覚えておくことである.
また、円形キューですので、挿入アルゴリズムと削除アルゴリズムで%MAX QUE SIZEを計算することを覚えておいてください.
▼▼dek（Deque）
インデックスとは?キューのフロントエンド(フロント)とバックエンド(バックエンド)から挿入および削除できるキュー
両端キューの略
DEXのADTは次のようになります.
#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 5
typedef int element;
typedef struct { // 큐 타입
element data[MAX_QUEUE_SIZE];
int front, rear;
} DequeType;
// 오류 함수
void error(char *message)
{
fprintf(stderr, "%s\n", message);
exit(1);
}
// 초기화
void init_deque(DequeType *q)
{
q->front = q->rear = 0;
}
// 공백 상태 검출 함수
int is_empty(DequeType *q)
{
return (q->front == q->rear);
}
// 포화 상태 검출 함수
int is_full(DequeType *q)
{
return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}
// 원형큐 출력 함수
void deque_print(DequeType *q)
{
printf("DEQUE(front=%d rear=%d) = ", q->front, q->rear);
if (!is_empty(q)) {
int i = q->front;
do {
i = (i + 1) % (MAX_QUEUE_SIZE);
printf("%d | ", q->data[i]);
if (i == q->rear)
break;
} while (i != q->front);
}
printf("\n");
}
// 삽입 함수
void add_rear(DequeType *q, element item)
{
if (is_full(q))
error("큐가 포화상태입니다");
q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
q->data[q->rear] = item;
}
// 삭제 함수
element delete_front(DequeType *q)
{
if (is_empty(q))
error("큐가 공백상태입니다");
q->front = (q->front + 1) % MAX_QUEUE_SIZE;
return q->data[q->front];
}
element get_front(DequeType *q)
{
if (is_empty(q))
error("큐가 공백상태입니다");
return q->data[(q->front + 1) % MAX_QUEUE_SIZE];
}
// 삽입 함수
void add_front(DequeType *q, element val)
{
if (is_full(q))
error("큐가 포화상태입니다");
q->data[q->front] = val;
q->front = (q->front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
}
// 삭제 함수
element delete_rear(DequeType *q)
{
int prev = q->rear;
if (is_empty(q))
error("큐가 공백상태입니다");
q->rear = (q->rear - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
return q->data[prev];
}
element get_rear(DequeType *q)
{
if (is_empty(q))
error("큐가 공백상태입니다");
return q->data[q->rear];
}
int main(void)
{
DequeType queue;
init_deque(&queue);
for (int i = 0; i < 3; i++) {
add_front(&queue, i);
deque_print(&queue);
}
for (int i = 0; i < 3; i++) {
delete_rear(&queue);
deque_print(&queue);
}
return 0;
}DEQUE(front=4 rear=0) = 0 |
DEQUE(front=3 rear=0) = 1 | 0 |
DEQUE(front=2 rear=0) = 2 | 1 | 0 |
DEQUE(front=2 rear=4) = 2 | 1 |
DEQUE(front=2 rear=3) = 2 |
DEQUE(front=2 rear=2) = Reference
この問題について([資料構造]キュー), 我々は、より多くの情報をここで見つけました https://velog.io/@eunsung-dev/자료구조-큐テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol