🎈목차
1."Queue"란 무엇인가??
2. FIFO 구조 queue의 이해
3. 일반 큐의 문제점 이해
4. arrayqueue와 listqueue간의 코드구현과 비교
🎆 1."Queue"란 무엇인가??
큐는 입구와 출구가 구분된 자료구조
선입선출 구조(FIFO : First Input First Output)
배열로 구현하거나 연결리스트로 구현할 수 있음
🎇 2. FIFO 구조 queue의 이해
<기본용어 정리>
queue size : 큐의 공간 크기(즉, 저장 가능한 데이터의 양)
put(enqueue) : 큐에 데이터를 넣는 작업
get(dequeue) : 큐에서 데이터를 꺼내는 작업
front :큐에서 첫 데이터의 위치(즉, 출력할 데이터의 위치)
rear : 큐의 마지막 데이터의 한 칸 다음 위치(즉, 입력될 데이터가 들어올 위치)
< 큐의 주요 기능>
1. 큐의 생성하기
2. 큐가 꽉 차있는지 검사
3. 큐가 완전히 비어있는가 검사
4. 큐의 데이터 추가하기
5. 큐에서 데이터 꺼내오기
7. 큐 내의 모든 데이터를 출력하기
8. 큐 소멸하기
🔑<일반 큐의 문제점>
- 배열 기반의 큐의 문제점?
지난 시간에 배열 기반의 큐를 구현하였을때 문제점을 찾지 못했는가?
대부분 아래와 같은 문제를 찾았을 것이다.
6의 용량을 가진 큐가 제거 연산을 수행할 때 마다 용량이 줄어들고 있다.
그렇다고 아래처럼 제거 연산 후 하나씩 옆으로 옮기기에는 비용이 너무 크다.
이 문제를 해결하려면 큐의 시작과 끝을 연결해서 순환할 수 있는 순환 큐(Circular Queue)로 만들면 된다.
아래처럼 순환큐를 만들면 제거연산 후에도 같은 용량을 가질 수 있다.
출처:링크텍스트
🥇<list queue의 특징>
queue을 구현하는 방법-배열(array)를 이용해서 구현하는 방법,list를 이용해서 구현하는 방법
배열을 이용한 구현에서는 queue의 size가 고정되나 queue의 size에 제한 받지 않고 데이터를 저장하기 위해서는 list로 구현하면 된다.
선입선출 구조 (FIFO: First Input First Output)를 유지하는 형태로 list queue를 구현하면 된다.
🧨4. arrayqueue와 listqueueu간의 코드구현과 비교
⚒ arrayqueue.h [1]
#pragma once
enum BOOL { FALSE, TRUE };
typedef struct _queue {
int *queue;
int size;
int front, rear;
}Queue;
BOOL createQueue(Queue * qp, int size); /* 큐 생성 및 초기화 함수 */
BOOL isQueueEmpty(const Queue *qp); /* 큐가 완전히 비어있는가 */
BOOL isQueueFull(const Queue *qp); /* 큐가 꽉차있는가 검사 */
BOOL enqueue(Queue * qp, int enqueData); /* 큐에 데이터 하나를 저장 함 */
BOOL dequeue(Queue * qp, int * dequeData); /* 큐에서 데이터 하나를 꺼냄 */
void printQueue(const Queue * qp); /* 큐 내의 모든 데이터를 출력(dequeue하는 것은 아님) */
void destroyQueue(Queue * qp); /* 큐 소멸 함수 */
arrayqueue.cpp[2]
#include <stdio.h>
#include <malloc.h>
#include "18~20강 circulator Queue.h"
/*--------------------------------------------------------------------------------------
Function name : createQueue - 원형큐 생성 및 초기화 함수
Parameters : qp - 큐 구조체의 주소
size - 큐의 크기
Returns : 생성 성공하면 TRUE, 실패하면 FALSE 리턴
--------------------------------------------------------------------------------------*/
BOOL createQueue(Queue * qp, int size)
{
if (qp == NULL) {
return FALSE;
}
qp->queue = (int*)calloc(size, sizeof(int));
if (qp->queue != NULL) {
qp->size = size;
qp->front = 0;
qp->rear = 0;
return TRUE;
}
else {
return FALSE;
}
}
/*--------------------------------------------------------------------------------------
Function name : isQueueEmpty - 큐가 비어있는가 검사
Parameters : qp - 큐 구조체의 주소
Returns : 완전히 비어있으면 TRUE 리턴, 비어있지 않으면 FALSE 리턴
--------------------------------------------------------------------------------------*/
BOOL isQueueEmpty(const Queue *qp)
{
if (qp == NULL) {//qp 포인터 NULL check
return FALSE;
}
if (qp->front == qp->rear) {//queue가 텅 비어 있으면
return TRUE;
}
else {
return FALSE;
}
}
/*--------------------------------------------------------------------------------------
Function name : isQueueFull - 큐가 꽉차있는가 검사
Parameters : qp - 큐 구조체의 주소
Returns : 꽉차 있으면 TRUE 리턴, 아니면 FALSE 리턴
--------------------------------------------------------------------------------------*/
BOOL isQueueFull(const Queue *qp)
{
if (qp == NULL) {//qp포인터 NULL check
return FALSE;
}
if (qp->front == (qp->rear + 1) % qp->size) { //queue가 꽉 차여있으면
return TRUE;
}
else {
return FALSE;
}
}
/*--------------------------------------------------------------------------------------
Function name : enqueue() - 큐에 데이터 하나를 저장함
Parameters : qp - 큐 구조체의 주소
enqueData - 큐에 저장할 데이터
Returns : 성공적으로 저장하면 TRUE, 실패하면 FALSE 리턴
--------------------------------------------------------------------------------------*/
BOOL enqueue(Queue * qp, int enqueData)
{
if (qp == NULL) {
return FALSE;
}
if (isQueueFull(qp)) {
return FALSE;
}
qp->queue[qp->rear] = enqueData;
qp->rear = (qp->rear + 1) % qp->size;
return TRUE;
}
/*--------------------------------------------------------------------------------------
Function name : dequeue() - 큐에서 데이터 하나를 꺼냄
Parameters : qp - 큐 구조체의 주소
dequeData - 꺼낸 데이터를 저장할 기억공간의 주소
Returns : 성공적으로 꺼내면 TRUE, 실패하면 FALSE 리턴
--------------------------------------------------------------------------------------*/
BOOL dequeue(Queue * qp, int * dequeData)
{
if (qp == NULL) {
return FALSE;
}
if (isQueueEmpty(qp)) {
return FALSE;
}
*dequeData = qp->queue[qp->front];
qp->front = (qp->front + 1) % qp->size;
return TRUE;
}
/*--------------------------------------------------------------------------------------
Function name : printQueue() - 큐 내의 모든 데이터를 출력 함
Parameters : qp - 큐 구조체의 주소
Returns : 없음
--------------------------------------------------------------------------------------*/
void printQueue(const Queue * qp)
{
if (qp == NULL) {//qp 포인터 NULL check
return;
}
//queue내의 모든 데이터 출력(dequeue 하면 출력되는 순서로 출력)
for (int i = qp->front; i != qp->rear; i = (i + 1) % qp->size)
{
printf("%5d\n", qp->queue[i]);
}
printf("\n");
}
/*--------------------------------------------------------------------------------------
Function name : destroyQueue() - 큐 소멸 함수
Parameters : qp - 큐 구조체의 주소
Returns : 없음
--------------------------------------------------------------------------------------*/
void destroyQueue(Queue * qp)
{
if (qp == NULL) {
return;
}
if (qp->queue != NULL) {
free(qp->queue);
}
qp->queue = NULL;
qp->size = 0;
qp->front = qp->rear = 0;
}
arrayqueue main.cpp
#include "18~20강 circulator Queue.h"
#include <stdio.h>
int menu(const char**, int);
void myFlush();
void input(Queue*);
void myDelete(Queue*);
/*--------------------------------------------------------------------------------
Function name : main()
---------------------------------------------------------------------------------*/
int main()
{
Queue que; /* 큐 관리구조체 선언*/
const char* menuList[] = { "입력하기", "삭제하기", "출력하기", "종료" }; /* 메뉴리스트*/
int menuCnt; /* 메뉴개수 저장 변수*/
int menuNum; /* 메뉴번호 저장 변수*/
createQueue(&que, 5); /* 크기가 5인 큐 생성 및 초기화*/
menuCnt = sizeof(menuList) / sizeof(menuList[0]); /* 메뉴 개수 계산 하기*/
while (1)
{
menuNum = menu(menuList, menuCnt);
if (menuNum == menuCnt) /* 종료메뉴 선택 시 반복문 탈출 하기*/
{
break;
}
switch (menuNum)
{
case 1: input(&que); break;
case 2: myDelete(&que); break;
case 3: printQueue(&que); /* queue내의 모든 데이터 출력 하기*/
}
}
destroyQueue(&que);
return 0;
}
/*--------------------------------------------------------------------------------------------------------
Function name : input() - 큐에 데이터를 반복적으로 입력 함
Parameters : qPtr - 큐의 주소
Returns : 없음
----------------------------------------------------------------------------------------------------------*/
void input(Queue* qPtr)
{
int enqueData;
while (1) {
printf("enqueue할 정수형 데이터를 입력하시오(문자 입력 시 종료) : ");
if (scanf("%d", &enqueData) != 1) { /* 문자나 EOF가 입력되면 while문을 빠져 나감*/
myFlush();
break;
}
if (!enqueue(qPtr, enqueData))
printf("enqueue 실패!!\n");
}
}
/*------------------------------------------------------------------------------------------------------------
Function name : myDelete() - 큐에 데이터를 반복적으로 꺼냄
Parameters : qPtr - 큐의 주소
Returns : 없음
------------------------------------------------------------------------------------------------------------*/
void myDelete(Queue* qPtr)
{
int i;
int cnt; /* dequeue할 횟수를 입력 받아 저장할 변수*/
int dequeData; /* dequeue한 데이터를 저장할 변수*/
int res; /* dequeue()함수의 리턴값을 저장할 변수*/
printf("Queue에서 데이터를 dequeue할 회수를 입력하시오: ");
scanf("%d", &cnt);
for (i = 0; i < cnt; i++) {
res = dequeue(qPtr, &dequeData);
if (res == 1) /* 성공적으로 get 작업을 수행 했으면*/
{
printf("dequeue 데이터: %5d\n", dequeData);
}
else
printf("dequeue 실패!\n");
}
}
/*------------------------------------------------------------------------------------------------------------
Function name : menu() - 메뉴를 출력하고 메뉴번호를 입력 받아 리턴 함
Parameters : menuLIst - 메뉴 출력할 문자열
menuCnt - 메뉴 개수
Returns : 선택된 메뉴번호
------------------------------------------------------------------------------------------------------------*/
int menu(const char** menuList, int menuCnt)
{
int i;
int menuNum = 0; /* 입력된 메뉴번호 저장 변수*/
int res; /* scanf()함수의 리턴값 저장 변수*/
for (i = 0; i < menuCnt; i++)
{
printf("%d. %s\n", i + 1, menuList[i]);
}
while (menuNum<1 || menuNum>menuCnt) /* 메뉴번호 범위의 번호가 입력시 까지 반복*/
{
printf("# 메뉴번호를 입력하세요 : ");
res = scanf("%d", &menuNum);
if (res != 1) /* 정수가 입력되지 않았으면*/
{
myFlush(); /* 입력버퍼 비우기*/
continue;
}
}
return menuNum;
}
/*------------------------------------------------------------------------------------------------------------
Function name : myFlush() - 입력버퍼 지우기
Parameters : 없음
Returns : 없음
------------------------------------------------------------------------------------------------------------*/
void myFlush()
{
while (getchar() != '\n')
{
;
}
}
<출력화면>
🛠 listqueue.h[1]
#pragma once
enum BOOL { FALSE, TRUE };
#define TRUE 1;
#define FALSE 0
typedef struct _node Node;
struct _node
{
int data;
Node *next;
};
typedef struct _queue {
Node *head;
Node *tail;
}Queue;
typedef int BOOL;
BOOL createQueue(Queue * qp); /* 큐 생성 및 초기화 함수 */
BOOL isQueueEmpty(const Queue *qp); /* 큐가 완전히 비어있는가 */
BOOL enqueue(Queue * qp, int enqueData); /* 큐에 데이터 하나를 저장 함 */
BOOL dequeue(Queue * qp, int * dequeData); /* 큐에서 데이터 하나를 꺼냄 */
void printQueue(const Queue * qp); /* 큐 내의 모든 데이터를 출력(dequeue하는 것은 아님) */
void destroyQueue(Queue * qp); /* 큐 소멸 함수 */
listqueue.cpp [2]
#include <stdio.h>
#include <malloc.h>
#include "21강 list Queue.h"
/*--------------------------------------------------------------------------------------
Function name : createQueue - 큐 초기화 함수
Parameters : qp - 큐 구조체의 주소
Returns : 성공 - TRUE / 실패 - FALSE
--------------------------------------------------------------------------------------*/
BOOL createQueue(Queue * qp)
{
if (qp == NULL) {//qp 포인터 NULL check
return FALSE ;
}
qp->head = (Node*)calloc(1, sizeof(Node));//head mode 생성
if (qp->head == NULL) {
return FALSE;
}
qp->tail = (Node*)calloc(1, sizeof(Node));//tail node 생성
if (qp->tail == NULL) {
free(qp->head);
return FALSE;
}
else {//head node가 tail node를 tail node가 tail node를 가르키게 함
qp->head->next = qp->tail;
qp->tail->next = qp->tail;
return TRUE;
}
}
/*--------------------------------------------------------------------------------------
Function name : isQueueEmpty - 큐가 비어있는가 검사
Parameters : qp - 큐 구조체의 주소
Returns : 완전히 비어있으면 TRUE 리턴, 비어있지 않으면 FALSE 리턴
--------------------------------------------------------------------------------------*/
BOOL isQueueEmpty(const Queue *qp)
{
if (qp == NULL) {
return FALSE;
}
if (qp->head->next == qp->tail) {
return TRUE;
}
else {
return FALSE;
}
}
/*--------------------------------------------------------------------------------------
Function name : enqueue - 큐에 데이터 하나를 저장함
Parameters : qp - 큐 구조체의 주소
enqueData - 큐에 저장할 데이터
Returns : 성공적으로 저장하면 TRUE, 실패하면 FALSE 리턴
--------------------------------------------------------------------------------------*/
BOOL enqueue(Queue * qp, int enqueData)
{
Node*cur;
if (qp == NULL) {
return FALSE;
}
Node*np = (Node*)(calloc(1, sizeof (Node)));
if (np == NULL) {
return FALSE;
}
cur = qp->head;
while (cur->next != qp->tail)
cur = cur->next;
cur->next = np;
np->next = qp->tail;
np->data = enqueData;
return TRUE;
}
/*--------------------------------------------------------------------------------------
Function name : dequeue - 큐에서 데이터 하나를 꺼냄
Parameters : qp - 큐 구조체의 주소
dequeData - 꺼낸 데이터를 저장할 기억공간의 주소
Returns : 성공적으로 꺼내면 TRUE, 실패하면 FALSE 리턴
--------------------------------------------------------------------------------------*/
BOOL dequeue(Queue * qp, int * dequeData)
{
Node*cur;
if (qp == NULL) {
return FALSE;
}
if (isQueueEmpty(qp)) {
return FALSE;
}
else {
*dequeData = qp->head->next->data;
cur = qp->head->next;
qp->head->next = qp->head->next->next;
free(cur);
return TRUE;
}
}
/*--------------------------------------------------------------------------------------
Function name : printQueue - 큐 내의 모든 데이터를 출력 함
Parameters : qp - 큐 구조체의 주소
Returns : 없음
--------------------------------------------------------------------------------------*/
void printQueue(const Queue * qp)
{
Node*curp;
if (qp == NULL) {
return;
}
printf("큐 :");
curp = qp->head->next;
while (curp != qp->tail) {
printf(" %d-", curp->data);
curp = curp->next;
}
printf("\n\n");
}
/*--------------------------------------------------------------------------------------
Function name : destroyQueue - 큐 소멸 함수
Parameters : qp - 큐 구조체의 주소
Returns : 없음
--------------------------------------------------------------------------------------*/
void destroyQueue(Queue * qp)
{
Node*curp;
if (qp == NULL) {
return;
}
curp = qp->head->next;
while (curp != qp->tail) {
qp->head->next = qp->head->next->next;
free(curp);
curp = qp->head->next;
}
free(qp->head);
free(qp->tail);
qp->head = qp->tail = NULL;
printf("BYE");
}main.cpp [3]
#define _CRT_SECURE_NO_WARNINGS
#include "21강 list Queue.h"
#include <stdio.h>
int menu(const char **, int);
void myFlush();
void input(Queue *);
void myDelete(Queue *);
/*--------------------------------------------------------------------------------
Function name : main()
--------------------------------------------------------------------------------*/
int main()
{
Queue que; /* 큐 관리구조체 선언*/
const char *menuList[] = { "입력하기", "삭제하기", "출력하기", "종료" }; /* 메뉴리스트*/
int menuCnt; /* 메뉴개수 저장 변수*/
int menuNum; /* 메뉴번호 저장 변수*/
createQueue(&que); /* 큐 생성 및 초기화*/
menuCnt = sizeof(menuList) / sizeof(menuList[0]); /* 메뉴 개수 계산 하기*/
while (1)
{
menuNum = menu(menuList, menuCnt);
if (menuNum == menuCnt) /* 종료메뉴 선택 시 반복문 탈출 하기*/
{
break;
}
switch (menuNum)
{
case 1: input(&que); break;
case 2: myDelete(&que); break;
case 3: printQueue(&que); /* queue내의 모든 데이터 출력 하기*/
}
}
destroyQueue(&que);
return 0;
}
/*--------------------------------------------------------------------------------------------------------
Function name : input() - 큐에 데이터를 반복적으로 입력 함
Parameters : qPtr - 큐의 주소
Returns : 없음
----------------------------------------------------------------------------------------------------------*/
void input(Queue *qPtr)
{
int enqueData;
printf("enqueue할 정수형 데이터를 입력하시오(문자 입력 시 종료) : ");
if (scanf("%d", &enqueData) != 1) { /* 문자나 EOF가 입력되면 while문을 빠져 나감*/
myFlush();
}
if (!enqueue(qPtr, enqueData))
printf("enqueue 실패!!\n");
printQueue(qPtr);
}
/*------------------------------------------------------------------------------------------------------------
Function name : myDelete() - 큐에 데이터를 반복적으로 꺼냄
Parameters : qPtr - 큐의 주소
Returns : 없음
------------------------------------------------------------------------------------------------------------*/
void myDelete(Queue *qPtr)
{
int i;
int cnt; /* dequeue할 횟수를 입력 받아 저장할 변수*/
int dequeData; /* dequeue한 데이터를 저장할 변수*/
int res; /* dequeue()함수의 리턴값을 저장할 변수*/
//printf("Queue에서 데이터를 dequeue할 데이터를 입력하시오: ");
scanf("%d", &dequeData);
res = dequeue(qPtr, &dequeData);
if (res == 1) /* 성공적으로 get 작업을 수행 했으면*/
{
//printf("dequeue 데이터: %5d\n", dequeData);
}
else
printf("dequeue 실패!\n");
printQueue(qPtr);
}
/*------------------------------------------------------------------------------------------------------------
Function name : menu() - 메뉴를 출력하고 메뉴번호를 입력 받아 리턴 함
Parameters : menuLIst - 메뉴 출력할 문자열
menuCnt - 메뉴 개수
Returns : 선택된 메뉴번호
------------------------------------------------------------------------------------------------------------*/
int menu(const char **menuList, int menuCnt)
{
int i;
int menuNum = 0; /* 입력된 메뉴번호 저장 변수*/
int res; /* scanf()함수의 리턴값 저장 변수*/
for (i = 0; i < menuCnt; i++)
{
printf("%d. %s\n", i + 1, menuList[i]);
}
while (menuNum<1 || menuNum>menuCnt) /* 메뉴번호 범위의 번호가 입력시 까지 반복*/
{
printf("# 메뉴번호를 입력하세요 : ");
res = scanf("%d", &menuNum);
if (res != 1) /* 정수가 입력되지 않았으면*/
{
myFlush(); /* 입력버퍼 비우기*/
continue;
}
}
return menuNum;
}
/*------------------------------------------------------------------------------------------------------------
Function name : myFlush() - 입력버퍼 지우기
Parameters : 없음
Returns : 없음
------------------------------------------------------------------------------------------------------------*/
void myFlush()
{
while (getchar() != '\n')
{
;
}
}
<실행 화면>
