선형 자료구조 (스택, 큐, 덱)
스택
[이 포스트에서는 라이브러리를 사용하는 자료구조가 아닌 배열을 사용하여 자료구조를 다루고 있습니다.]
스택은 스택에 값을 삽입하는 push()와 값을 삭제하는 pop(), 스택이 비었는지 확인하는 isEmpty(), 스택이 포화상태 인지 확인하는 isFull() 정도로 기능을 설명할 수 있습니다.
또, 스택에는 top이라고 불리는 포인터가 있습니다. 이 포인터는 현재 스택의 최상위 값을 나타내며, 이 포인터가 배열의 끝을 가리키고 있다면 포화상태 즉, Full이라고 할 수 있고 배열의 제일 첫번째를 가리킨다면 Empty라고 할 수 있습니다.
|
1
2
3
4
5
6
7
8
9
10
11
|
//배열의 사이즈는 N으로 정의
bool isFull() {
if(top == N - 1) return true;
return false;
}
bool isEmpty() {
if(top == -1) return true;
return false;
}
|
cs |
push는 top 포인터를 1 증가시키고, top 포인터가 가리키는 위치에 값을 삽입하는 함수입니다. 이 때, 스택이 포화 상태라면 push함수는 사용 불가능합니다.
|
1
2
3
4
5
6
|
//배열과 삽입하려는 데이터는 정수로 가정
void push(int data) {
if(isFull()) return; //배열(스택)이 포화상태이므로, push 불가.
stack[++top] = data;
}
|
cs |
반대로, pop은 현재 top포인터가 가리키는 위치의 값을 리턴하고 그 값을 배열에서 삭제한 후, top포인터를 1 감소하는 함수입니다. push와 반대로 스택이 공백 상태 일 때, pop함수는 사용 불가능 해집니다.
|
1
2
3
4
|
int pop() {
if(isEmpty()) exit(-1); //배열(스택)이 공백상태이므로, pop 불가.
return stack[top--];
}
|
cs |
위와 같이 프로그래머가 스택의 공백상태, 포화상태에 대하여 처리해주지 않으면, 오버플로우, 언더플로우가 발생할 수 있으므로 주의하여야합니다.
큐
큐는 스택의 push와 비슷한 enqueue와, pop과 비슷한 dequeue가 있습니다. 그리고 큐는 스택과 다르게 front, rear 포인터가 존재합니다. front는 현재 삽입된 데이터들의 가장 앞쪽을 가리키고, rear는 현재 삽입된 데이터들의 가장 마지막 쪽을 가리킵니다. 즉, 초기값은 둘다 동일합니다.
큐는 선형 배열로 구현할 때, 원형 배열로 구현할 때, count 기반의 원형 배열로 구현할 때가 전부 조금씩 다르게 구현됩니다. 선형으로 구현하게 되면 여유 공간이 있을 때도 포화 상태로 인식하게 되는 경우가 생기며, 이를 활용하기 위해 배열 내 원소의 이동과 front와 rear값이 변동되어야하므로 O(N)의 시간복잡도가 소요됩니다.
선형으로 구현할 때는 front와 rear의 초기값은 -1로 설정하고, isEmpty()는 front와 rear가 같을때 true를 리턴합니다. isFull()은 rear가 배열의 마지막 인덱스를 가리킬때 true를 반환합니다.
|
1
2
3
4
5
6
7
8
9
10
11
|
//배열의 사이즈는 N으로 정의
bool isEmpty() {
if(front == rear) return true;
return false;
}
bool isFull() {
if(rear == N - 1) return true;
return false;
}
|
cs |
enqueue()의 경우 큐가 포화 상태가 아닐 때, rear를 1 증가시키고 rear가 가리키는 위치에 값을 삽입하는 함수입니다.
|
1
2
3
4
5
6
|
//배열과 삽입하려는 데이터는 정수로 가정
void enqueue(int data) {
if(isFull()) return; //배열(큐)가 포화상태이므로, enqueue 불가.
queue[++rear] = data;
}
|
cs |
dequeue()의 경우 큐가 공백 상태가 아닐 때, front를 1 증가시키고 front가 가리키는 위치의 값을 리턴하고 front 위치의 값을 삭제합니다.
|
1
2
3
4
|
int dequeue() {
if(isEmpty()) exit(-1); //배열(큐)가 공백상태이므로, dequeue 불가.
return queue[++front];
}
|
cs |
다음으로 원형으로 구현하는 큐입니다. 원형 큐는 배열의 마지막 인덱스에 도달 후 다음 인덱스로 첫번째 인덱스를 접근하게 하기 위해 나머지 연산을 이용하여 배열 내 인덱스를 이동합니다. 선형 배열에서의 단점은 해소했으나 0번째 인덱스를 비워놓아야 하기 때문에 N-1개의 원소를 저장할 수 있는 구조입니다.
원형 큐에서는 front와 rear의 초기값을 1로 정의합니다. 이는 공백 큐 상태와 포화큐 상태 구분을 위해 배열의 0번째를 비워놓기 때문입니다. 그러므로 isEmpty()는 똑같이 front와 rear가 같을 때, true를 리턴하지만 isFull()은 rear의 다음 위치가 front랑 같을 때 true를 리턴합니다.
|
1
2
3
4
5
6
7
8
9
|
bool isEmpty() {
if(front == rear) return true;
return false;
}
bool isFull() {
if(front == (rear + 1) % N) return true; //원형 큐에서의 나머지 연산.
return false;
}
|
cs |
enqueue()의 경우 큐가 포화 상태가 아닐 때, rear를 나머지 연산을 이용하여 1 증가시키고 rear가 가리키는 위치에 데이터를 삽입합니다.
|
1
2
3
4
5
|
void enqueue(int data) {
if(isFull()) return;
rear = (rear + 1) % N;
queue[rear] = data;
}
|
cs |
dequeue()의 경우 큐가 공백 상태가 아닐 때, front를 나머지 연산을 이용해 1 증가시키고, front가 가리키는 위치의 값을 리턴하고 그 값을 삭제합니다.
|
1
2
3
4
5
|
int dequeue() {
if(isEmpty()) exit(-1);
front = (front + 1) % N;
return queue[front];
}
|
cs |
count를 기반으로 하는 원형 큐는 일반 원형 큐와는 다르게 rear를 사용하지않고 count를 사용합니다. count는 큐에 삽입된 원소의 개수를 저장합니다. count와 front는 초기값이 0으로 설정됩니다. 일반 원형 큐에 비해 count값으로 공백, 포화를 판단하므로, N개의 원소를 저장할 수 있습니다.
count 기반의 원형 큐에서 isEmpty()는 count가 0일때 true를 리턴합니다. isFull()은 count값이 배열의 사이즈와 같을 때 true를 리턴합니다.
|
1
2
3
4
5
6
7
8
9
|
bool isEmpty() {
if(count == 0) return true;
return false;
}
bool isFull() {
if(count == N) return true;
return false;
}
|
cs |
enqueue()의 경우 큐가 포화 상태가 아닐 때, (front + count) % N 위치에 데이터를 삽입하고 count를 1 증가시킵니다.
|
1
2
3
4
5
|
void enqueue(int data) {
if(isFull()) return;
queue[(front+count) % N] = data;
count++;
}
|
cs |
dequeue()의 경우 큐가 공백 상태가 아닐 때, 현재 front의 값을 반환하고 삭제한 후, front를 나머지 연산을 이용해 1 증가시키고 count를 1 감소시킵니다.
|
1
2
3
4
5
6
7
|
int dequeue() {
if(isEmpty()) exit(-1);
int data = queue[front];
front = (front + 1) % N;
count--;
return data;
}
|
cs |
덱
덱은 스택과 큐의 기능이 합쳐진 자료구조로, front 위치와 rear 위치 둘 다에서 삽입과 삭제가 가능합니다. 큐에서 설명하였듯이, 효율적으로 자료를 저장할 수 있는 count 기반의 원형 배열로 구현하게 됩니다. 공백과 포화의 조건은 count 기반의 원형 큐와 같습니다.
rear에서 삽입하는 addRear의 경우 덱이 포화 상태가 아닐 때, (front + count) % N 위치에 데이터를 삽입하고 count를 1 증가시킵니다.
|
1
2
3
4
5
|
void addRear(int data) {
if(isFull()) return;
queue[(front + count) % N] = data;
count++;
}
|
cs |
front에서 삽입하는 addFront의 경우 덱이 포화 상태가 아닐 때, front를 나머지 연산을 이용해 1 감소시킨 후 front 위치에 자료를 삽입하고 count를 1 증가시킵니다.
|
1
2
3
4
5
6
|
void addFront(int data) {
if(isFull()) return;
front = (front - 1 + N) % N;
queue[front] = data;
count++;
}
|
cs |
rear에서 삭제하는 removeRear의 경우 덱이 공백 상태가 아닐 때, rear 위치의 자료를 반환 및 삭제 후, count 값을 1 감소시킵니다.
|
1
2
3
4
5
6
|
int removeRear() {
if(isEmpty()) exit(-1);
int data = queue[(front + count - 1) % N];
count--;
return data;
}
|
cs |
front에서 삭제하는 removeFront의 경우 덱이 공백 상태가 아닐 때, front 위치의 데이터를 반환 및 삭제 후 front를 나머지 연산을 이용하여 1 증가시키고 count 값을 1 감소시킵니다.
|
1
2
3
4
5
6
7
|
int removeFront() {
if(isEmpty()) exit(-1);
int data = queue[front];
front = (front + 1) % N;
count--;
return data;
}
|
cs |
이렇게 이번 포스트에서는 선형 자료구조인 스택, 큐, 덱의 기능과 구현에 대해서 리뷰해보았습니다.