[자료구조] 큐(1)
큐(queue)
선입선출(FIFO: First-In-First-Out) 또는 후입후출(LILO: Last-In-Last-Out) 프로토콜을 구현하는 자료구조를 말함
- 큐의 뒤에서는 삽입만 하고, 앞에서는 삭제만 할 수 있는 구조임
- 큐에 자료를 삽입할 수 있는 자료의 수는 유한해야 함(overflow 발생)
- 삭제 시에 자료의 조사(underflow)를 선행해야 함
- 삽입 시 rear, 삭제 시 front를 통해 연산이 이루어짐
- e.g.) 입장권을 구입하기 위해 기다리는 사람들의 줄, 활주로에서 이륙을 위해 대기중인 비행기의 줄
큐의 삽입/삭제의 구현
1차원 배열의 크기(queue_array[20])에 원소를 삽입/삭제하는 프로그램
#include <stdio.h>
#define MAX 20
int queue_array[MAX];
int rear = -1;
int front = -1;
void insert(){ // 큐에 rear를 이용하여 원소의 삽입
int add_item;
if(rear == MAX -1)
printf("큐 오버플로우\n");
else{
if(front == -1) //큐가 empty인 경우 원소 삽입
front = 0;
printf("큐에 원소를 삽입:");
scanf("%d", &add_item);
rear = rear + 1;
queue_array[rear] = add_item;
}
}
void delete(){ // 큐에서 front를 이용하여 원소 삭제
if (front == - 1 || front > rear){ //큐가 empty이면 언더플로우
printf("큐 언더플로우\n");
return ;
}
else{
printf("큐에서 삭제된 원소 : %d\n", queue_array[front]);
front = front + 1;
}
}
void display(){ //큐에 있는 원소들을 출력
int i;
if (front == - 1)
printf("큐가 empty이다. \n");
else{
printf("큐에 있는 원소 : \n");
for (i = front; i <= rear; i++)
printf("%d", queue_array[i]);
printf("\n");
}
}
main(){
int choice;
printf("1. 큐에 원소 삽입\n");
printf("2. 큐에서 원소 삭제\n");
printf("3. 큐의 모든 원소 출력\n");
printf("4. 종료\n");
while (1){
printf("큐의 연산 종류에 해당하는 번호를 선택하세요 : ");
scanf("%d", &choice);
switch (choice){
case 1:
insert();
break;
case 2:
delete();
break;
case 3:
display();
break;
case 4:
exit(1);
default :
printf("잘못된 선택입니다. \n");
}
}
}
실행결과
1. 큐에 원소 삽입
2. 큐에서 원소 삭제
3. 큐의 모든 원소 출력
4. 종료
큐의 연산 종류에 해당하는 번호를 선택하세요 : 1
큐에 원소를 삽입: 10
큐의 연산 종류에 해당하는 번호를 선택하세요 : 3
큐에 있는 원소:
10
큐의 연산 종류에 해당하는 번호를 선택하세요 :
이동큐(moving queue)
선형큐의 삽입/삭제 시 문제점
- 원소의 삽입/삭제 시 큐는 점차 오른쪽으로 이동하여 선형큐의 잘못된 포화상태로 인식함
- 큐의 빈 기억공간이 있음에도 불구하고 overflow가 발생함
- rear = N - 1에 의해 큐가 포화상태가 됨
선형큐의 잘못된 포화상태 인식의 해결 방법
- 저장된 원소들을 배열의 앞부분으로 이동하여 해결함
- 순차자료에서의 이동 작업은 연산이 복잡하여 효율성이 떨어짐
- 최악의 경우 원소 삽입 시마다 데이터 이동에 대한 오버헤드 발생함
- 최악의 경우 = O(큐의 크기)
이동큐 삽입/삭제
삽입 알고리즘
addmq(q) { //이동후 삽입
int i;
if (queue_full){ //큐의 오버플로우
if(front != -1){
for(i=0; i<SIZE-front-1; i++)
queue[i]=queue[front+i+1]; //원소 이동
front=-1;
rear=rear-SIZE+i; //이동에 따른 rear값 변경
rear=rear+1;
queue[rear]=e;
return true;
}
else return false;
}
else{
rear=rear+1;
queue[rear]=e; //원소 e 삽입
}
}
삭제 알고리즘
deletemq(q) { //삭제후 이동
int i;
char data;
if (rear==-1) queue-underflow;
e=q[0];
for(i=0; i<=rear; i++){
q[i]=q[i+1];
}
rear=rear-1;
}
환형큐(Circular queue)
이동큐의 특징
- 선형큐의 기억공간 활용 문제를 해결해줌
- 원소들의 이동에 따른 연산 시간이 지연됨 - 시간복잡도: O(n)
환영큐
- 1차원 배열로 구성된 큐를 시계방향으로 두 개의 포인터가 이동하는 환형으로 간주함
- 논리적으로 배열의 처음과 끝이 연결되어 있다고 가정
- 초기상태 => front = rear = 0
- 삽입동작 => rear = N-1 이면 다음 원소는 queue[0]애 저장
- 큐가 공백 => front = rear
- 환영큐의 논리적 구조(N=8)
1차원 배열을 이용한 큐의 구현
크기가 n인 배열 Q[0:n-1]을 환형으로 간주
- 자료의 삽입/삭제를 위한 큐의 rear와 front의 위치를 지정하기 위한 방법
- 마지막 색인 n-1에서 논리적인 다음 자리인 색인 0번으로 이동하기 위해서 나머지 연산자 mod를 사용함
- rear = (rear + 1) % n(마지막으로 삽입된 원소의 위치)
- front = (front + 1) % n(첫 번째 원소로부터 반 시계 방향으로 하나 앞의 위치)
- front = rear의 포화상태/공백상태를 구분이 필요함
- 최대 원소 수 = n-1
- 공백상태/포화상태 구분을 쉽게 하기 위해서 front가 있는 자리는 사용하지 않고 항상 빈자리로 둠(1개의 기억공간을 낭비)
- 초기 front = rear = 0(환형이기 때문에 첨자를 -1로 설정할 수 없음)
- 공백 front = rear
환형큐에서의 연산(생성/삽입/삭제) : creatcq[8]
환영큐의 삽입/삭제 구현
1차원 배열의 크기(cqueue_arr[5])에 원소를 삽입/삭제하는 프로그램
#include <stdio.h>
#define MAX 5
int cqueue_arr[MAX];
int front = -1; //front와 rear를-1로 초기화
int rear = -1;
void insert(int item){ //원소 삽입
if((front == 0 && rear == MAX-1) || (front == rear+1)){ //오버플로우 검사
printf("큐 오버플로우\n");
return;
}
if(front == -1){
front = 0; // front와 rear를-1에서0으로 설정
rear = 0;
}
else{
if(rear == MAX-1) rear = 0;
else rear = rear+1;
}
cqueue_arr[rear] = item ; //원소 삽입
}
void deletion(){ //원소 삭제
if(front == -1){
printf("큐 언더플로우\n");
return ;
}
printf("큐에서 삭제 원소 : %d\n", cqueue_arr[front]); //front 위치의 원소 삭제
if(front == rear){
front = -1;
rear=-1;
}
else{
if(front == MAX-1) front = 0;
else front = front+1;
}
}
void display(){ //원소 출력
int front_pos = front, rear_pos = rear;
if(front == -1){ //큐의 언더플로우
printf("큐가 비었음\n");
return;
}
printf("큐의 원소들은 :");
if(front_pos <= rear_pos)
while(front_pos <= rear_pos){
printf("%d ", cqueue_arr[front_pos]);
front_pos=front_pos+1;
}
else{
while(front_pos <= MAX-1){
printf("%d ", cqueue_arr[front_pos]);
front_pos=front_pos+1;
}
front_pos = 0;
while(front_pos <= rear_pos){
printf("%d ", cqueue_arr[front_pos]);
front_pos=front_pos+1;
}
}
printf("\n");
}
int main(){
int choice, item;
printf("1. 삽입");
printf("\t2. 삭제");
printf("\t3. 출력");
printf("\t4. 종료\n");
do{
printf("연산 선택 : ");
scanf("%d", &choice);
switch(choice){
case 1 :
printf("큐에 삽입할 원소 : ");
scanf("%d", &item);
insert(item); //원소 삽입 함수 insert() 호출
break;
case 2 :
deletion(); ////원소 삭제 함수 deletion() 호출
break;
case 3:
display();
break;
case 4:
break;
default:
printf("번호 선택을 다시 하세요!!!");
}
}while(choice!=4);
return 0;
}
실행결과
1. 삽입 2. 삭제 3. 출력 4. 종료
연산 선택 : 2 큐 언더플로우
연산 선택 : 1
큐에 삽입할 원소 : 10
연산 선택 : 1
큐에 삽입할 원소 : 20
연산 선택 : 1
큐에 삽입할 원소 : 30
연산 선택 : 3
큐의 원소들은 :10 20 30
연산 선택 : 2
큐에서 삭제 원소 : 10
연산 선택 : 3
큐의 원소들은 :20 30
연산 선택:
학습정리
- 큐는 입장권을 구입하기 위해 기다리는 사람들의 줄과 같이 선입선출(FIFO: First-In-First-Out) 또는 후입후출(LILO: Last-In-Last-Out) 프로토콜을 구현하는 자료구 조이다.
- 큐는 삽입 시 rear, 삭제 시 front를 통해 연산이 이루어진다.
- 이동큐는 선형큐의 삽입/삭제 시 포화상태의 잘못된 인식의 문제점을 해결할 수 있지만 저장된 원소들을 앞부분으로 이동하는 오버헤드가 발생한다.
- 환형큐는 이동큐의 시간 지연 문제점을 해결하기 위한 자료구조로서 1차원 배열로 구성 된 큐를 시계방향으로 두 개의 포인터가 이동하는 환형으로 생각하여 원소들을 삽입/삭 제할 수 있는 구조이다.