덱(deque)
덱(deque)은 double-ended queue의 줄임말로서 큐의 전단(front)과 후단(rear)에서 모두 삽입과 삭제가 가능한 자료 구조이다.
특징
1. 배열로도 구현이 가능하고, 연결 리스트로도 구현이 가능하다. 따라서 구현한 자료구조에 따라서 해당 자료구조의 특징을 갖는다.
2. 데이터의 맨 앞과 맨 뒤에서만 삽입, 삭제, 접근이 필요할 때 사용하는 것이 바람직하다.
| 장점 | 단점 |
| 데이터의 앞과 뒤에서만 삽입, 삭제, 접근이 이루어질때 굉장히 빠르게 동작한다. O(1) | 중간 요소를 접근하거나 중간에 삽입, 삭제가 필요한 작업이 있다면 굳이 채택할 필요가 없다. |
덱의 연산
| 시계방향으로 증가하는 함수 • delete_front • add_rear • is_full • get_front 반시계방향으로 감소하는 함수 • add_front • delete_rear |
 |
데크 ADT
데크 ADT는 임의의 데크(double-ended queue, deque)는 스택과 큐의 합체 방식으로 작동한다.
삽입과 삭제는 앞(front)과 뒤(rear)라 불리는 양쪽 끝 위치에서 이루어진다.
| addFront(x) : 요소 x를 덱의 맨 앞에 추가 addRear(x) : 요소 x를 덱의 맨 뒤에 추가 deleteFront() : 큐의 맨 앞의 요소를 삭제하고 반환 deleteRear() : 큐의 맨 뒤의 요소를 삭제하고 반환 getFront() : 큐의 맨 앞의 요소를 삭제하지 않고 반환 getRear() : 큐의 맨 뒤의 요소를 삭제하지 않고 반환 isEmpty() : 큐가 비어있으면 true 아니면 false 반환 isFull() : 큐가 가득 차 있으면 true 아니면 false 반환 size() : 큐 내의 모든 요소 개수를 반환 display() : 큐 내의 모든 요소 출력 |
 |
