[자료구조 기초] queue , 큐

Queue

queue는 기다리는 줄을 자료구조로 표현

한쪽 끝 (Rear)에서는 element의 삽입만, 또 다른 끝 (front)에서는 원소의 삭제만 하도록 제한되어 있는 유한 순서 리스트이다

https://images.app.goo.gl/ABrE4fSn1CzkgdZs8

먼저 들어간 애가 먼저 삭제되는 FIFO 리스트이다. ( First In First Out) , 스택과 반대되는 개념이다.

---

Queue의 추상 자료형

• 0개 이상의 원소를 가진 유한 순서 리스트
• 선형 리스트나 연결 리스트를 사용한다.
• 리스트의 처음과 끝을 나타내는 Front와 Rear가 필요하다

---

Queue의 연산

operation	desc
init	큐를 초기화
insert	큐에 새로운 데이터를 하나 삽입
delete	큐의 Front 에 있는 데이터를 없애고 그 값을 반환
getFront	큐의 Front 에 있는 데이터의 값을 반환
getSize	현재 큐에 들어가 있는 원소의 수를 반환
isEmpty	큐가 비어있는지 확인
isFull	큐가 다 찻는지 확인

 

Queue 의 활용

• 시뮬레이션의 대기열
• 통신에서 수신한 데이터 패킷을 모아놓는 구조
• 프린트 대기열
• cpu 작업 스케쥴링

---

Array를 이용한 Queue의 표현

크기가 고정된 1차원 배열을 이용하여 queue를 표현한다

첫 번째 원소를 가리키는 Front, 마지막 원소를 가리키는 Rear변수가 있어야 함

Front = 0, Rear = -1로 초기화한다.

operation	desc
init	data[MaxQueueSize], Front, Reat 를 갖는 구조체 변수 선언 Front = 0, Rear = -1
insert	Rear를 1 증가 하고 data[Rear]에 데이터 삽입
delete	data[Front] 값을 읽어오고, Front 1 증가
getFront	data[Front] 데이터 반환
getSize	(Rear - Front+1)을 리턴
isEmpty	Front > Rear = empty
isFull	Rear > = MaxQueueSize-1 일 경우 큐가 꽉참

#define MaxQueueSize 10

typedef struct{
	int Front;
	int Rear;
	int data[MaxQueueSize];
}queueType;

void init(queueType *Qptr){
	Qptr->Front = 0;
	Qptr->Rear = -1;
}

int isEmpty(queueType *Qptr){
	return (Qptr->Front > Qptr->Rear);
}

int isFull(queueType *Qptr){
	return (Qptr->Rear >= MaxQueueSize-1);
}

int getSize(queueType *Qptr){
	return (Qptr->Rear - Qptr->Front +1);
}

int insert (queueType *Qptr, int x){
	if(isFull(Qptr)){
		printf("Can't insert the item in queue, Queue is full\n");
	}else{
		Qptr->Rear = Qptr->Rear +1;
		Qptr->data[Qptr->Rear] = x;
	}
}

int delete (queueType *Qptr){
	int temp;
	
	if (isEmpty(Qptr)){
		printf("Can't delete the item in queue, Queue is empty\n");
		return -1;
	}else{
		temp = Qptr->data[Qptr->Front];
		Qptr->Front = Qptr->Front+1;
		return temp;
		
	}
}

void queuePrint(queueType *Qptr){
	int i = 1,j;
	
	printf ("Queue has %d element \n",getSize(Qptr));
	for (j = Qptr->Front; j<= Qptr->Rear; j++){
		printf("%d element : %d\n", i++, Qptr->data[j]);
	}
}

 

#include <stdio.h>
#include "queue_array.h"

