Data Structures & Algorithms
[Data Structures] 큐 (Queue)와 덱 (Deque)
숄구-ml
2022. 5. 6. 21:28
1. 큐는 스택과 달리 먼저 들어간 데이터가 먼저 나오는 구조 = 'First In, First Out' = 선입선출
2. 큐의 ADT 정의
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
void QueueInit(Queue * pq);
//큐의 초기화를 진행
//큐 생성 후 제일 먼저 호출되어야 하는 함수
int QIsEmpty(Queue * pq);
//큐가 빈 경우 TRUE(1), 그렇지 않은 경우 FALSE(0)
void Enqueue(Queue * pq, Data data);
//큐에 데이터를 저장. 매개변수 data로 전달된 값을 저장
Data Dequeue(Queue * pq);
//저장순서가 가장 앞선 데이터를 삭제
//본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다
Data QPeek(Queue * pq);
//저장순서가 가장 앞선 데이터를 반환하되 삭제하지 않는다
//본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야
|
cs |
3. 배열 기반의 큐 = '원형 큐 (circular queue)'
- F와 R의 위치만으로 꽉 찬 경우와 텅 빈 경우를 구분할 수가 없다
- 따라서, 배열의 저장공간을 하나 비워둠으로써 이를 해결한다
- 원형 큐가 텅 빈 상태 - F와 R이 동일한 위치를 가리킨다
- 원형 큐가 꽉 찬 상태 - R이 가리키는 위치의 앞을 F가 가리킨다
- 원형 큐의 헤더파일 정의 및 구현
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#ifndef __C_QUEUE_H__
#define __C_QUEUE_H__
#define TRUE 1
#define FALSE 0
#define QUE_LEN 100
typedef int Data;
typedef struct _cQueue
{
int front; //그림에서 F라 표현했던 멤버
int rear; //그림에서 R이라 표현했던 멤버
Data queArr[QUE_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
|
cs |
4. 연결 리스트 기반의 큐
- 리스트 기반 큐의 헤더 파일 정의
|
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
|
#ifndef __C_QUEUE_H__
#define __C_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; // 그림을 통해서 F라 표현한 멤버
Node * rear; // 그림을 통해서 R이라 표현한 멤버
} 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
|
cs |
- 연결 리스트 기반 큐의 구현 예시
5. 덱은 앞으로도 뒤로도 넣을 수 있고, 앞으로도 뒤로도 뺄 수 있는 자료구조
- ADT를 구성하는 핵심 기능: 앞으로 넣기 / 뒤로 넣기 / 앞에서 빼기 / 뒤에서 빼기
- 따라서, 덱의 구현은 양방향 연결리스트가 가장 용이하다
- 연결 리스트 기반 덱의 구현 예시
|
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
32
33
34
35
36
|
#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 _dlDeque
{
Node * head;
Node * tail;
} DLDeque;
typedef DLDeque Deque;
void DequeInit(Deque * pdeq);
// 덱의 초기화를 진행
// 덱 생성 후 제일 먼저 호출되어야 하는 함수
int DQIsEmpty(Deque * pdeq);
//덱의 머리에 데이터를 저장, data로 전달된 값을 저장
void DQAddFirst(Deque * pdeq, Data data);
//덱의 머리에 데이터를 저장
void DQAddLast(Deque * pdeq, Data data);
//덱의 꼬리에 데이터를 저장
Data DQRemoveFirst(Deque * pdeq);
//덱의 머리에 위치한 데이터를 반환 및 소멸
Data DQRemoveLast(Deque * pdeq);
//덱의 꼬리에 위치한 데이터를 반환 및 소멸
Data DQGetFirst(Deque * pdeq);
//덱의 머리에 위치한 데이터를 소멸하지 않고 반환
Data DQGetLast(Deque * pdeq);
//덱의 꼬리에 위치한 데이터를 소멸하지 않고
|
cs |
728x90