Notice
Recent Posts
Recent Comments
Link
«   2025/01   »
일 월 화 수 목 금 토
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
Tags
more
Archives
Today
Total
관리 메뉴

나의 IT일지

데큐 본문

알고리즘과 자료구조

데큐

세레프 2023. 4. 28. 10:16

 Queue는 데이터를 입력한 순서대로 데이터를 삭제하는 선출선입 자료구조로, 주로 순서대로 처리해야 하는 경우에 사용한다.  

 반대로 Stack은 최근에 입력한 데이터를 먼저 삭제하는 후출선입 자료구조로, 주로 순서를 반대로 처리해야 하는 경우에 사용된다.

  삽입 / 삭제 삽입 위치 / 삭제 위치
Queue enQueue / deQueue rear / front
Stack push / pop top / top

 이러한 Queue와 Stack 자료구조를 합쳐서 만든 자료구조가 있는데, 이 자료구조를 Deque라고 한다.

 

Deque

 Deque란 양쪽 끝에서 삽입과 삭제가 가능한 자료구조로, Queue와 Stack처럼 삽입되는 순서대로 데이터를 저장하며, 삭제한다. 단지 Queue처럼 양쪽으로 데이터를 삽입 / 삭제를 할 수 있으며, Stack처럼 한쪽에서 데이터를 삽입 / 삭제를 동시에 할 수 있다.

 이때 입출력이 어느 방향으로 진행 되냐에 따라 저장되는 순서가 바뀌게 된다. 예시로 먼저 front쪽으로 "A"가 삽입되고, 두번째로 rear쪽으로 "C"가 삽입된 뒤, 마지막으로 front쪽으로 "D"가 삽입되면 다음과 같이 데이터가 저장되어 있다.

 

 그래서 노드는 다른 노드를 양쪽에서 연결 할 수 있는 이중 연결 형식으로 구현해야 한다.

typedef struct DeQueueNodeType{
	element data;
	struct DQNode* llink;
	struct DQNode* rlink;
} DQNode;

 

typedef struct DeQueueType{
	DQNode* front, * rear;
} DQueType;

 위의 구조는 데큐가 사용하는 노드와 데큐의 정보인 front, rear를 구현해 놓은 것이다.  이때, node(노드)란 데이터를 저장하는 공간으로, 구조체를 통해 노드에 어떤 형태의 데이터를 저장할지 결정한다.

 

데큐 알고리즘

 데큐는 양쪽에서 데이터를 삽입하고 삭제하는 자료구조이기에, 데이터를 삽입, 삭제 , 출력하는 기능을 알고리즘을 통해 소스코드로 구현해야 한다. 이때 front와 rear는 삽입되는 방향에 따라 데이터가 위치하는 요소의 주소를 지정한다. 그래서 front와 rear는 노드가 생성되기 전까지, "NULL"로 구현해야 한다. 그리고 이는 해당 상태를 공백상태이기 때문이다.

DQueType* createDQue() {
	DQueType* DQ = (DQueType*)malloc(sizeof(DQueType));
	DQ->front = NULL;
	DQ->rear = NULL;
	return DQ;
}

 

  • 데이터 삽입 함수
    1. 기능 
      • 노드가 있는 경우
        1. rear 방향 :  rear에 저장된 값을 새로운 노드의 왼쪽 포인터 변수에 저장, 새로운 노드의 주소를 rear와 기존 마지막 노드에 저장
        2. front 방향 :  front에 저장된 값을 새로운 노드의 오른쪽 포인터 변수에 저장, 노드의 주소를 front와 기존 첫 노드에 저장
      • 노드가 없는 경우 : 노드의 주소에 NULL값을 저장한 후, 노드의 주소를 rear,front에 저장
    1.  
    2. 함수의 자료형 : void
    3. 매개변수 : 저장할 데이터, 노드를 연결할 데큐

알고리즘
1. 새로운 노드의 오른쪽 포인터 변수와 왼쪽 포인터 변수에 NULL값을 저장
2.노드가 없는 경우(front == NULL): 
    1. 새로운 노드의 포인터 변수에 NULL값을 저장
    2. 노드의 주소를 rear,front에 저장
