배열 기반 Bag 자료구조 개념

[ 이 게시물은 개념 설명 게시물이고 소스코드는 다음 게시물에 있습니다. ]

자료구조에서 흔히 보이지는 않지만 Bag이라는 자료구조가 있다.

이 자료구조의 원리는 다음과 같다.

'우리는 항상 가방에서 물건을 꺼낼 때 중간에 있는 물건을 먼저 잡기 마련이다. 그리고 그 중간의 물건을 꺼내게 된다'

는 발상에 근거하여 Bag 자료구조가 나타나게 되었다.

그림으로 설명하면 다음과 같다.

처음에는 -1로 초기화 된( 초기화 값은 코더가 설정해 주는 부분이다. )Bag Array가 있다.  

이때 한칸씩 Push하여 0번째 배열부터 6번째 배열까지 1~7의 값을 넣게 되었다.

이때 배열 위치를 가리키는 pos라는 변수는 마지막 값 다음 칸을 가리키고 있다.

그다음 Pop를 행할 때 이제 Bag 만의 Pop가 나오는데 (pos-1)과 처음 시작점의 중간 지점( (pos-1)/2 )을 가리키게 하여 Pop을 한다.  

그렇게 되면 4자리가 공백이 되니 한칸씩 왼쪽으로 당겨준다(아래 그림 참조) 이렇게 Bag 자료구조는 이루어져 있다.