void main()
{
	// q1 이름을 가진 큐 생성
	queueType q1;	
	init(&q1);   //초기화

	// 큐에 원소 넣기
	insert(&q1, 10);
	insert(&q1, 20); 
	insert(&q1, 30); 
	insert(&q1, 40);
	insert(&q1, 50); 
	insert(&q1, 60); 
	insert(&q1, 70);
	// 큐 내용 전체 출력
	queuePrint(&q1);
	/*
	Queue has 7 element
	1 element : 10
	2 element : 20
	3 element : 30
	4 element : 40
	5 element : 50
	6 element : 60
	7 element : 70
	*/
	
	
	
	// 큐 원소 꺼내기
	printf("큐에서 %d을 꺼냈습니다.\n", delete(&q1));
	printf("큐에서 %d을 꺼냈습니다.\n", delete(&q1));
	printf("큐에서 %d을 꺼냈습니다.\n", delete(&q1));
	/*
	큐에서 10을 꺼냈습니다.
	큐에서 20을 꺼냈습니다.
	큐에서 30을 꺼냈습니다.
	*/
   
	// 큐에 원소 넣기
	insert(&q1, 80);  
	insert(&q1, 90); 
	
	// 큐 내용 전체 출력
	queuePrint(&q1);	
	/*
	Queue has 6 element
	1 element : 40
	2 element : 50
	3 element : 60
	4 element : 70
	5 element : 80
	*/
	
}

 

Array를 이용한 Queue의 문제점 : 표류 현상

Front index 왼쪽 부분은 비워져 있어도 사용을 못한다 -> 효율적인 메모리 사용이 불가함

 

이를 해결하기 위한 방법은 아래와 같다

• 큐의 원소가 하나 제거될 때마다 모든 원소를 왼쪽 이동 (Shift Left)
• Rear 인덱스가 오른쪽 끝에 와서 더 이상 증가시킬 수 없을 때 큐의 모든 원소를 빈 공간만큼 왼쪽 이동 (Shift Left)
• 원형 배열 (Circular Array)을 사용

---

Circular Array를 이용한 Queue의 표현

원형 배열 큐에서는 인덱스 만으로 빈 큐와 꽉 찬 큐를 검사하기 힘듦

비어있는 경우와 꽉 찬 경우 모두 Front와 Rear의 차이가 1 임 로테이션하기 때문에

삽입, 삭제 index를 계산할 때 dividend(%)를 사용한다.  queue max 사이즈로 나눈 나머지에 해당하는 배열에 넣어주면 됨.

 

but, 빈 큐와 꽉 찬 큐의 검사를 위해서 별도의 방법이 필요함  왜냐하면 원형 배열에 의해 아래와 같은 상황이 발생하면 앞에서 사용한 isEmpty 함수와 isFull 함수를 적용할 수 없다

아래와 같이 3번이 Front인 상황에서 삭제를 하면 Front는 1이 증가한다. Front > rear 이므로 Empty 상황이어야 하지만 실상은 Empty 가 아니다

또한 삽입의 상황에서도 마찬가지이다.

 

이를 해결하기 위해서 2 가지 방법을 사용할 수 있다

1) count

count 초기화 = 0

삽입되면 1 증가, 삭제되면 -1

카운터 변수가 0이면 empty이고, 꽉 차 있는지 확인 (MaxQueueSize == count)

2) Front와 Rear 사이에 빈 배열 넣기

큐에 모든 원소가 다 차는 경우에 발생하므로 큐에 최대한 채울 수 있는 배열을 MaxQueueSize-1로 설정한다.

공간 하나를 적게 사용하지만 , 별도의 카운터 변수 없이 사용이 가능하다

#define MaxQueueSize 6
typedef struct{
	int Front;
	int Rear;
	int Count;
	int data[MaxQueueSize];
}queueType;

void init(queueType *Qptr){
	Qptr->Front =0;
	Qptr->Rear = -1;
	Qptr->Count = 0;
}

int isEmpty(queueType *Qptr){
	return (Qptr->Count == 0);
}

int isFull(queueType *Qptr){
	return (Qptr->Count == MaxQueueSize);
}