데크 ADT 메쏘드
주요 메쏘드
• push(e): front 위치에 원소를 삽입
• element pop(): front 위치의 원소를 삭제하여 반환
• inject(e): rear 위치에 원소를 삽입
• element eject(): rear 위치의 원소를 삭제하여 반환
보조 메쏘드
• element front(): front 위치의 원소를 반환
• element rear(): rear 위치의 원소를 반환
• integer size(): 데크에 저장된 원소의 수를 반환
• boolean isEmpty(): 데크가 비어 있는지 여부를 반환
예외
• emptyDequeException(): 비어 있는 데크로부터 삭제를 시도할 경우 발령
• fullDequeException(): 만원인 데크에 대해 삽입을 시도할 경우 발령
배열에 기초한 데크
크기 N의 배열을 원형으로 사용한다. 이때 선형배열을 사용하면 비효율적이다.
두 개의 변수를 사용하여 front와 rear 위치를 관리한다.
☑ f:front원소의첨자
☑ r:rear원소의 첨자
빈 큐를 만원 큐로부터 차별하기 위해 다음과 같은 방법을 이용한다.
1. 한 개의 노드를 저장할 공간을 예비로 지정한다.
2. 원소 개수를 기억한다.
배열에 기초한 덱의 구현
아래 링크의 방식과 유사하다.
[7] 큐 ② 배열 ADT
큐(QUEUE) : 먼저 들어온 데이터가 먼저 나가는 자료구조선입선출(FIFO: First-In First-Out) 순서를 따른다. (예) 매표소의 대기열 큐 ADT• 큐 ADT는 임의의 삽입과 삭제는 선입선출(First-In First-Out, FIF
udangtangtang-cording-oldcast1e.tistory.com
헤더 및 구조체
#include <stdio.h>
#include <stdlib.h>
typedef int element;
#define N 10
typedef struct {
element *data; // 데이터 저장 배열
int front, rear; // 포인터와 리어 변수
int size; // 배열의 사이즈
} DequeType;
void print(DequeType *Q);이 코드는 배열을 이용하여 구현된 덱(Deque) 자료구조를 정의하는 부분입니다. 덱은 양쪽 끝에서 삽입과 삭제가 가능한 자료구조로, 이 코드에서는 정적 배열을 사용하여 덱을 구현하고 있습니다.
주요 구조체와 상수는 다음과 같습니다:
DequeType: 덱을 나타내는 구조체입니다. 이 구조체는 다음과 같은 멤버를 가지고 있습니다.
▶ element *data: 데이터를 저장하는 배열입니다.
▶ int front, rear: 덱의 전단(front)과 후단(rear)을 가리키는 포인터 변수입니다.
▶ int size: 배열의 크기를 나타내는 변수입니다.
element: 덱에 저장되는 데이터의 타입을 정의하는 typedef입니다. 이 코드에서는 정수형을 사용하고 있습니다.
N: 덱의 배열 크기를 나타내는 상수입니다. 여기서는 10으로 정의되어 있습니다.
이 코드는 배열을 이용하여 덱을 구현하고 있으며, 이후에 이 구조체를 활용하여 덱의 기능을 구현할 수 있습니다.
init 함수
// 큐 초기화 함수
void init(DequeType *Q){
Q->data = (int*)malloc(sizeof(int)*Q->size);
Q->front = Q->rear = 0; // 큐의 front와 rear를 초기화
}
이 함수는 덱(Deque)을 초기화하는 함수입니다. 초기화 과정에서는 다음을 수행합니다:
동적으로 할당된 메모리를 이용하여 덱의 데이터를 저장할 배열을 생성합니다.
이 배열의 크기는 덱의 size 멤버에 저장된 값에 의해 결정됩니다.
덱의 전단(front)과 후단(rear)을 0으로 초기화합니다. 이렇게 함으로써 덱이 비어있는 상태로 초기화됩니다.
주의할 점은 Q->size가 0이 아니어야만 메모리를 할당하는 것입니다. 그렇지 않으면 메모리 할당 과정에서 문제가 발생할 수 있습니다.
덱을 초기화하는 과정은 덱을 사용하기 전에 반드시 수행되어야 하는 과정이며, 이 함수를 통해 덱을 초기화할 수 있습니다.
isEmpty / isFull함수
// 큐가 비어있는지 확인하는 함수
int isEmpty(DequeType *Q){
return (Q->front == Q->rear);
}
// 큐가 꽉 차 있는지 확인하는 함수
int isFull(DequeType *Q){
return (Q->front == (Q->rear + 1) % Q->size);
}
이 두 함수는 각각 덱(Deque)이 비어있는지와 꽉 차 있는지를 확인하는 함수입니다.
• isEmpty
▷ 이 함수는 덱이 비어있는지 확인합니다.
▷ 비어있는 경우에는 전단(front)과 후단(rear)이 같은 위치를 가리키므로 (Q->front == Q->rear)의 조건이 참이 됩니다.
• isFull
▷ 이 함수는 덱이 꽉 차 있는지 확인합니다.
▷ 꽉 차 있는 경우에는 후단(rear)가 전단(front)의 바로 뒤에 위치해야 합니다.
▷ 따라서 (Q->front == (Q->rear + 1) % Q->size)의 조건이 참이 됩니다.
이러한 함수들을 사용하여 덱의 상태를 확인할 수 있습니다.
만약 덱이 비어있는지 또는 꽉 차 있는지를 확인하고 싶을 때 이 함수들을 호출하여 확인할 수 있습니다.
add_front 함수
// 데크의 앞에 원소를 추가하는 함수
void add_front(DequeType *Q, element e){
if (isFull(Q)) {
printf("overflow "); // overflow 메시지 출력
print(Q); // 현재 큐의 상태 출력
exit(1); // 프로그램 종료
} else {
Q->data[Q->front] = e;
Q->front = (Q->front - 1 + Q->size) % Q->size; // front 이동
}
}
이 함수는 덱(Deque)의 앞에 원소를 추가하는 함수입니다.
1. 먼저, isFull(Q)를 호출하여 덱이 꽉 차 있는지 확인합니다.
2. 만약 덱이 꽉 차 있다면 오버플로우(overflow)가 발생한 것이므로 "overflow" 메시지를 출력합니다.
3. 현재 덱의 상태를 출력한 뒤 프로그램을 종료합니다.
4. 덱이 꽉 차 있지 않다면, 새로운 원소를 덱의 앞(front)에 추가합니다.
5. 이때, Q->front에 새로운 원소를 할당하고, Q->front를 앞으로 한 칸 이동시킵니다.
여기서 주의할 점은 Q->front가 배열의 인덱스이므로 배열의 범위를 벗어나지 않도록 배열의 크기에 맞게 원형으로 이동하는 것입니다.
이 함수는 덱의 앞에 원소를 추가하는 기능을 수행하며, 추가한 뒤에는 덱의 상태를 확인하여 오버플로우가 발생하지 않도록 합니다.
add_rear 함수
// 데크의 뒤에 원소를 추가하는 함수
void add_rear(DequeType *Q, element e){
if (isFull(Q)) {
printf("overflow "); // overflow 메시지 출력
print(Q); // 현재 큐의 상태 출력
exit(1); // 프로그램 종료
} else {
Q->rear = (Q->rear + 1) % Q->size; // rear 이동
Q->data[Q->rear] = e; // 데이터 삽입
}
}이 함수는 덱(Deque)의 뒤에 원소를 추가하는 함수입니다.
1. 먼저, isFull(Q)를 호출하여 덱이 꽉 차 있는지 확인합니다.
2. 만약 덱이 꽉 차 있다면 오버플로우(overflow)가 발생한 것이므로 "overflow" 메시지를 출력합니다.
3. 현재 덱의 상태를 출력한 뒤 프로그램을 종료합니다.
4. 덱이 꽉 차 있지 않다면, 덱의 후단(rear)을 다음 위치로 이동시킨 후 새로운 원소를 추가합니다.
5. Q->rear을 (Q->rear + 1) % Q->size로 업데이트하여 원형 구조를 유지합니다.
6. 그리고 그 위치에 새로운 원소를 할당합니다.
이 함수는 덱의 뒤에 원소를 추가하는 기능을 수행하며, 추가한 뒤에는 덱의 상태를 확인하여 오버플로우가 발생하지 않도록 합니다.
delete_front 함수
// 데크의 앞에서 원소를 삭제하는 함수
element delete_front(DequeType *Q){
if (isEmpty(Q)) {
printf("underflow "); // underflow 메시지 출력
exit(1); // 프로그램 종료
} else {
Q->front = (Q->front + 1) % Q->size; // front 이동
int del = Q->data[Q->front]; // 삭제된 원소 저장
Q->data[Q->front] = 0; // 삭제된 위치를 0으로 초기화
return del; // 삭제된 원소 반환
}
}
이 함수는 덱(Deque)의 앞에서 원소를 삭제하는 함수입니다.
1. 먼저, isEmpty(Q)를 호출하여 덱이 비어있는지 확인합니다.
2. 만약 덱이 비어있다면 언더플로우(underflow)가 발생한 것이므로 "underflow" 메시지를 출력하고 프로그램을 종료합니다.
3. 덱이 비어있지 않다면, 덱의 전단(front)을 다음 위치로 이동시킵니다.
4. Q->front를 (Q->front + 1) % Q->size로 업데이트하여 원형 구조를 유지합니다.
5. 삭제된 원소를 저장한 후, 해당 위치를 0으로 초기화합니다. 이는 삭제된 위치를 비우는 작업입니다.
6. 마지막으로 삭제된 원소를 반환합니다.
이 함수는 덱의 앞에서 원소를 삭제하는 기능을 수행하며, 삭제한 원소를 반환합니다.
만약 덱이 비어있을 경우에는 언더플로우가 발생하여 프로그램이 종료됩니다.
delete_rear 함수
// 데크의 뒤에서 원소를 삭제하는 함수
element delete_rear(DequeType *Q){
if (isEmpty(Q)) {
printf("underflow "); // underflow 메시지 출력
exit(1); // 프로그램 종료
} else {
int del = Q->data[Q->rear]; // 삭제된 원소 저장
Q->data[Q->rear] = 0; // 삭제된 위치를 0으로 초기화
Q->rear = (Q->rear - 1 + Q->size) % Q->size; // rear 이동
return del; // 삭제된 원소 반환
}
}
이 함수는 덱(Deque)의 뒤에서 원소를 삭제하는 함수입니다.
1. 먼저, isEmpty(Q)를 호출하여 덱이 비어있는지 확인합니다.
2. 만약 덱이 비어있다면 언더플로우(underflow)가 발생한 것이므로 "underflow" 메시지를 출력하고 프로그램을 종료합니다.
3. 덱이 비어있지 않다면, 덱의 후단(rear)에서 원소를 삭제합니다.
4. 삭제된 원소를 del 변수에 저장한 후, 해당 위치를 0으로 초기화합니다.
5. 그다음에는 덱의 후단(rear)을 이동시킵니다.
6. Q->rear를 (Q->rear - 1 + Q->size) % Q->size로 업데이트하여 원형 구조를 유지합니다.
7. 마지막으로 삭제된 원소를 반환합니다.
이 함수는 덱의 뒤에서 원소를 삭제하는 기능을 수행하며, 삭제한 원소를 반환합니다.
만약 덱이 비어있을 경우에는 언더플로우가 발생하여 프로그램이 종료됩니다.
pri nt 함수
// 큐의 상태를 출력하는 함수
void print(DequeType *Q){
for(int j = 0; j < Q->size; j++){
printf(" %d", Q->data[j]); // 배열의 모든 원소 출력
}
printf("\n");
}
이 함수는 덱(Deque)의 상태를 출력하는 함수입니다.
함수의 동작은 간단합니다:
1. 덱의 데이터 배열에서 모든 원소를 순회하면서 각 원소를 출력합니다. 반복문을 통해 Q->data [j]의 형태로 각 원소를 출력합니다.
2. 모든 원소를 출력한 뒤에는 개행 문자(\n)를 출력하여 줄을 바꿉니다.
3. 이 함수를 호출하면 덱의 현재 상태를 화면에 출력할 수 있습니다. 이를 통해 덱에 저장된 데이터를 확인할 수 있습니다.
main 함수
// 메인 함수
int main(){
int q, n, e; // 큐의 크기, 연산의 개수, 원소
scanf("%d", &q); // 큐의 크기 입력
scanf("%d", &n); // 연산의 개수 입력
getchar(); // 개행 문자 처리
char F; // 연산을 나타내는 문자
DequeType DQ; // 큐 선언
DQ.size = q; // 큐의 크기 설정
init(&DQ); // 큐 초기화
// 큐에 원소 삽입 전 모든 원소를 0으로 초기화
for (int i = 0; i < DQ.size; i++) {
DQ.data[i] = 0;
}
// 연산 수행
for (int i = 0; i < n; i++) {
scanf("%c", &F); // 연산 입력
getchar(); // 개행 문자 처리
switch (F) {
case 'I':
scanf("%d", &e); // 삽입할 원소 입력
getchar(); // 개행 문자 처리
add_rear(&DQ, e); // 데크의 뒤에 원소 삽입
break;
case 'D':
delete_front(&DQ); // 데크의 앞에서 원소 삭제
break;
case 'F':
scanf("%d", &e); // 삽입할 원소 입력
getchar(); // 개행 문자 처리
add_front(&DQ, e); // 데크의 앞에 원소 삽입
break;
case 'R':
delete_rear(&DQ); // 데크의 뒤에서 원소 삭제
break;
case 'P':
print(&DQ); // 큐의 상태 출력
break;
}
}
free(DQ.data); // 동적 할당된 메모리 해제
return 0;
}전체 코드
#include <stdio.h>
#include <stdlib.h>
typedef int element;
#define N 10
typedef struct {
element *data; // 데이터 저장 배열
int front, rear; // 포인터와 리어 변수
int size; // 배열의 사이즈
} DequeType;
void print(DequeType *Q);
// 큐 초기화 함수
void init(DequeType *Q){
Q->data = (int*)malloc(sizeof(int)*Q->size);
Q->front = Q->rear = 0; // 큐의 front와 rear를 초기화
}
// 큐가 비어있는지 확인하는 함수
int isEmpty(DequeType *Q){
return (Q->front == Q->rear);
}
// 큐가 꽉 차 있는지 확인하는 함수
int isFull(DequeType *Q){
return (Q->front == (Q->rear + 1) % Q->size);
}
// 데크의 앞에 원소를 추가하는 함수
void add_front(DequeType *Q, element e){
if (isFull(Q)) {
printf("overflow "); // overflow 메시지 출력
print(Q); // 현재 큐의 상태 출력
exit(1); // 프로그램 종료
} else {
Q->data[Q->front] = e;
Q->front = (Q->front - 1 + Q->size) % Q->size; // front 이동
}
}
// 데크의 뒤에 원소를 추가하는 함수
void add_rear(DequeType *Q, element e){
if (isFull(Q)) {
printf("overflow "); // overflow 메시지 출력
print(Q); // 현재 큐의 상태 출력
exit(1); // 프로그램 종료
} else {
Q->rear = (Q->rear + 1) % Q->size; // rear 이동
Q->data[Q->rear] = e; // 데이터 삽입
}
}
// 데크의 앞에서 원소를 삭제하는 함수
element delete_front(DequeType *Q){
if (isEmpty(Q)) {
printf("underflow "); // underflow 메시지 출력
exit(1); // 프로그램 종료
} else {
Q->front = (Q->front + 1) % Q->size; // front 이동
int del = Q->data[Q->front]; // 삭제된 원소 저장
Q->data[Q->front] = 0; // 삭제된 위치를 0으로 초기화
return del; // 삭제된 원소 반환
}
}
// 데크의 뒤에서 원소를 삭제하는 함수
element delete_rear(DequeType *Q){
if (isEmpty(Q)) {
printf("underflow "); // underflow 메시지 출력
exit(1); // 프로그램 종료
} else {
int del = Q->data[Q->rear]; // 삭제된 원소 저장
Q->data[Q->rear] = 0; // 삭제된 위치를 0으로 초기화
Q->rear = (Q->rear - 1 + Q->size) % Q->size; // rear 이동
return del; // 삭제된 원소 반환
}
}
// 큐의 상태를 출력하는 함수
void print(DequeType *Q){
for(int j = 0; j < Q->size; j++){
printf(" %d", Q->data[j]); // 배열의 모든 원소 출력
}
printf("\n");
}
// 메인 함수
int main(){
int q, n, e; // 큐의 크기, 연산의 개수, 원소
scanf("%d", &q); // 큐의 크기 입력
scanf("%d", &n); // 연산의 개수 입력
getchar(); // 개행 문자 처리
char F; // 연산을 나타내는 문자
DequeType DQ; // 큐 선언
DQ.size = q; // 큐의 크기 설정
init(&DQ); // 큐 초기화
// 큐에 원소 삽입 전 모든 원소를 0으로 초기화
for (int i = 0; i < DQ.size; i++) {
DQ.data[i] = 0;
}
// 연산 수행
for (int i = 0; i < n; i++) {
scanf("%c", &F); // 연산 입력
getchar(); // 개행 문자 처리
switch (F) {
case 'I':
scanf("%d", &e); // 삽입할 원소 입력
getchar(); // 개행 문자 처리
add_rear(&DQ, e); // 데크의 뒤에 원소 삽입
break;
case 'D':
delete_front(&DQ); // 데크의 앞에서 원소 삭제
break;
case 'F':
scanf("%d", &e); // 삽입할 원소 입력
getchar(); // 개행 문자 처리
add_front(&DQ, e); // 데크의 앞에 원소 삽입
break;
case 'R':
delete_rear(&DQ); // 데크의 뒤에서 원소 삭제
break;
case 'P':
print(&DQ); // 큐의 상태 출력
break;
}
}
free(DQ.data); // 동적 할당된 메모리 해제
return 0;
}연결리스트에 기초한 데크
• 이중연결리스트를 사용하여 데크 구현 가능하다.
▷ 삽입과 삭제가 특정위치에서만 수행되므로, 특별노드는 불필요하다.
• front 원소를 연결리스트의 첫 노드에, rear 원소를 끝 노드에 저장하고 각각의 노드를 f와 r로 가리키게 한다.
• 기억장소 사용은 O(n)이며, 데크 ADT의 각 작업은 O(1) 시간에 수행한다.
연결리스트에 기초한 덱의 구현
헤더 및 구조체
#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. 모든 연산을 처리한 후에 프로그램이 종료됩니다.
전체 코드
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.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;
void init(DequeType* D) {
D->front = NULL;
D->rear = NULL;
D->size = 0;
}
int isEmpty(DequeType* D) {
return D->size == 0;
}
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++;
}
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++;
}
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;
}
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;
}
void print(DequeType* D) {
if (isEmpty(D)) {
printf("Deque is empty.\n");
return;
}
QueueNode* p = D->front;
while (p != NULL) {
printf("[%c] ", p->data);
p = p->next;
}
printf("\n");
}
int main() {
int n, e; // 연산의 개수, 원소
// scanf("%d", &n); getchar(); // 개행 문자 처리
char F[5]; // 연산을 나타내는 문자열
DequeType DQ; // 데크 선언
init(&DQ); // 데크 초기화
srand(time(NULL));
printf("----------<add_front>----------\n");
for (int i = 0; i < 7; i++) add_front(&DQ, rand() % 26 + 65); print(&DQ);
printf("---------<delete_front>-------\n");
for (int i = 0; i < 3; i++) printf("[%c] is deleted from front.\n", delete_front(&DQ)); print(&DQ);
printf("-----------<add_rear>----------\n");
for (int i = 0; i < 3; i++) add_rear(&DQ, rand() % 26 + 65); print(&DQ);
printf("----------<delete_rear>-------\n");
for (int i = 0; i < 1; i++) printf("[%c] is deleted from rear.\n", delete_rear(&DQ)); print(&DQ);
printf("----------<add_front>----------\n");
for (int i = 0; i < 3; i++) add_front(&DQ, rand() % 26 + 65); print(&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);
// }
// }'Datastructure > [7] 큐' 카테고리의 다른 글
| [7] 큐 ⑥ 응용 : 연결리스트를 이용한 데크 구현 (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 |
