2021. 3. 10. 17:01ㆍ코딩/자료구조
이번글은 큐에대해서 다뤄보려고 한다.
큐라는 알고리즘을 만들기위해 위에 도식화된 그림처럼 생각해보았다.
데이터를 전체 옮기는것 보다 포인터 두개를 두는게 효율적이라는 결론이 나온다.
push와 pop 대신 inque와 deque를 사용하겠다.
다음은 queue클래스를 구현하기위해 필요한 것들이다.
-인스턴스 변수
in_ptr - inque를 위한 포인터의 위치
de_ptr - deque를 위한 포인터의 위치
max - 큐 용량
queue - 데이터 저장
-클래스 메소드
생성자
-인스턴스 메소드
inque - 데이터 입력
deque - 데이터 출력
compareptr - 포인터의 결정
peek - 스택의 꼭대기 데이터
index - 검색을 통한 key값의 index찾기
clear - 스택 모든요소 제거 -> 데이터를 지우는게 아니라 스택을지운다.
capacity - 스택의 용량확인
size - 데이터의 수 확인
public void inque(int x){
if(out_ptr<in_ptr){
if(in_ptr>max-1){
if(out_ptr !=0){
in_ptr = 0;
queue[in_ptr++] = x;
}
else{
System.out.println("큐가 꽉찼습니다");
}
}
else if(out_ptr>in_ptr){
queue[in_ptr++] = x;
}
else{
~~->여기서 문제가 발생함 in_ptr == out_ptr 일때
맨처음 작성한 inque메소드인데 여기서 문제가 발생해 더이상 코드를 작성하지못했다.
in_ptr을 다음에 들어갈 데이터의 위치로 이용하고
out_ptr을 다음에 뽑아질 데이터의 위치로 이용을 하였다.
out_ptr < in_ptr 인 상황과 out_ptr> in_ptr 인 상황 둘다 정상적인데
in_ptr == out_ptr 인상황이 문제가 발생했다
-> 처음시작에는 데이터를 그냥 집어넣고 pointer을 옮기면 되지만
위의 문제를 해결할 방법이 없어 다른 방식으로 생각을 했다
데이터의 수를 변수로 추가를 한다면 pointer의 대소비교는 필요가 없어지게 된다.
아래가 수정된 큐 클래스로 자료 갯수 변수 추가로 인해 훨씬 간단하고 이해쉬운 코드가 되었다
class queue_exercise{
int in_ptr;
int out_ptr;
int max;
int[] queue;
int num;
public queue_exercise(int max, int[] queue){
this.in_ptr = 0;
tihs.out_ptr = 0;
this.num = 0; 생성자
this. max = max;
this.queue =queue;
}
public void inque(int x){
if(num==max) ===> 데이터의 개수 = 최대개수 일때
System.out.println("큐가 꽉찼습니다");
else{
queue[in_ptr++] = x;
num++; ===> 데이터가 한개 추가될때마다 데이터개수의 증가를 반영하기위해
if(in_ptr ==max)
in_ptr=0;
}
}
public int deque(){
if(num ==0) ===> 데이터의개수 =0일때
return -1;
else{
num--; ===> 데이터가 하나 빠졋기때문에 데이터 감소 반영 위해
int out_result = queue[out_ptr++]; ===> 결과값을 출력해야하는데 out_ptr+1 = max이면 out_ptr을 0으로 바꿔야 하므러
if(out_ptr ==max)
out_ptr = 0;
return out_result;
}
}
~~~~
나머지 메소드는 앞글에서 배운 스택과 비슷하여 이후내용은 스킵하겠다.
'코딩 > 자료구조' 카테고리의 다른 글
| 자료구조 11 - 재귀 알고리즘(1) (0) | 2021.03.11 |
|---|---|
| 자료구조 09 - 스택과 큐(1) (0) | 2021.03.09 |
| 자료구조 08 - 이진 검색 (0) | 2021.03.07 |
| 자료구조 07 - 선형 검색 (0) | 2021.03.06 |
| 자료구조 06 - 클래스 (0) | 2021.03.06 |