큐는 스택과 함께 언급되고 비교되는 자료구조.
스택은 먼저 들어간 데이터가 나중에 나오는 구조인 반면, 큐는 먼저 들어간 데이터가 먼저 나오는 구조.
큐의 이해
우리는 하루에도 몇 번씩 줄을 선다. 대중교통을 이용할 때에도, 패스트푸드점에서 주문을 할 때에도 줄을 서는 이유는 먼저 온 사람이 먼저 서비스를 받도록 하기 위함이다.
큐는 '선입선출' 구조의 자료구조.
큐는 FIFO(First-In, First-Out) 구조의 자료구조.
뒤로 넣고 앞으로 빼는 구조.
큐의 ADT
큐의 핵심은 두 가지 연산.
enqueue - 큐에 데이터를 넣는 연산
dequeue - 큐에서 데이터를 꺼내는 연산
큐의 배열 기반 구현
원형 큐 구현
// CircularQueue.h
#ifndef __CIRCULAR_QUEUE_H__
#define __CIRCULAR_QUEUE_H__
#define TRUE 1
#define FALSE 0
#define LEN 100
typedef int Data;
typedef struct _cQueue
{
int first;
int rear;
Data queArr[LEN];
} CQueue;
typedef CQueue Queue;
void QueueInit(Queue* pq);
int QIsEmpty(Queue* pq);
void Enqueue(Queue* pq, Data data);
Data Dequeue(Queue* pq);
Data QPeek(Queue* pq);
#endif// CircularQueue.c
#include <stdio.h>
#include"CircularQueue.h"
void QueueInit(Queue* pq)
{
pq->first = 0;
pq->rear = 0;
}
int QIsEmpty(Queue* pq)
{
if (pq->first == pq->rear) return TRUE;
return FALSE;
}
int Next(int rear)
{
if (rear == LEN - 1) return 0;
return rear + 1;
}
void Enqueue(Queue* pq, Data data)
{
pq->rear = Next(pq->rear);
if (pq->rear == pq->first)
{
printf("no memory\n");
exit(-1);
}
pq->queArr[pq->rear] = data;
}
Data Dequeue(Queue* pq)
{
if (QIsEmpty(&pq))
{
printf("Empty\n");
exit(-1);
}
pq->first = Next(pq->first);
return pq->queArr[pq->first];
}
Data QPeek(Queue* pq)
{
if (QIsEmpty(&pq))
{
printf("Empty\n");
exit(-1);
}
return pq->queArr[Next(pq->first)];
}// CircularQueueMain.c
#include <stdio.h>
#include "CircularQueue.h"
int main()
{
Queue queue;
QueueInit(&queue);
Enqueue(&queue, 1); Enqueue(&queue, 2);
Enqueue(&queue, 3); Enqueue(&queue, 4);
Enqueue(&queue, 5);
while (!QIsEmpty(&queue))
{
printf("%d ", Dequeue(&queue));
}
return 0;
}출력 결과
1 2 3 4 5큐의 연결리스트 기반 구현
// ListBaseQueue.h
#ifndef __LB_QUEUE_H__
#define __LB_QUEUE_H__
#define TRUE 1
#define FALSE 0
typedef int Data;
typedef struct _node
{
Data data;
struct _node * next;
} Node;
typedef struct _lQueue
{
Node * front;
Node * rear;
} LQueue;
typedef LQueue Queue;
void QueueInit(Queue * pq);
int QIsEmpty(Queue * pq);
void Enqueue(Queue * pq, Data data);
Data Dequeue(Queue * pq);
Data QPeek(Queue * pq);
#endif// ListBaseQueue.c
#include <stdio.h>
#include <stdlib.h>
#include "ListBaseQueue.h"
void QueueInit(Queue * pq)
{
pq->front = NULL;
pq->rear = NULL;
}
int QIsEmpty(Queue * pq)
{
if(pq->front == NULL)
return TRUE;
else
return FALSE;
}
void Enqueue(Queue * pq, Data data)
{
Node * newNode = (Node*)malloc(sizeof(Node));
newNode->next = NULL;
newNode->data = data;
if(QIsEmpty(pq))
{
pq->front = newNode;
pq->rear = newNode;
}
else
{
pq->rear->next = newNode;
pq->rear = newNode;
}
}
Data Dequeue(Queue * pq)
{
Node * delNode;
Data retData;
if(QIsEmpty(pq))
{
printf("Queue Memory Error!");
exit(-1);
}
delNode = pq->front;
retData = delNode->data;
pq->front = pq->front->next;
free(delNode);
return retData;
}
Data QPeek(Queue * pq)
{
if(QIsEmpty(pq))
{
printf("Queue Memory Error!");
exit(-1);
}
return pq->front->data;
}// ListBaseQueueMain.c
#include <stdio.h>
#include "ListBaseQueue.h"
int main(void)
{
// Queue의 생성 및 초기화 ///////
Queue q;
QueueInit(&q);
// 데이터 넣기 ///////
Enqueue(&q, 1); Enqueue(&q, 2);
Enqueue(&q, 3); Enqueue(&q, 4);
Enqueue(&q, 5);
// 데이터 꺼내기 ///////
while(!QIsEmpty(&q))
printf("%d ", Dequeue(&q));
return 0;
}큐의 활용
큐는 운영체제 및 네트워크와 관련된 소프트웨어의 구현에 있어서 중요한 역할을 담당하는 자료구조.
큐잉 이론(queuing theory)이라는 학문에서는 수학적으로 모델링된 결과의 확인을 위해서 특정 현상을 '시뮬레이션(simulation)하게 되는데, 이때에도 큐는 중요한 역할을 담당.
햄버거집의 시뮬레이션 예제 코드
HamburgerSim.c
#include <stdio.h>
#include <stdlib.h> // rand, srand 함수를 사용하기 위함
#include <time.h> // time 함수를 사용하기 위함
#include "CircularQueue.h"
#define CUS_COME_TERM 15 // 고객의 주문 간격: 초 단위
#define CHE_BUR 0 // 상수: 치즈버거
#define BUL_BUR 1 // 상수: 불고기버거
#define DUB_BUR 2 // 상수: 더블버거
#define CHE_TERM 12 // 조리 시간(sec): 치즈버거
#define BUL_TERM 15 // 조리 시간(sec): 불고기버거
#define DUB_TERM 24 // 조리 시간(sec): 더블버거
int main(void)
{
int makeProc = 0;
int cheOrder = 0, bulOrder = 0, dubOrder = 0;
int sec;
Queue que;
QueueInit(&que);
srand(time(NULL));
for(sec=0; sec<3600; sec++)
{
if(sec % CUS_COME_TERM == 0)
{
switch(rand() % 3)
{
case CHE_BUR:
Enqueue(&que, CHE_TERM);
cheOrder += 1;
break;
case BUL_BUR:
Enqueue(&que, BUL_TERM);
bulOrder += 1;
break;
case DUB_BUR:
Enqueue(&que, DUB_TERM);
dubOrder += 1;
break;
}
}
if(makeProc <= 0 && !QIsEmpty(&que))
makeProc = Dequeue(&que);
makeProc--;
}
printf("Simulation Report!! \n\n");
printf("[Order Count]\n");
printf("- Cheese Burger: %d \n", cheOrder);
printf("- Bulgogi Burger: %d \n", bulOrder);
printf("- Double Burger: %d \n\n", dubOrder);
printf("※ Waiting room size: %d \n", QUE_LEN);
return 0;
}덱(Deque)의 이해와 구현
.png)
큐가 뒤로 넣고 앞으로 빼는 구조라면 덱은 앞으로도 뒤로도 넣을 수 있고, 앞으로도 뒤로도 뺄 수 있는 자료구조.
deque는 double-ended queue를 줄여서 표현한 이름.
코드 구현
// Deque.h
#ifndef DEQUE_H_
#define DEQUE_H_
#define TRUE 1
#define FALSE 0
typedef struct _node // 노드
{
int data; // 사용자에게 입력 받은 데이터를 저장
struct _node * prev; // 노드가 이전 노드를 가리킬 포인터 변수
struct _node * next; // 노드가 다음 노드를 가리킬 포인터 변수
} Node;
typedef struct _dlDque // 양방향 연결 리스트 덱
{
Node * head; // 앞 노드를 가리킬 포인터 변수
Node * tail; // 뒤 노드를 가리킬 포인터 변수
} DLDeque;
typedef DLDeque Deque;
void DequeInit(Deque * pdeq); // 덱을 초기화
int DQIsEmpty(Deque * pdeq); // 덱에 데이터가 비워져 있는지 확인
void DQAddFirst(Deque * pdeq, int data); // 덱의 앞에 노드를 추가
void DQAddLast(Deque * pdeq, int data); // 덱의 뒤에 노드를 추가
int DQRemoveFirst(Deque * pdeq); // 덱의 앞에 있는 노드를 삭제
int DQRemoveLast(Deque * pdeq); // 덱의 뒤에 있는 노드를 삭제
int DQGetFirst(Deque * pdeq); // 덱의 앞에 있는 노드의 데이터를 조회
int DQGetLast(Deque * pdeq); // 덱의 뒤에 있는 노드의 데이터를 조회
#endif// Deque.c
#include <stdio.h>
#include <stdlib.h> // malloc, free 함수를 사용하기 위함
#include "Deque.h"
// 덱을 초기화 //
void DequeInit(Deque * pdeq)
{
pdeq->head = NULL;
pdeq->tail = NULL;
}
// 덱에 데이터가 비워져 있는지 확인 //
int DQIsEmpty(Deque * pdeq)
{
if(pdeq->head == NULL)
return TRUE;
else
return FALSE;
}
// 덱의 앞에 노드를 추가 //
void DQAddFirst(Deque * pdeq, int data)
{
Node * newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = pdeq->head;
if(DQIsEmpty(pdeq))
pdeq->tail = newNode;
else
pdeq->head->prev = newNode;
newNode->prev = NULL;
pdeq->head = newNode;
}
// 덱의 뒤에 노드를 추가 //
void DQAddLast(Deque * pdeq, int data)
{
Node * newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->prev = pdeq->tail;
if(DQIsEmpty(pdeq))
pdeq->head = newNode;
else
pdeq->tail->next = newNode;
newNode->next = NULL;
pdeq->tail = newNode;
}
// 덱의 앞에 있는 노드를 삭제 //
int DQRemoveFirst(Deque * pdeq)
{
Node * rnode = pdeq->head;
int rdata;
if(DQIsEmpty(pdeq))
{
printf("Deque Memory Empty!!");
exit(-1);
}
rdata = pdeq->head->data;
pdeq->head = pdeq->head->next;
free(rnode);
if(pdeq->head == NULL)
pdeq->tail = NULL;
else
pdeq->head->prev = NULL;
return rdata;
}
// 덱의 뒤에 있는 노드를 삭제 //
int DQRemoveLast(Deque * pdeq)
{
Node * rnode = pdeq->tail;
int rdata;
if(DQIsEmpty(pdeq))
{
printf("Deque Memory Empty!!");
exit(-1);
}
rdata = pdeq->tail->data;
pdeq->tail = pdeq->tail->prev;
free(rnode);
if(pdeq->tail == NULL)
pdeq->head = NULL;
else
pdeq->tail->next = NULL;
return rdata;
}
// 덱의 앞에 있는 노드의 데이터를 조회 //
int DQGetFirst(Deque * pdeq)
{
if(DQIsEmpty(pdeq))
{
printf("Deque Memory Empty!!");
exit(-1);
}
return pdeq->head->data;
}
// 덱의 뒤에 있는 노드의 데이터를 조회 //
int DQGetLast(Deque * pdeq)
{
if(DQIsEmpty(pdeq))
{
printf("Deque Memory Empty!!");
exit(-1);
}
return pdeq->tail->data;
}// DequeMain.c
#include <stdio.h>
#include "Deque.h"
int main(void)
{
// 덱 생성 및 초기화 //
Deque deq;
DequeInit(&deq);
/* [데이터 넣기 1차] */
// 데이터 넣기(앞) //
DQAddFirst(&deq, 3); DQAddFirst(&deq, 2); DQAddFirst(&deq, 1);
// 데이터 넣기(뒤) //
DQAddLast(&deq, 4); DQAddLast(&deq, 5); DQAddLast(&deq, 6);
// 데이터 꺼내기(앞부터) //
while(!DQIsEmpty(&deq))
printf("%d ", DQRemoveFirst(&deq));
printf("\n\n");
/* [데이터 넣기 2차] */
// 데이터 넣기(앞) //
DQAddFirst(&deq, 3); DQAddFirst(&deq, 2); DQAddFirst(&deq, 1);
// 데이터 넣기(뒤) //
DQAddLast(&deq, 4); DQAddLast(&deq, 5); DQAddLast(&deq, 6);
// 데이터 꺼내기(뒤부터) //
while(!DQIsEmpty(&deq))
printf("%d ", DQRemoveLast(&deq));
return 0;
}출력 결과
1 2 3 4 5 6
6 5 4 3 2 1
댓글 없음:
댓글 쓰기