int getSize(queueType *Qptr){
	return (Qptr->Count);
}

int insert (queueType *Qptr, int x){
	if(isFull(Qptr)){
		printf("Can't insert the item in queue, Queue is full\n");
	}else{
		// 이부분이 원형배열의 문제점을 보완해 주는 파트이다
		Qptr->Rear = (Qptr->Rear +1)%MaxQueueSize;
		Qptr->data[Qptr->Rear] = x;
		// 이부분이 원형배열의 문제점을 보완해 주는 파트이다
		Qptr->Count = Qptr->Count+1;
	}
}

int delete (queueType *Qptr){
	int temp;
	
	if (isEmpty(Qptr)){
		printf("Can't delete the item in queue, Queue is empty\n");
		return -1;
	}else{
		temp = Qptr->data[Qptr->Front];
		// 이부분이 원형배열의 문제점을 보완해 주는 파트이다
		Qptr->Front = (Qptr->Front+1)%MaxQueueSize;
		Qptr->Count = Qptr->Count-1;
		return temp;
		
	}
}

void queuePrint(queueType *Qptr){
	int i,j;
	
	printf ("Queue has %d element \n",getSize(Qptr));
	for (i =1; i <= Qptr->Count; i++){
		printf("%d element : %d\n", i, Qptr->data[j%MaxQueueSize]);
		j++;
	}
}

 

#include <stdio.h>
#include "queue_circular.h"

void main()
{
	// q1 이름을 가진 큐 생성
	queueType q1;
	init(&q1);   //초기화
	queuePrint(&q1); // Queue has 0 element

	// 큐에 원소 넣기
	insert(&q1, 10);
	insert(&q1, 20);
	insert(&q1, 30);
	insert(&q1, 40);
	insert(&q1, 50);
	insert(&q1, 60);
	insert(&q1, 70); //에러발생 : Can't insert the item in queue, Queue is full
	// 큐 내용 전체 출력
	queuePrint(&q1);
	/*
	Queue has 6 element
	1 element : 10
	2 element : 20
	3 element : 30
	4 element : 40
	5 element : 50
	6 element : 60
	*/


	// 큐 원소 꺼내기
	printf("큐에서 %d을 꺼냈습니다.\n", delete(&q1));
	printf("큐에서 %d을 꺼냈습니다.\n", delete(&q1));
	printf("큐에서 %d을 꺼냈습니다.\n", delete(&q1));
	/*
	큐에서 10을 꺼냈습니다.
	큐에서 20을 꺼냈습니다.
	큐에서 30을 꺼냈습니다.
	*/

	// 큐에 원소 넣기
	insert(&q1, 80);
	insert(&q1, 90);

	// 큐 내용 전체 출력
	queuePrint(&q1);
	/*
	Queue has 5 element
	1 element : 80
	2 element : 90
	3 element : 30
	4 element : 40
	5 element : 50
	*/
}

---

Linked List를 이용한 Queue의 표현

동적으로 생생된 노드를 연결하는 형태로 큐를 표현, 가장 먼저 삽입된 노드를 Front 포인터가 가리키고 가장 나중에 삽입된 노드를 Rear포인터가 가리킴

operation	desc
init	큐를 노드를 가리키는 변수 Front 와 Rear의 선언 및 NULL 로 초기화
insert	큐의 Rear 포인터가 가리키는 위치에 노드 삽입 후 Rear 포인터 이동
delete	큐의 Front 포인터가 가리키는 위치에 있는 노드를 삭제 후 Front 포인터 이동
getFront	큐의 Front 에 있는 데이터의 값을 반환
getSize	Front 부터 노드를 따라가며 노드 수를 카운트 한다
isEmpty	Front NULL 이면 비었다
isFull	개수의 제약이 없으나 전체크기에 제약을 두는 것은 가능

데이터의 삽입

데이터의 삭제

 

