[ 문제 2-데크 ] 데크는 큐의 전단(front)과 후단(rear)에서 모두 삽입과 삭제가 가능한 자료구조다. 헤드 노드와 테일 노드가 없는 이중연결리스트를 사용하여 아래에 정의된 데크 함수들을 구현하시오.
◦ 초기 상태
- 주의 : 연산 수행 도중 원소가 모두 삭제되어 데크가 비는 경우에도, 아래 초기 상태가 되어야 함.
◦ 데크 연산
- add_front(deque, X) : deque의 앞에 원소 X를 추가 (주 교재의와 동일).
- add_rear(deque, X) : deque의 뒤에 원소 X를 추가 (주 교재의와 동일).
- delete_front(deque) : deque의 앞에 있는 원소를 반환한 다음 삭제 (주 교재의pop과 동일).
- delete_rear(deque) : deque의 뒤에 있는 원소를 반환한 다음 삭제 (주 교재의와 동일).
- print(deque) : deque의 모든 원소들을 전단부터 후단까지 차례로 출력.
◦ 입출력 형식:
1) 첫 번째 라인 : 연산의 개수 n
2) 두 번째 이후 라인: n개의 연산이 한 줄에 하나씩 차례로 입력됨.
- 하나의 줄에는 연산의 종류, 추가인 경우 원소가 주어짐 (원소는 양의 정수로 표기).
- 연산의 종류: 다음의 연산 이름이 대문자로 주어짐.
AF (add_front), AR (add_rear), DF (delete_front), DR (delete_rear), P (print)
※ underflow 발생 시, 화면에 underflow를 출력하고 프로그램 종료.
코드 설명
헤더 및 구조체
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int element;
typedef struct QueueNode {
element data;
struct QueueNode* prev;
struct QueueNode* next;
} QueueNode;
typedef struct {
QueueNode* front;
QueueNode* rear;
int size;
} DequeType;각각의 구조체에 대한 설명은 다음과 같습니다:
• typedef int element;: 덱에 저장될 데이터의 자료형을 정의합니다.
• typedef struct QueueNode {... } QueueNode;: 덱의 노드를 정의하는 구조체입니다.
이 구조체는 덱의 원소를 저장하는 data 필드와 이전 노드를 가리키는 prev 포인터, 다음 노드를 가리키는 next 포인터를 포함합니다.
• typedef struct { ... } DequeType;: 덱 자료구조를 정의하는 구조체입니다.
이 구조체는 덱의 전단(front)을 가리키는 front 포인터, 덱의 후단(rear)을 가리키는 rear 포인터, 그리고 현재 덱에 저장된 원소의 개수를 나타내는 size를 포함합니다.
덱은 QueueNode 구조체를 이용하여 이중 연결 리스트로 구현되어 있습니다.
이중 연결 리스트는 각각의 노드가 이전 노드와 다음 노드를 가리키는 구조를 가지고 있어서 원소의 삽입과 삭제를 효율적으로 수행할 수 있습니다.
init 함수
void init(DequeType* D) {
D->front = NULL;
D->rear = NULL;
D->size = 0;
}
이 함수는 덱(Deque) 자료구조를 초기화하는 역할을 합니다. 여기서 사용된 변수와 포인터에 대한 설명은 다음과 같습니다.
• DequeType* D: 초기화할 덱을 가리키는 포인터입니다.
함수의 기능은 다음과 같습니다:
• D->front = NULL;: 덱의 전단(front)을 NULL로 설정하여 덱이 비어있음을 나타냅니다.
• D->rear = NULL;: 덱의 후단(rear)을 NULL로 설정하여 덱이 비어있음을 나타냅니다.
• D->size = 0;: 덱의 현재 크기를 0으로 초기화합니다.
이 함수를 호출하면 덱이 비어있는 상태로 초기화됩니다.
isEmpty 함수
int isEmpty(DequeType* D) {
return D->size == 0;
}
이 함수는 덱(Deque)이 비어있는지를 확인하는 역할을 합니다. 여기서 사용된 변수와 포인터에 대한 설명은 다음과 같습니다.
• DequeType* D: 확인할 덱을 가리키는 포인터입니다.
함수의 기능은 다음과 같습니다:
• D->size == 0: 덱의 현재 크기가 0이면 덱이 비어있다는 것을 의미합니다.
따라서 이 함수는 덱이 비어있는지를 확인하여, 비어있으면 1을 반환하고 비어있지 않으면 0을 반환합니다.
add_front 함수
void add_front(DequeType* D, element e) {
QueueNode* new = (QueueNode*)malloc(sizeof(QueueNode));
new->data = e;
new->prev = NULL;
new->next = D->front;
if (isEmpty(D)) {
D->rear = new;
} else {
D->front->prev = new;
}
D->front = new;
D->size++;
}이 함수는 덱(Deque)의 전단(front)에 원소를 추가하는 기능을 수행합니다.
여기서 사용된 변수와 포인터에 대한 설명은 다음과 같습니다:
• DequeType* D: 원소를 추가할 덱을 가리키는 포인터입니다.
• element e: 덱에 추가할 원소입니다.
함수의 기능은 다음과 같습니다:
• QueueNode* new = (QueueNode*) malloc(sizeof(QueueNode));: 새로운 노드를 동적으로 할당합니다.
• new->data = e;: 새로운 노드의 데이터 필드에 원소 e를 저장합니다.
• new->prev = NULL;: 새로운 노드의 이전 노드를 NULL로 설정합니다.
• new->next = D->front;: 새로운 노드의 다음 노드를 현재 덱의 전단(front)을 가리키도록 설정합니다.
• if (isEmpty(D)) { D->rear = new; } else { D->front->prev = new; }
덱이 비어있는 경우에는 새로운 노드가 덱의 후단(rear)도 가리키도록 설정하고, 비어있지 않은 경우에는 현재 전단(front)의 이전 노드를 새로운 노드로 설정합니다.
• D->front = new;: 새로운 노드를 덱의 전단(front)으로 설정합니다.
• D->size++;: 덱의 크기를 증가시킵니다.
이 함수를 호출하면 덱의 전단에 새로운 원소가 추가됩니다.
만약 덱이 비어있는 경우에는 후단(rear)도 새로운 노드를 가리키게 됩니다.
add_rear 함수
void add_rear(DequeType* D, element e) {
QueueNode* new = (QueueNode*)malloc(sizeof(QueueNode));
new->data = e;
new->prev = D->rear;
new->next = NULL;
if (isEmpty(D)) {
D->front = new;
} else {
D->rear->next = new;
}
D->rear = new;
D->size++;
}이 함수는 덱(Deque)의 후단(rear)에 원소를 추가하는 기능을 수행합니다. 여기서 사용된 변수와 포인터에 대한 설명은 다음과 같습니다.
• DequeType* D: 원소를 추가할 덱을 가리키는 포인터입니다.
• element e: 덱에 추가할 원소입니다.
함수의 기능은 다음과 같습니다:
• QueueNode* new = (QueueNode*) malloc(sizeof(QueueNode));: 새로운 노드를 동적으로 할당합니다.
• new->data = e;: 새로운 노드의 데이터 필드에 원소 e를 저장합니다.
• new->prev = D->rear;: 새로운 노드의 이전 노드를 현재 덱의 후단(rear)을 가리키도록 설정합니다.
• new->next = NULL;: 새로운 노드의 다음 노드를 NULL로 설정합니다.
• if (isEmpty(D)) { D->front = new; } else { D->rear->next = new; }
덱이 비어있는 경우에는 새로운 노드가 덱의 전단(front)도 가리키게 되고, 비어있지 않은 경우에는 현재 후단(rear)의 다음 노드를 새로운 노드로 설정합니다.
• D->rear = new;: 새로운 노드를 덱의 후단(rear)으로 설정합니다.
• D->size++;: 덱의 크기를 증가시킵니다.
이 함수를 호출하면 덱의 후단에 새로운 원소가 추가됩니다. 만약 덱이 비어있는 경우에는 전단(front)도 새로운 노드를 가리키게 됩니다.
delete_front 함수
element delete_front(DequeType* D) {
if (isEmpty(D)) {
printf("underflow\n");
exit(EXIT_FAILURE);
}
QueueNode* del = D->front;
element val = del->data;
D->front = del->next;
if (D->front != NULL) {
D->front->prev = NULL;
} else {
D->rear = NULL;
}
free(del);
D->size--;
return val;
}이 함수는 덱(Deque)의 전단(front)에서 원소를 삭제하고 해당 원소를 반환하는 기능을 수행합니다.
여기서 사용된 변수와 포인터에 대한 설명은 다음과 같습니다:
• DequeType* D: 원소를 삭제할 덱을 가리키는 포인터입니다.
함수의 기능은 다음과 같습니다:
• if (isEmpty(D)) { printf("underflow\n"); exit(EXIT_FAILURE); }
덱이 비어있는 경우에는 언더플로우(underflow)가 발생하며, 이에 대한 메시지를 출력하고 프로그램을 종료합니다.
• QueueNode* del = D->front;:
삭제할 노드를 가리키는 포인터 del을 선언하고, 이를 덱의 전단(front)을 가리키도록 설정합니다.
• element val = del->data;: 삭제할 노드의 데이터를 변수 val에 저장합니다.
• D->front = del->next;: 덱의 전단을 삭제한 노드의 다음 노드로 설정합니다.
• if (D->front!= NULL) { D->front->prev = NULL; } else { D->rear = NULL; }
만약 덱의 전단이 NULL이 아니면, 전단의 이전 노드를 NULL로 설정합니다. 그렇지 않으면, 덱이 비어있다는 것이므로 후단(rear)도 NULL로 설정합니다.
• free(del);: 삭제할 노드를 해제합니다.
• D->size--;: 덱의 크기를 감소시킵니다.
• return val;: 삭제된 원소를 반환합니다.
이 함수를 호출하면 덱의 전단에서 원소가 삭제되고, 해당 원소의 값이 반환됩니다. 만약 덱이 비어있는 경우에는 프로그램이 종료됩니다.
delete_rear 함수
element delete_rear(DequeType* D) {
if (isEmpty(D)) {
printf("underflow\n");
exit(EXIT_FAILURE);
}
QueueNode* del = D->rear;
element val = del->data;
D->rear = del->prev;
if (D->rear != NULL) {
D->rear->next = NULL;
} else {
D->front = NULL;
}
free(del);
D->size--;
return val;
}이 코드는 덱(Deque) 자료구조에서 후단(rear)에서 원소를 삭제하는 함수를 구현한 것입니다.
여기서 사용된 변수 및 포인터에 대한 설명은 다음과 같습니다:
• DequeType* D: 원소를 삭제할 덱을 가리키는 포인터입니다.
함수의 기능은 다음과 같습니다:
• if (isEmpty(D)) { printf("underflow\n"); exit(EXIT_FAILURE); }
덱이 비어있는 경우에는 언더플로우(underflow)가 발생하며, 이에 대한 메시지를 출력하고 프로그램을 종료합니다.
• QueueNode* del = D->rear;
삭제할 노드를 가리키는 포인터 del을 선언하고, 이를 덱의 후단(rear)을 가리키도록 설정합니다.
• element val = del->data;: 삭제할 노드의 데이터를 변수 val에 저장합니다.
• D->rear = del->prev;: 덱의 후단을 삭제된 노드의 이전 노드로 설정합니다.
• if (D->rear!= NULL) { D->rear->next = NULL; } else { D->front = NULL; }
만약 덱의 후단이 NULL이 아니면, 후단의 다음 노드를 NULL로 설정합니다.
그렇지 않으면, 덱이 비어있다는 것이므로 전단(front)도 NULL로 설정합니다.
• free(del);: 삭제할 노드를 해제합니다.
• D->size--;: 덱의 크기를 감소시킵니다.
• return val;: 삭제된 원소를 반환합니다.
이 함수를 호출하면 덱의 후단에서 원소가 삭제되고, 해당 원소의 값이 반환됩니다.
만약 덱이 비어있는 경우에는 "underflow" 메시지가 출력되고 프로그램이 종료됩니다.
pri nt 함수
void print(DequeType* D) {
if (isEmpty(D)) {
printf("Deque is empty.\n");
return;
}
QueueNode* p = D->front;
while (p != NULL) {
printf(" %d", p->data);
p = p->next;
}
printf("\n");
}이 코드는 덱(Deque)의 내용을 출력하는 함수를 구현한 것입니다. 여기서 사용된 변수 및 포인터에 대한 설명은 다음과 같습니다:
• DequeType* D: 출력할 덱을 가리키는 포인터입니다.
함수의 기능은 다음과 같습니다:
1. 덱이 비어있는 경우에는 "Deque is empty."라는 메시지를 출력하고 함수를 종료합니다.
2. 덱의 전단(front)을 가리키는 포인터 p를 선언하고, 이를 덱의 전단으로 설정합니다.
3. 덱의 각 노드를 순회하면서 해당 노드의 데이터를 출력합니다.
4. 노드를 순회하기 위해 p 포인터를 사용하고, 각 노드의 데이터를 출력한 후에는 다음 노드로 이동합니다.
5. 모든 노드의 데이터를 출력한 후에는 개행 문자(\n)를 출력하여 줄을 바꿉니다.
이 함수를 호출하면 덱의 내용이 출력됩니다. 덱이 비어있는 경우에는 "Deque is empty."라는 메시지가 출력됩니다.
main 함수
int main() {
int n, e; // 연산의 개수, 원소
scanf("%d", &n); getchar(); // 개행 문자 처리
char F[5]; // 연산을 나타내는 문자열
DequeType DQ; // 데크 선언
init(&DQ); // 데크 초기화
// 연산 수행
for (int i = 0; i < n; i++) {
scanf("%s", F); // 연산 입력
if (strcmp(F, "AF") == 0) {
scanf("%d", &e); getchar();
add_front(&DQ, e);
} else if (strcmp(F, "AR") == 0) {
scanf("%d", &e); getchar();
add_rear(&DQ, e);
} else if (strcmp(F, "DF") == 0) {
delete_front(&DQ);
} else if (strcmp(F, "DR") == 0) {
delete_rear(&DQ);
} else if (strcmp(F, "P") == 0) {
print(&DQ);
}
}
return 0;
}이 코드는 사용자로부터 데크(Deque)의 연산을 입력받아 수행하는 프로그램입니다.
여기서 사용된 변수와 함수에 대한 설명은 다음과 같습니다:
• int n, e;: 연산의 개수와 원소를 저장하는 변수입니다.
• char F [5];: 연산을 나타내는 문자열을 저장하는 배열입니다.
연산의 종류에 따라 "AF", "AR", "DF", "DR", "P" 중 하나의 문자열이 저장됩니다.
• DequeType DQ;: 데크를 나타내는 구조체 변수입니다.
• init(&DQ);: 데크를 초기화하는 함수를 호출하여 데크를 비어있는 상태로 초기화합니다.
• add_front(&DQ, e);: 데크의 전단에 원소를 추가하는 함수를 호출합니다.
• add_rear(&DQ, e);: 데크의 후단에 원소를 추가하는 함수를 호출합니다.
• delete_front(&DQ);: 데크의 전단에서 원소를 삭제하는 함수를 호출합니다.
• delete_rear(&DQ);: 데크의 후단에서 원소를 삭제하는 함수를 호출합니다.
• print(&DQ);: 데크의 내용을 출력하는 함수를 호출합니다.
프로그램은 다음과 같이 작동합니다:
1. 사용자로부터 연산의 개수를 입력받습니다.
2. 연산의 개수만큼 반복하면서 연산을 입력받고 해당 연산을 수행합니다.
3. 입력받은 연산에 따라 각각의 함수를 호출하여 데크에 원소를 추가하거나 삭제하고, 데크의 내용을 출력합니다.
4. 모든 연산을 처리한 후에 프로그램이 종료됩니다.
'Datastructure > [7] 큐' 카테고리의 다른 글
| [7] 큐 ④ 덱(deque) (0) | 2024.05.22 |
|---|---|
| [7] 큐 ⑤ 응용 : 배열로 구성된 원형 큐 ADT 구현 (1) | 2024.05.22 |
| [7] 큐 ③ 연결리스트 ADT (0) | 2024.05.20 |
| [7] 큐 ② 배열 ADT (0) | 2024.05.20 |
| [7] 큐 ① (0) | 2024.03.03 |
