큐 Queue

큐 Queue

 

개념

* First in first out. 먼저 들어간 자료가 가장 먼저 나오는 구조이다.

* 양쪽에 구멍이 뚫린 느낌

 

제약

* 가장 앞에 있는 요소만 접근 가능하다. (중간이나 뒤에서 자료 접근 불가 )

 

 

삽입 (Enqueue)

<시작 or 메모리가 끝까지 채워지기 전>

* 그냥 차곡차곡 넣으면 됨. 

* 시간 복잡도 = O(1)

 

<메모리가 끝까지 채워졌는데, 앞부분에 빈 공간이 있을 때>

* 큐는 앞부분부터 자료가 빠져나가기 때문에 생기는 구조

* 다시 0부터 채워짐 (물론 비어있으면 ^^)

 

<결론>

* 메모리가 얼마나 쌓여있는가를 체크하는 변수가 2개인 것! (처음과 끝)

* 메모리의 끝이 다 사용되었고, 앞부분이 비어있다면

  다시 앞부분부터 채워지는 순환고리 형태의 메모리 사용을 볼 수 있다.

 

 

제거 (Dequeue)

* 큐가 얼마나 쌓여있는가를 처음과 끝을 가지고 판단한다.

* 처음이 가리키고 있는 부분을 다음으로 넘긴다.

* 시간 복잡도 = O(1)

 

 

검색

* Enqueue와 Dequeue만 할줄아는 큐에서 검색은 정신 나간다.

* 중간에 원하는 데이터를 찾았다고 해도 요소를 모두 빼낸 후 다시 집어넣어야한다. (순서 때문에)

  스택은 원하는 데이터를 찾은 부분부터 다시 요소를 집어넣으면 되지만 큐는 그러면 순서가 꼬여버린다.

  큐는 통로 형식이기 때문! 

* 모든 요소를 어차피 다 빼내야 한다면 차라리 다른 큐를 만들어서 집어넣으면 위에보단 빠르다.

* 어쩌피 시간 복잡도 = O(n)

 

 

언제 사용하냐?

* 자료의 처리속도보다 유입속도가 더 빠를 때 

* 입출력 스트립 버퍼

* 대기줄처럼 순서대로 들어가야 할 때

 

 

 

 

 

 

 

 

 

 

 

귀여운 그림은 낡은 창고님이 그리셨습니다.