<자료구조 알고리즘> 큐

 

 

큐란?

배열처럼 선형 구조의 자료구조(뭔가 한 줄이라는 느낌)이며 양쪽 끝에서 접근할 수 있고 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 자료구조이다. 스택은 데이터를 쌓는 데에 반해 큐는 데이터를 밀어 넣는다고 생각하면 쉽다.

자 차근차근 알아보도록 하자.

 

1. 종이컵 디스펜서

정수기 옆에 종이컵을 뽑아 먹을 수 있게 달려있는 종이컵 디스펜서 한 번 쯤은 써 보았을 것이다.  종이컵 디스펜서와 큐의 구조가 굉장히 비슷하다.

종이컵을 뽑을 때에는 아래에서 뽑고 종이컵을 보충해 줄 때에는 위에서 넣는다.

항상 맨 아래의 종이컵만 뽑을 수 있다. (중간에 있는 것을 먼저 뽑을 수는 없다.)

위에서 종이컵을 빼 내거나 아래에서 집어 넣을 수는 없다.

 

따라서 종이컵을 보충해서 뽑는 다고 생각했을 때 가장 먼저 넣은 종이컵을 가장 먼저 뽑게 된다. 이러한 구조를 first in first out 줄여서 FIFO라고 한다. 우리말로 하면 선입선출이라고 할 수 있을 듯 하다.

 

2. 큐

그러면 이제 본격적으로 큐를 알아보자, 큐는 아래와 같이 생겼다.

종이컵 디스펜서를 큐, 종이컵을 저장하는 데이터라고 생각하면 된다.

큐는 위에서 종이컵을 보충했던 것처럼 한쪽에서 데이터 삽입(queue.push()), 아래에서 종이컵을 뽑았던 것처럼 반대쪽 끝 데이터 삭제(queue.pop()) 

데이터 삭제 및 추가와 다르게 데이터에 접근하는 것은 데이터 삽입하는 쪽 데이터에 접근(q.back()), 삭제하는 쪽 데이터에 접근(q.front()) 이렇게 양쪽 모두 가능하다. 

※ 배열과 같이 i번째 값에 바로 접근 하는 것이 안되고 종이컵 디스펜서처럼 3번째 값을 알고 싶으면 앞에 있는 모든 데이터를 꺼내야 한다. 

 

3.구현

동적 배열을 이용해서도 구현을 할 수 있기는 하지만 중간에 있는 데이터에 접근하지는 않을 것이고 양 쪽 끝에서 길이 변화가 많이 발생할 테니 연결 리스트를 사용하는 것이 더 효율적일 것이다. 

구현은 다음 글에서.....