typedef struct node{
	char data;
	struct node* next;
}nodeType;

nodeType *Front;
nodeType *Rear;

void init(){
	Front = NULL;
	Rear = NULL;
}

int isEmpty(){
	return (Front == NULL);
}


int getSize(){
	nodeType *p;
	int count = 0;
	
	for (p= Front; p!=NULL; p = p->next){
		count ++;
	}
	return count;
}

void insert(char item){
	nodeType *p= (nodeType*)malloc(sizeof(nodeType));
	p->data = item;
	p->next = NULL;
	
	if(isEmpty()){
		// 빈 큐일 경우 Front 와 Rear가 모두 생성된 노드를 포인트
		Front = p;
		Rear = p;
	}else{
		Rear->next = p;
		Rear = p;
	}
}

char delete(){
	nodeType *p;
	char item;
	
	if(isEmpty()){
		printf("Can't delete the item in queue, Queue is empty\n");
		exit(1);
		
	}else{
		p = Front;
		Front = Front->next;
		item = p->data;
		free(p);
		return (item);
	}
}

void printQueue(){
	nodeType *p;
	printf ("Queue has %d element \n",getSize());
	for (p=Front; p!=NULL; p=p->next){
		printf("-----\n");
		printf("%c \n", p->data);
	}
}

 

#include <stdio.h>
#include <stdlib.h>
#include "queue_linkedlist.h"

void main(void)
{
	init();
	
	// 큐에 원소 넣기
	insert('A');
	insert('B');
	insert('C');
	insert('D');
	printQueue();	
	/*
	Queue has 4 element
	-----
	A
	-----
	B
	-----
	C
	-----
	D
	*/
	
	// 큐 원소 꺼내기
	printf("큐에서 %c를 꺼냈습니다.\n", delete());
	printf("큐에서 %c를 꺼냈습니다.\n", delete());
	//큐에서 A를 꺼냈습니다.
    //큐에서 B를 꺼냈습니다.
	printQueue();
	/*
	Queue has 2 element
	-----
	C
	-----
	D
	*/

	// 큐에 원소 넣기
	insert('O');
	insert('P');
	printQueue();	
	/*
	Queue has 4 element
	-----
	C
	-----
	D
	-----
	O
	-----
	P
	*/

}

---

Circular Linked List를 이용한 큐의 표현

원형 연결 리스트를 이용하면 Rear만 이용해서 큐 표현이 가능하다 왜냐하면 Rear 즉 큐의 마지막 노드를 가리키는 링크는 항상 큐의 첫 번째 노드를 가리키기 때문이다.

 

operation	desc
init	큐를 노드를 가리키는 변수  Rear의 선언 및 NULL 로 초기화
insert	큐의 Rear 포인터가 가리키는 위치에 노드 삽입 후 Rear 포인터 이동
delete	큐의 Rear 포인터가 가리키는 위치에 있는 노드 다음 노드 (즉, Front 노드)를 삭제
getFront	Front 부터 노드를 따라가며 노드 수를 카운트 한다
getSize	Front 부터 노드를 따라가며 노드 수를 카운트 한다
isEmpty	Front NULL 이면 비었다
isFull	개수의 제약이 없으나 전체크기에 제약을 두는 것은 가능

데이터의 삽입

void insert(char item){
  nodeType *p= (nodeType*)malloc(sizeof(nodeType));
  p->data = item;
  p->next = NULL;
  
 if(isEmpty()){
   Rear->next =p;
   Rear = p;
 }     
  
 else{    
    Rear->next =p;
    Rear=p;
   } 
}

데이터의 삭제

 

---

Deque (Double End Queue)

삽입과 삭제가 Front와 Rear 모두에서 가능한 구조

큐로도 동작이 가능하고 스택으로 동작할 수 있다.

원형 배열로 구현할 경우, Front , Rear 값이 증가하기도 하고 감소하기도 한다.