Data Structure : Queue
자료구조(출처)
Queue
큐는 선형 리스트의 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지도록 구성한 자료구조.
가장 먼저 삽입된 자료가 가장 먼저 출력되는 선입선출(FIFO) 방식으로 처리함.
가장 먼저 삽입된 자료의 기억공간을 가리키는 포인터로 삭제 작업이 이루어지는 Front 포인터
가장 마지막에 삽입된 자료가 위치한 기억장소를 가리키는 포인터로 삽입 작업이 이루어지는 Rear 포인터
Queue는 순서를 기다리는 대기 행렬 처리에 사용되거나 운영체제의 작업 스케쥴링에 사용됨.
순차 자료구조로 구현한 큐
Sequential Queue
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
using namespace std;
const int MAX = 100000;
template <class T>
class Queue {
private :
int front_idx=0;
int rear_idx=0;
int q_size=0;
T data[MAX];
public :
Queue() {}
bool empty() {
if(q_size<0) {
return true;
}
else return false;
}
void push(const T& val) {
if(rear_idx == MAX-1) {
cout << "Queue is full" << '\n';
}
else
data[rear_idx++]=val;
q_size++;
}
void pop() {
if(empty() == 1) {
cout << "Queue is empty" << '\n';
}
else
front_idx++;
q_size--;
}
int size() {
if(empty() == true) {
return 0;
}
else
return q_size;
}
int front() {
if(empty() == 1) {
cout << "Queue is empty" << '\n';
}
else
return data[front_idx];
}
int back() {
if(empty() == 1) {
cout << "Queue is empty" << '\n';
}
else
return data[rear_idx];
}
};
int main() {
Queue<int> test;
cout << "size : " << test.size() << '\n';
for(int i=0; i<5;i++) {
test.push(i);
cout << "push : " << i
<< " / front : " << test.front()
<< " / size : " << test.size() << '\n';
}
for(int i=0; i<5;i++) {
test.pop();
cout << "pop : " << i
<< " / front : " << test.front()
<< " / size : " << test.size() << '\n';
}
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
size : 0
push : 0 / front : 0 / size : 1
push : 1 / front : 0 / size : 2
push : 2 / front : 0 / size : 3
push : 3 / front : 0 / size : 4
push : 4 / front : 0 / size : 5
pop : 0 / front : 1 / size : 4
pop : 1 / front : 2 / size : 3
pop : 2 / front : 3 / size : 2
pop : 3 / front : 4 / size : 1
pop : 4 / front : 0 / size : 0
Circular Queue
순차 큐에서는 큐가 포화 상태가 아님에도 rear 값이 배열의 끝에 위치하게 된다면 포화 상태로 인식하여 더 이상 삽입 연산을 수행하지 않음.
이는 rear 값을 맨 앞으로 옮기면 해결되는 문제임. 이를 해결하기 위해 원형 큐가 등장하게 됨.
원형 큐는 순차 큐의 잘못된 포화 상태 문제를 해결함.
1
2
3
4
5
6
7
8
삽입 위치는 rear = (rear+1) mod n
삭제 위치는 front = (front+1) mod n
원형 큐는 공백 상태와 포화 상태를 다음과 같이 구분함.
공백 상태 : front == rear
포화 상태 : (rear+1) mod n == front
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
using namespace std;
const int MAX = 5;
template <class T>
class Queue {
private :
int front_idx=0;
int rear_idx=0;
int q_size=0;
T data[MAX];
public :
Queue() {}
bool empty() {
if(front_idx == rear_idx ) {
front_idx=0;
rear_idx=0;
return true;
}
else return false;
}
void push(const T& val) {
if((rear_idx+1)%MAX == front_idx ) {
cout << "Queue is full " << '\n';
}
else {
rear_idx=(rear_idx+1)%MAX;
data[rear_idx]=val;
q_size++;
}
}
void pop() {
if(empty()) {
cout << "Queue is empty" << '\n';
}
else {
front_idx=(front_idx+1)%MAX;
q_size--;
}
}
int size() {
if(empty()) {
return 0;
}
else
return q_size;
}
int front() {
if(empty()) {
return 0;
}
else {
return data[front_idx+1];
}
}
int back() {
if(empty()) {
return 0;
}
else {
return data[rear_idx];
}
}
};
연결 자료구조로 구현한 큐
1
2
3
4
5
6
순차 자료구조를 이용해 구현한 큐의 단점에는 아래와 같음.
1. 사용 크기가 배열 크기로 제한되어 큐의 길이를 마음대로 사용할 수 없음.
2. 원소가 없어도 항상 고정된 크기를 유지해야함. -> 메모리 낭비
이러한 단점을 해결해주는 것이 연결 자료구조임.
Linked Queue
아래 코드는 push를 하면 반드시 pop를 한다는 가정하에 작성한 코드임.
push만 하고 종료를 하면 할당한 노드들은 delete가 되지 않으므로 delete를 해주는 멤버 함수를 작성해야 함.
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>
using namespace std;
typedef struct Qnode{
int data;
struct Qnode* link;
} Qnode;
typedef struct PointQ {
Qnode* front, *rear;
} PointQ;
template <class T>
class LinkedQ {
private :
int q_size=0;
PointQ* LQ = new PointQ;
public :
LinkedQ() {
LQ->front=NULL;
LQ->rear=NULL;
}
bool empty() {
if(LQ->front == NULL ) {
return true;
}
else return false;
}
void push(const T& val) {
Qnode* newNode = new Qnode;
newNode->data=val;
newNode->link=NULL;
if(empty()) {
LQ->front=newNode;
LQ->rear=newNode;
}
else {
LQ->rear->link = newNode;
LQ->rear=newNode;
}
q_size++;
}
void pop() {
if(empty()) {
cout << "Queue Empty!!" << '\n';
}
else {
Qnode* dNode = LQ->front;
LQ->front=dNode->link;
if(LQ->front == NULL) {
LQ->rear = NULL;
}
delete dNode;
q_size--;
}
}
int size() {
if(empty()) {
return 0;
}
else
return q_size;
}
int front() {
if(empty()) {
return -1;
}
else {
return LQ->front->data;
}
}
int back() {
if(empty()) {
return -1;
}
else {
return LQ->rear->data;
}
}
~LinkedQ() {
delete LQ;
}
};
int main() {
LinkedQ<int> test;
cout << "size : " << test.size() << '\n';
for(int i=1; i<=5; i++) {
test.push(i);
cout << "push : " << i
<< " / front : " << test.front()
<< " / back : " << test.back()
<< " / size : " << test.size() << '\n';
}
for(int i=1; i<=6;i++) {
test.pop();
cout << "pop : " << i
<< " / front : " << test.front()
<< " / back : " << test.back()
<< " / size : " << test.size() << '\n';
}
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
size : 0
push : 1 / front : 1 / back : 1 / size : 1
push : 2 / front : 1 / back : 2 / size : 2
push : 3 / front : 1 / back : 3 / size : 3
push : 4 / front : 1 / back : 4 / size : 4
push : 5 / front : 1 / back : 5 / size : 5
pop : 1 / front : 2 / back : 5 / size : 4
pop : 2 / front : 3 / back : 5 / size : 3
pop : 3 / front : 4 / back : 5 / size : 2
pop : 4 / front : 5 / back : 5 / size : 1
pop : 5 / front : -1 / back : -1 / size : 0
Queue Empty!!
pop : 6 / front : -1 / back : -1 / size : 0
This post is licensed under CC BY 4.0 by the author.