3. 노드가 있을 경우
    1. front 방향으로 삽입될 경우
         1. front가 가리키는 노드의 왼쪽 포인터 변수에 새로운 노드의 주소를 저장
         2. front에 저장되어 있는 값을 새로운 노드의 오른쪽 포인터 변수에 저장
         3. front에 새로운 노드의 주소를 저장
    2. rear 방향으로 삽입될 경우
         1. rear가 가리키는 노드의 왼쪽 포인터 변수에 새로운 노드의 주소를 저장
         2. rear에 저장되어 있는 값을 새로운 노드의 오른쪽 포인터 변수에 저장
         3. rear에 새로운 노드의 주소를 저장		 
void insertFront(DQueType* DQ, element item) {
	DQNode* newNode = (DQNode*)malloc(sizeof(DQNode));
	newNode->rlink = NULL;
	newNode->llink = NULL;

	newNode->data = item;
	if (DQ->front == NULL) {
		DQ->front = newNode;
		DQ->rear = newNode;
	}
	else {
		DQ->front->llink = newNode;
		newNode->rlink = DQ->front;
		DQ->front = newNode;
	}
}

void insertRear(DQueType* DQ, element item) {
	DQNode* newNode = (DQNode*)malloc(sizeof(DQNode));
	newNode->data = item;

	newNode->rlink = NULL;
	newNode->llink = NULL;

	if (DQ->front == NULL) {
		DQ->front = newNode;
		DQ->rear = newNode;
	}
	else {
		DQ->rear->rlink = newNode;
		newNode->llink = DQ->rear;
		DQ->rear = newNode;
	}
}

 

  • 데이터 삭제 함수
    1. 기능
      • 노드가 있는 경우
        1. front 방향 :  front가 지정하는 노드의 오른쪽 포인터 변수의 값을 front에 저장
        2. rear 방향 :  rear 가 지정하는 노드의 오른쪽 포인터 변수의 값을 rear 에 저장
      • 노드가 없는 경우 : 공백상태 출력 
    2. 함수의 자료형 : 데이터의 자료형
    3. 매개변수 : 노드를 삭제할 데큐

알고리즘
1.노드가 없는 경우(front == NULL): "공백상태"를 출력
2. 노드가 있을 경우
    1. front 방향에서 삭제될 경우
         1. front가 가리키는 노드의 오른쪽 포인터 변수의 값을 front에 저장
         2. front가 가리키는 노드의 왼쪽 포인터 변수의 값을 NULL로 저장
         3. 만약 "front == NULL"이 될 경우, rear도 NULL
    2. rear 방향으로 삽입될 경우
         1. rear가 가리키는 노드의 왼쪽 포인터 변수의 값을 rear에 저장
         2. rear가 가리키는 노드의 오른쪽 포인터 변수의 값을 NULL로 저장
         3. 만약 "rear== NULL"이 될 경우, front도 NULL
 
element deleteFront(DQueType* DQ) {
	DQNode* old = DQ->front;
	element item;
	if (DQ->front == NULL) {
		printf("\n Linked deQue is empty! \n");  return;
	}
	else {
		item = old->data;
		DQ->front = DQ->front->rlink;
		DQ->front->llink = NULL;
        
		if (DQ->front == NULL) {
			DQ->front = NULL;
			DQ->rear = NULL;
		}
		free(old);
		return item;
	}
}


element deleteRear(DQueType* DQ) {
	DQNode* old = DQ->rear;
	element item;
	if (DQ->front == NULL) {
		printf("\n Linked deQue is empty! \n"); return;
	}
	else {
		item = old->data;
        DQ->rear = DQ->rear->llink;
		DQ->rear->rlink = NULL;
		if (DQ->rear == NULL) {
			DQ->front = NULL;
			DQ->rear = NULL;
		}

		free(old);
		return item;
	}
}
  • 데이터 출력 함수
    •  기능 : front부터 rear의 위치까지의 데이터 내용을 출력
알고리즘 노드에 저장되어 있는 데이터를 front부터 rear까지 출력 
void printDQ(DQueType* DQ) {
	DQNode* temp = DQ->front;
	printf("DeQue : ");
	while (temp) {
		printf("%3c", temp->data);
		temp = temp->rlink;
	}
}

 데이터 삽입, 데이터 삭제, 데이터 출력하는 함수를 구현했으며, 해당 함수들을 통해 데큐를 생성하면 다음과 같다.

