자료 구조 - 큐
‘c++로 쉽게 풀어쓴 자료구조 1판 - 천인국, 최영규’ 책을 참고하여 작성한 포스트입니다.
큐(Queue)
- 큐는 자료의 입출력이 선입선출(FIFO: First-In First-Out)의 형태로 일어나는 자료구조를 말한다.
- 큐에서 삽입이 일어나는 곳을 후단(rear)이라고 하고 삭제가 일어나는 곳을 전단(front)라고 한다.
큐의 추상 자료형
스택과 유사하다
데이터: 선입선출의 접근 방법을 유지하는 요소들의 모음
연산
- enqueue(e): 주어진 요소 e를 큐의 맨 앞에 추가
- dequeue(): 큐가 비어 있지 않으면 맨 앞에 있는 요소를 삭제하고 반환
- isEmpty(): 큐가 비어 있으면 true, 그렇지 않으면 false 반환
- peek(): 큐가 비어있지 않으면 맨 앞에 있는 요소를 삭제하지 않고 반환
- isFull(): 큐가 가득 차 있으면 true, 그렇지 않으면 false 반환
- size(): 큐 내의 모든 요소들의 개수를 반환
- display(): 큐 내의 모든 요소들을 출력함
큐의 활용
컴퓨터 장치들 사이에서 데이터를 주고받을 때 각 장치들 사이에 존재하는 속도의 차이나 시간 차이를 극복하기 위한 임시 기억 장치로 큐가 사용되는데, 이것을 보통 버퍼(buffer)라고 부른다.
큐의 구현
- 선형 큐 : front와 rear의 값이 계속 증가하므로 언젠가는 배열의 끝에 도달하게 되어 더 이상 삽입하지 못하게 된다. 이 때 모든 요소들을 왼쪽으로 이동시켜야 하는데 그러면 삽입 연산의 시간 복잡도가 $O(n)$이 된다.
- 원형 큐 : 배열이 원형처럼 처음과 끝이 연결되어 있다고 가정한 큐이다. 배열의 끝에 도달하면 가리키는 인덱스를 0으로 바꾸어주면 된다. 그러면 배열이 포화되지 않는 이상 삽입과 큐는 끝없이 이루어질 수 있다.
원형 큐 구현 시 포화 상태와 공백 상태를 구분하기 위해 하나의 자리는 항상 비워두어야 한다!
원형 큐의 구현
큐 구현 코드
#include <cstdio>
#include <cstdlib>
#define MAX_QUEUE_SIZE 100
inline void printErrorMSG(char* message) {
printf("%s\n", message);
exit(1);
}
class CircularQueue {
protected:
int front;
int rear;
int queue[MAX_QUEUE_SIZE];
public:
CircularQueue() {
front = 0;
rear = 0;
}
bool isEmpty() {
if(front == rear) {
return true;
} else {
return false;
}
}
bool isFull() {
if(front == (rear+1)%MAX_QUEUE_SIZE) {
return true;
} else {
return false;
}
}
void enqueue(e) {
if(isFull()) {
printErrorMSG("queue is full");
} else {
queue[rear] = e;
rear += 1;
}
}
int dequeue() {
if(isEmpty()) {
printErrorMSG("queue is empty");
} else {
int n = queue[front];
front = (front+1)%MAX_QUEUE_SIZE;
return n;
}
}
int peek() {
if(isEmpty()) {
printErrorMSG("queue is empty");
} else {
return queue[front];
}
}
int size() {
if(front > rear) {
return 8 - front + rear;
} else {
return rear - front;
}
}
void display() {
if(front > rear) {
for(int i=front+1; i<MAX_QUEUE_SIZE; i++) {
printf("%d, ");
}
for(int i=0; i<=rear; i++) {
printf("%d, ");
}
} else {
for(int i=front+1; i<=rear; i++) {
printf("%d, ");
}
}
printf("\n");
}
}
연결리스트로 구현한 큐
원형 배열로 구현한 큐도 스택과 같이 크기가 제한된다는 약점이 있다. 연결리스트를 이용하면 크기 제한이 사라진다. 자세한건 연결리스트에서!
덱(deque)
덱은 double-ended queue의 줄임말로서 큐의 전단(front)과 후단(rear)에서 모두 삽입과 삭제가 가능한 큐를 의미한다. 중간에 삽입 삭제는 x!
즉, 스택과 큐의 연산들을 모두 가지고 있다고 보면 된다.
덱 추상 자료형
데이터: 전단과 후단을 통한 접근을 허용하는 요소들의 모음
연산
- addFront(e): 주어진 요소 e를 덱의 맨 앞에 추가
- deleteFront(): 덱이 비어 있지 않으면 맨 앞 요소를 삭제하고 반환
- addRear(e): 주어진 요소 e를 덱의 맨 뒤에 추가
- deleteRear(): 덱이 비어 있지 않으면 맨 뒤 요소를 삭제하고 반환
- isEmpty(): 덱이 비어 있으면 true, 그렇지 않으면 false 반환
- getFront(): 덱이 비어있지 않으면 맨 앞 요소를 삭제하지 않고 반환
- getRear(): 덱이 비어있지 않으면 맨 뒤 요소를 삭제하지 않고 반환
- isFull(): 덱이 가득 차 있으면 true, 그렇지 않으면 false 반환
- display(): 덱 내의 모든 요소들을 출력함
덱의 구현
- 덱도 원형 큐에서와 같이 배열을 이용하는 방법과 연결 리스트를 사용하는 방법이 있다.
배열을 이용한 원형 덱의 구현
앞서 구현한 원형 큐 클래스를 상속받아 구현한다.
원형 큐의 구현
덱 구현 코드
// 앞서 만든 큐 클래스
#include "CircularQueue.h"
class CircularDeque : public CircularQueue {
public:
CircularDeque() {}
void addRear (int val) {
// 큐와 동일한 연산
enqueue(val);
}
int deleteFront() {
// 큐와 동일한 연산
return dequeue();
}
int getFront() {
// 큐와 동일한 연산
return peek();
}
void addFront(int val) {
if(isFull()) {
printErrorMSG("deque is full");
} else {
queue[front] = val;
front = (front-1) % MAX_QUEUE_SIZE;
}
}
int deleteRear() {
if(isEmpty()) {
printErrorMSG("deque is empty");
} else {
int n = queue[rear];
rear = (rear-1+MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
return n;
}
}
int getRear() {
if(isEmpty()) {
printErrorMSG("deque is empty");
} else {
return queue[rear];
}
}
void display() {
printf("덱의 요소들: ");
int length = (front < rear) ? rear : rear+MAX_QUEUE_SIZE;
for(int i=front+1; i<=lentgh; i++) {
printf("%d, ", queue[i % MAX_QUEUE_SIZE]);
}
printf("\n");
}
}
연결된 덱의 구현
덱은 스택이나 큐와 달리 전단과 후단에서 모두 삽입, 삭제가 가능하므로 이중 연결 리스트를 이용해 구현해야 한다.
Leave a comment