[자료구조] 큐(Queue)
큐(Queue)란
자료구조 중 하나로, 스택(Stack)처럼 데이터가 들어가는 배열이라 생각하면 편하며
스택과는 다르게 후입후출(LILO: Last In Last Out) 구조를 가진다.
1. 큐의 기본 구조
큐는 전단과 후단을 관리해야 하는데,
첫번째 요소 하나 앞의 인덱스를 가리키는 front, 마지막 요소의 인덱스를 가리키는 rear가 필요하고
큐에 요소를 넣는 enqueue, 요소를 제거하는 dequeue 메소드를 기본으로 가진다.
큐의 구조 - 그림으로 표현
C++로 큐를 구현하기 위해서 배열을 원형으로 이용한 원형큐 방식을 사용하겠다. 간단한 원형큐 구조는 아래와 같다.
2. C++, 큐 객체 구현
#define MAX 5
#define PUSH 1
#define POP 2
class Queue{
private:
int front;
int rear;
int lastOp;
int data[MAX];
public:
Queue(){
front = 0;
rear = 0;
lastOp = 0;
}
~Queue(){}
int isEmpty(){
if(front == rear && lastOp != PUSH){
return 1;
}else return 0;
}
bool isFull(){
if(front == rear && lastOp == PUSH) return 1;
else return 0;
}
void enqueue(int i){
if (!isFull()){
rear = (rear+1)%MAX;
this->data[rear] = i;
lastOp = PUSH;
}
}
int dequeue(){
if(!isEmpty()){
lastOp = POP;
front = (front+1)%MAX;
return data[front];
}
return 0;
}
void printQ(){
int numberOfQ;
numberOfQ = rear > front ? rear-front : (rear+MAX) - front;
int index = front +1;
for (int i = 0; i < numberOfQ; i++){
cout << data[(index+i)%MAX] << " ";
}
cout << endl;
}
};
Queue 객체 설명
- private으로 front, rear, lastOp, data를 선언한다.
// lastOp는 isFull과 isEmpty를 확인할 때, 둘 다 front와 rear가 같은 경우이므로 구분을 위한 변수이다. - Queue(){} // 생성자 함수, 변수들을 초기값 0으로 지정한다.
- bool isEmpty(){} // 큐가 비어 있는 지를 확인한다, 비어 있을 경우 true를 반환한다.
- bool isFull(){} // 큐가 꽉 차 있는 지 확인한다, 꽉 차 있을 경우 true를 반환한다.
- void enqueue(int i){} // isFull을 확인하고 아닐 경우,
lastOp를 PUSH으로 설정, rear+1에서 %MAX한 값을 rear로 설정하고, data[rear]를 i값으로 지정한다. - int dequeue(){} // isEmpty를 확인하고 아닐 경우,
lastOp를 POP으로 설정, front+1에서 %MAX한 값을 front로 설정하고, data[front]를 리턴한다. - void display(){} // rear가 front보다 클 경우 numberOfQ를 rear-front로 지정,
아닐 경우 numberOfQ를 (rear+MAX)-front로 지정한다.
index를 front+1로 선언하고 큐를 반복문을 이용해 순회하며 큐의 값들을 디스플레이한다.
3. main() 함수 예제
int main(){
Queue q; // Queue 생성
q.enqueue(1); // 1 추가
q.enqueue(2); // 2 추가
q.enqueue(3); // 3 추가
q.enqueue(4); // 4 추가
q.enqueue(5); // 5 추가
q.enqueue(6); // isFull이기에 추가 x
cout << q.dequeue() << endl; // LILO 구조에 따라 1이 반환
q.enqueue(9); // 9 추가
q.printQ(); // 2 3 4 5 9
}
4. output
1
2 3 4 5 9
정리,
큐는 후입후출 - 선입선출 구조를 가지는 자료구조
다양한 문제를 해결하기 위한 알고리즘에서 활용할 수 있다. - ex. BFS(너비 우선 탐색) 알고리즘 etc…