[자료구조] Stack과 Queue-2

본문과 관련하여 실습한 전체코드는 리파지토리에 별도 작성하였습니다.

https://github.com/ejImDev/data_structure_study.git

큐

삽입과 삭제가 양 끝에서 각각 수행되는 자료구조

선입선출(FIFO) 원칙하에 item의 삽입과 삭제 수행

큐를 배열로 구현하는 경우

1. 큐에서 삽입과 삭제를 거듭하게 되면 큐의 item들이 배열의 오른쪽 부분으로 편중되는 문제가 발생. 새 item들은 뒤에 삽입되고, 삭제는 앞에서 일어나기 때문
   

2. 위 항목이동 해결 방안
   방법 1) 큐의 item들을 배열의 앞부분으로 이동
   -> 수행시간이 큐에 들어있는 item의 수에 비례하는 단점
   
   

   방법 2) 배열을 원형으로. 즉, 배열의 마지막 원소가 첫 원소와 맞닿아있다고 여김
   
   

3. 방법 2로 새 item 삽입 후
   
   • 배열의 앞뒤가 맞닿아 있다고 생각하기 위해 배열의 rear 다음의 비어있는 원소의 인덱스
     
   • rear = (rear+1)%N (여기서 N은 배열의 크기)
     

4. 연속된 삭제를 하는 경우 큐의 마지막 item을 삭제한 후에 큐가 empty임에도 rear는 삭제된 item을 가리키게 됨. 다시 말해 front와 rear가 다른 item을 가리킴
   

5. 위 empty문제 해결 방안
   방법 1 ) item을 삭제할 때 마다 큐가 empty 되는지 검사하고, 만일 empty가 되면 front = rear = 0으로 만든다
   -> 삭제할 때 마다 조건검사를 하는것은 효율성이 저하됨
   
   

   방법2) front를 실제 가장 앞에있는 item의 바로 앞 비어있는 원소를 가리키게 한다.
   

   • 배열의 크기가 N이라면 실제로 N-1개의 공간만 item을 저장하는데 사용
     

참고 자료 : ‘경기대학교 소프트웨어중심대학사업단 - JAVA 자료구조’ https://youtu.be/iDNc_Ryhgcc