큐 개념 정리 JAVA

바킹독강의

큐 정의

한쪽 끝에서 원소를 넣고 한쪽 끝에서 원소를 뺄 수 있는 자료구조

먼저 들어온 원소가 먼저 나오게 된다 FIFO 

 

큐 성질

4번은 원칙적으로 불가능하지만 배열로 만들면 구현은 가능하다

 

큐는 배열로 구현하면 쉽다.

 

구현

원소를 넣으면 tail이 한 칸 올라감

55 원소를 뺀다고 하면 head를 한 칸 올리면 된다. 굳이 0번지에 있는 55를 덮을 필요 없다

배열에서 dat[head]부터 dat[tail-1]번지가 바로 큐의 원소들이 들어있는 자리

큐의 크기는 tail - head

push 하면 tail이 증가하고 pop하면 head가 증가된다

 

큐를 삽입 삭제하게 되면 점점 오른쪽으로 밀려나가게 된다. 그러면 배열이니 앞의 공간을 못쓰게 된다

 

해결방법:원형으로 만들기(원형 큐)

head나 tail에 1이 더해질때 0번지로 다시 오도록 하면 된다.

 

다른 방법: 배열의 크기를 push의 최대수로 하면 된다

 

push 함수

void push(int x){
	 dat[tail++]=x
}

 

 

pop함수

void pop(){
	 head++;
}

 

 

front함수/back 함수

맨 처음 원소, 맨 뒤의 원소 확인하는 함수

 

int front(){
	return dat[head];
}

int back(){
	return dat[tail-1];
}

 

 

큐가 비어있을때 front/back, pop을 호출하면 런타임에러가 발생할 수 있다