#include<stdio.h>
#include<stdlib.h>

typedef char element;

typedef struct DeQueueNodeType {
	element data;
	struct DQNode* llink;
	struct DQNode* rlink;
} DQNode;

typedef struct DeQueueType{
	DQNode* front, * rear;
} DQueType;

DQueType* createDQue() {
	DQueType* DQ = (DQueType*)malloc(sizeof(DQueType));
	DQ->front = NULL;
	DQ->rear = NULL;
	return DQ;
}
int isDeQEmpty(DQueType* DQ) {
	if (DQ->front == NULL)  return 1;
	else return 0;
}
void insertFront(DQueType* DQ, element item) {
	DQNode* newNode = (DQNode*)malloc(sizeof(DQNode));
	newNode->rlink = NULL;
	newNode->llink = NULL;

	newNode->data = item;
	if (isDeQEmpty(DQ)) {
		DQ->front = newNode;
		DQ->rear = newNode;
	}
	else {
		DQ->front->llink = newNode;
		newNode->rlink = DQ->front;
		DQ->front = newNode;
	}
}


void insertRear(DQueType* DQ, element item) {
	DQNode* newNode = (DQNode*)malloc(sizeof(DQNode));
	newNode->data = item;

	newNode->rlink = NULL;
	newNode->llink = NULL;

	if (isDeQEmpty(DQ)) {
		DQ->front = newNode;
		DQ->rear = newNode;
	}
	else {
		DQ->rear->rlink = newNode;
		newNode->llink = DQ->rear;
		DQ->rear = newNode;
	}
}

element deleteFront(DQueType* DQ) {
	DQNode* old = DQ->front;
	element item;
	if (isDeQEmpty(DQ)) {
		printf("\n Linked deQue is empty! \n");  return;
	}
	else {
		item = old->data;
        DQ->front = DQ->front->rlink;
		DQ->front->llink = NULL;
		if (DQ->front == NULL) {
			DQ->front = NULL;
			DQ->rear = NULL;
		}
		free(old);
		return item;
	}
}


element deleteRear(DQueType* DQ) {
	DQNode* old = DQ->rear;
	element item;
	if (isDeQEmpty(DQ)) {
		printf("\n Linked deQue is empty! \n"); return;
	}
	else {
		item = old->data;
        DQ->rear = DQ->rear->llink;
		DQ->rear->rlink = NULL;
		if (DQ->rear == NULL) {
			DQ->front = NULL;
			DQ->rear = NULL;
		}
		free(old);
		return item;
	}
}

void printDQ(DQueType* DQ) {
	DQNode* temp = DQ->front;
	printf("DeQue : ");
	while (temp) {
		printf("%3c", temp->data);
		temp = temp->rlink;
	}
}

int main(void) {
	DQueType* DQ1 = createDQue();
	element data;
	printf("\n front 삽입 A>> ");  insertFront(DQ1, 'A');  printDQ(DQ1);
	printf("\n front 삽입 B>> ");  insertFront(DQ1, 'B');  printDQ(DQ1);
	printf("\n rear  삽입 C>> ");  insertRear(DQ1, 'C');  printDQ(DQ1);
	printf("\n front 삭제  >> ");  data = deleteFront(DQ1);    printDQ(DQ1);
	printf("\t삭제 데이터: %c", data);
	printf("\n rear  삭제  >> ");  data = deleteRear(DQ1);     printDQ(DQ1);
	printf("\t\t삭제 데이터: %c", data);
	printf("\n rear  삽입 D>> ");  insertRear(DQ1, 'D');  printDQ(DQ1);
	printf("\n front 삽입 E>> ");  insertFront(DQ1, 'E');  printDQ(DQ1);
	printf("\n front 삽입 F>> ");  insertFront(DQ1, 'F');  printDQ(DQ1);

	return 0;
}

 

'알고리즘과 자료구조' 카테고리의 다른 글

트리 순회  (0) 2023.05.04
트리  (0) 2023.04.29
큐  (0) 2023.04.26
스택  (0) 2023.04.25
연결 리스트  (0) 2023.04.21
'알고리즘과 자료구조' Related Articles more
Comments