.. 좀 많이 늦었다.
의도치 않게 갑자기 금~일 일을 하게 됐어서 목요일 월요일은 몸 좀 쉰다고 공부를 손 놓고 있었다. 힘들었다..
지금도 매우 나른하지만, 공부를 완전 손 놔버릴순 없으니까. 이제 다시 공부 진도를 뽑아보도록 하자.
Ch 07-3 , Queue 구현 - 2 / Deque (덱)
07-3
저번에는 배열을 기반으로 Queue를 구현했었다. 이번에는 연결리스트를 기반으로 구현해보겠다.
일단 언제나 그랬듯, ADT와 여러 기능을 정의한 큐의 헤더파일을 먼저 보자.
/* LBQ.h */
#ifndef __L_B_Q_H__
#define __L_B_Q_H__
#define TRUE 1
#define FALSE 0
typedef int Data;
typedef struct _node { // List 기반 구현을 위한 노드
Data data;
struct _node *next;
} Node;
typedef struct _lQ { // 연결 리스트 큐로써의 구조체
Node *front;
Node *rear;
} LQ;
typedef LQ Queue;
void QueueInit (Queue *pq);
int QIsEmpty (Queue *pq);
void Enqueue (Queue *pq, Data data);
Data Dequeue (Queue *pq);
Data QPeek (Queue *pq);
#endif요정도다.
그러면 이 헤더파일의 ADT들의 세부적인 내용을 담은 소스파일이 필요하겠지?
주석과 함께 밑에 달아놓겠다.
/* LBQ.c */
#include <stdio.h>
#include <stdlib.h>
#include "LBQ.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;
// 새 노드의 다음에 저장된 데이터는 없으니 NULL.
newNode->data = data;
if (QIsEmpty(pq)) { // 만약 큐가 비었다면,
pq->front = newNode;
pq->rear = newNode;
// 큐의 front, rear는 새 노드를 가리킴.
} else { // 큐가 비어있지 않은 상태라면,
pq->rear->next = NULL;
pq->rear = newNode;
}
}
Data Dequeue (Queue *pq) { // 큐에 저장된 데이터를 빼냄.
Node *rnode;
Data rdata;
if (QIsEmpty(pq)) { // 큐가 비어있다면, 빼낼 데이터가 없다.
printf("ERROR\n");
exit(-1);
}
rnode = pq->front; // 큐에서 데이터를 빼는건 먼저 들어간 애를 빼야함
rdata = pq->front->data;
pq->front = pq->front->next; // front를 한 칸 뒤로 옮겨준다.
free(rnode);
return rdata;
}
Data QPeek (Queue *pq) {
if (QIsEmpty(pq)) {
printf("ERROR\n");
exit(-1);
}
return pq->front->data;
}07-4
이러한 큐는 어따 써먹냐!
이 큐는 운영체제 / 네트워크 관련 소프트웨어 구구현에 있어서 중요한 역할을 한단다.
..그렇단다.
그리고 학문 중 아예 따로 "Queuing theory (큐잉 이론)" 이라는 학문이 있다는데, 여기선 수학적으로 모델링된 결과의 확인을 위해, 특정 현상을 시뮬레이션을 한단다. 이 시뮬레이션에서 큐잉 이론이 쓰인단다.
이 목차에 대해서 구체적인 설명은 본서를 참고하는게 그냥 최고인 것 같아서 굳이 여기에 따로 복습 할 내용을 적진 않았다.
본서의 273p~277p 를 참고하자.
07-5
Deque(덱)
앞에 공부했던 애들을 돌이켜 생각해보자.
스택. 뒤로 넣고 뒤에서 뺀다. 후입선출.
큐. 뒤로 넣고 앞으로 뺀다. 선입선출.
그러면 덱은?
덱. 앞으로도 뒤로도 넣고, 앞으로도 뒤로도 뺀다.
즉, 뭐 ~입~출로 딱히 설명을 할 수가 없다. 스택과 큐의 특성을 모두 갖추고 있다.
그래서 이거는 Enqueue, Dequeue 처럼 넣고 빼는걸 두가지 과정으로 설명할 수 없고. 총 네가지로 짜야한다.
- 앞으로 넣기
- 앞에서 빼기
- 뒤로 넣기
- 뒤에서 빼기
이렇게 된다면, ADT가 어떻게 되는지 보자.
뭐 그동안 많이 본 Empty, Init 이런거는 그냥 딱 봐도 아니까 이제.. 주석 안 달겠다.
void DequeInit (Deque *pdeq);
int DQIsEmpty (Deque *pdeq);
void DQAddFirst (Deque *pdeq, Data data); // front에 넣기
void DQAddLast (Deque *pdeq, Data data); // rear에 넣기
Data DQRemoveFirst (Deque *pdeq); //front에서 빼기
Data DQRemoveLast (Deque *pdeq); //rear에서 빼기
Data DQPeekFirst (Deque *pdeq); // front에 뭐있니
Data DQPeekLast (Deque *pdeq); // rear에 뭐있니그러면 이제 헤더파일 구현.
/* Deque.h */
#ifndef __DEQUE_H__
#define __DEQUE_H__
#define TRUE 1
#define FALSE 0
typedef int Data;
typedef struct _node { // 쌍방향 연결 리스트 기반.
Data data;
struct _node *next;
struct _node *prev;
} Node;
typedef struct _deque {
Node *head;
Node *tail;
} ListDeque;
typedef ListDeque Deque;
void DequeInit (Deque *pdeq);
int DQIsEmpty (Deque *pdeq);
void DQAddFirst (Deque *pdeq, Data data);
void DQAddLast (Deque *pdeq, Data data);
Data DQRemoveFirst (Deque *pdeq);
Data DQRemoveLast (Deque *pdeq);
Data DQPeekFirst (Deque *pdeq);
Data DQPeekLast (Deque *pdeq);
#endif그 다음. 소스파일!
/* Deque.c */
#include <stdio.h>
#include <stdlib.h>
#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, Data data) { // head에 새로운 데이터 저장
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->data = data;
newNode->next = pdeq->head;
// newNode의 다음은 head포인터.
if (DQIsEmpty(pdeq)) { // 만약 첫번째 데이터 저장이라면
pdeq->tail = newNode; // tail도 newNode를 가리킴
} else { // 이미 들어가있는 데이터가 있다면
pdeq->head->prev = newNode;
}
newNode->prev = NULL; // 새 노드(헤드)의 앞은 아무것도 없다
pdeq->head = newNode; // 새 노드가 head가 된다.
}
void DQAddLast (Deque *pdeq, Data data) { // tail에 새로운 데이터 저장
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->data = data;
newNode->prev = pdeq->tail; // 현재 tail의 뒤에 newNode가 있다
if (DQIsEmpty(pdeq)) { // 이 이후론 DQAddFirst와 같은 해석
pdeq->head = newNode;
} else {
pdeq->tail->next = newNode;
}
newNode->next = NULL;
pdeq->tail = newNode;
}
Data DQRemoveFirst (Deque *pdeq) { // 현재 head 데이터 뽑아내기
Node *rnode;
Data rdata;
if (DQIsEmpty(pdeq)) { // 저장된 데이터가 없으면 뽑아낼게 없어요
printf("ERROR\n");
exit(-1);
}
rnode = pdeq->head; // 삭제할 데이터의 위치
rdata = pdeq->head->data; // 삭제할 데이터의 내용
pdeq->head = pdeq->head->next; // 헤드파일을 뒤로 한칸 옮겨주고
free(rnode);
if (pdeq->head == NULL) { // 만약 저장되어있는 데이터가 없다면
pdeq->tail = NULL; // 초기값으로 돌아감
} else { // 아직 데이터가 있다면
pdeq->head->prev = NULL; // 옮겨진 head 의 앞(prev)에 아무것도 없어요
}
return rdata; // 삭제된 데이터 반환
}
Data DQRemoveLast (Deque *pdeq) { // DQRemoveFirst와 유사
Node *rnode;
Data rdata;
if (DQIsEmpty(pdeq)) {
printf("ERROR\n");
exit(-1);
}
rnode = pdeq->tail;
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;
}
Data DQPeekFirst (Deque *pdeq) {
if (DQIsEmpty(pdeq)) {
printf("ERROR\n");
exit(-1);
}
return pdeq->head->data;
}
Data DQPeekLast (Deque *pdeq) {
if (DQIsEmpty(pdeq)) {
printf("ERROR\n");
exit(-1);
}
return pdeq->tail->data;
}..여기까지.
Noob.